| Show all threads Hide all threads Show all messages Hide all messages |
| Sokoban visualizer | Grandmaster | 1589. Sokoban | 6 Jun 2022 01:52 | 1 |
|
| Has anyone calculated the maximum possible number of boxes? | † SiriuS † | 1589. Sokoban | 25 Mar 2022 18:19 | 1 |
My max value is 13:
########
#@ $.$.#
# $.$.#
#$ $.$.#
#. $.$.#
#$ $.$.#
#. $.#
########
Has anybody found more? |
| TLE #62 | Oracle[Lviv NU] | 1589. Sokoban | 6 Jun 2019 05:54 | 5 |
TLE #62 Oracle[Lviv NU] 3 Nov 2009 20:40 Can somebody give me some hard test - my program works fine on all tests, which I can think out. BTW, here is some of them:
########
#.OOOOO#
#$O$O$O#
#OO$O$O#
#@O$O$O#
###***O#
#......#
########
########
#.O$OO.#
#O$..$O#
#$$..$O#
#O$..$$#
#@$O.$O#
#..$OO.#
########
########
#.O$OO.#
#O$..$O#
#$$..$O#
#O$..$$#
#@$..$O#
#.O$OO.#
########
########
#......#
###***O#
#@O$O$O#
#OO$O$O#
#$O$O$O#
#.OOOOO#
########
########
#.....O#
#$$$$$O#
#OO...O#
#$$$$$O#
#O.OO$.#
#.O$.$+#
########
########
#......#
###***O#
#@O$O$O#
#OO$O$O#
#OO$O$O#
#OOOOOO#
########
########
#.$.$OO#
#@OOOOO#
#O$$$$$#
#O.....#
#$$$$$$#
#......#
########
########
#.OOO.O#
#@$O##O#
#OOO*OO#
#.$O$O$#
#$$$$..#
#...OOO#
########
########
#OOOO.O#
#@OO##O#
#OOO*OO#
#.$O$OO#
#$$$$.O#
#...OOO#
########
#######
#@$OO.#
#$O$OO#
#.O.OO#
#######
P.S. space I've changed to O.
Edited by author 03.11.2009 20:42 I have TLE 62 too. Don't have ideas of how to proceed.
Can you give a hint of how you have improved you program to pass this test? I've stored only those positions, which can not be processed in some steps by greedy algo + store only positions, where man is in lowest-left cell + stop, when position is surely bad (I've used a lot of classes of bad positions) + make moves, that is surely necessary. Hi Oracle, can u give us some cases that considered as a bad position? I have a prunning issue also on my solution |
| Any other suggestion? | adityarev | 1589. Sokoban | 5 Jun 2019 12:53 | 2 |
Hi guys, i've tried to solve this problem with A*. I came with pull distance as heuristic and calculate the distance table with Floyd's algorithm. I also have put deadlock detector (for Simple and Frozen) on my code. Is there something i miss? Or do you have any other suggestion?
I am very happy if i can discuss with you guys. Thanks before for your help :) I know some interesting optimisations which helped me get TLE 78 but I don't understand how to use A* in this problem. Let's discuss it. My email is imoskovchenko72@gmail.com |
| give a configuration, is there O(P) sol to judge it has a sol?? | Shen Yang | 1589. Sokoban | 13 Jan 2019 12:42 | 2 |
I think the answer is probablye Yes... I think it is relating to the number of inverse pairs of permuation.. |
| TL 57 give me some hard test data | Vitalii Arbuzov | 1589. Sokoban | 17 Aug 2018 14:59 | 6 |
Many thank to Oracle[Lviv NU]. His test data helped me a lot. But now my program solves all that tests as well as any test that I can imagine.
Can anyone give test cases that he consider to be hard.
Thanks! I've found one test that takes about 20 seconds to process. It looks quite simple but for my greedy approach it's real hell
########
#......#
#------#
#*****-#
#------#
#$$$$$$#
#-----@#
########
Now it takes about 3 seconds to process this test but still TL 57-62...
Other not bad test:
########
#.....-#
#--##--#
#-*----#
#--#-#-#
#$$$$$$#
#-----+#
########
Edited by author 01.05.2011 00:06
Edited by author 01.05.2011 02:34 It looks hardly possible to pass this problem in Java.
I have really good solution but depending on configuration I always get TL 56,57 or 62.
Maybe I've missed cool truncation?
I store situation in one long variable in bit representation. In this case it's easy to check if all blocks are on their places (just do binary &)
Also I use 3 different heuristics to filter deadlock situations (Block with unreachable destination, stuck block not on destination, strongly connected area without man inside and with amount of blocks greater then amount of destinations) Also I use priority queue and process turns wich moves blocks closer to closest unblocked destination than it was in previous turn. I turn off heuristics automatically if they are not effective in current situation. (it looks effective on some tests but it doesn't actually help to pass 62 :D )
I'm pretty sure that even simpler C++ solution can pass all tests.
Java, Java, why you are so slow?...
Time limit is too strict.
Admins, is it good idea to add this problem to list of problems that one can have problem with using Java?
Guys...
If you have good ideas of how to improve don't hesitate to write them here.
Thanks,
Vitaliy
Edited by author 01.05.2011 02:31 My method needs a plenty of memory to store information, although got a Memory Limit Exceeds, but it can give out a solution to all the hard data in discuss in less than 0.1s. however, I still found some data that make my program run very slow(up to 2s), and even can not provide a solution(the solution exists). ######## #.O....# #####OO# #.@$OO$# #$O$O$O# #OO$O$O# #.$OOO.# ######## ######## #.O.O..# #####OO# #.@$OO$# #$O$O$O# #OO$O$O# #.$OO..# ######## ######## #......# #.OOO$@# #.O$OO$# #$O$O$O# #O$$O$O# #.$OOO.# ######## ######## #......# #.OOO$O# #.@$OO$# #$O$O$O# #O$$O$O# #.$OOO.# ######## can any one who passed this problem share some more outstanding ideas about how to optimize the algorithm? Many thank to Oracle[Lviv NU]. His test data helped me a lot. But now my program solves all that tests as well as any test that I can imagine.
Can anyone give test cases that he consider to be hard.
Thanks! ######
## . #
# * # #
# .$ #
# #$##
## @ #
##### my personal favorites:
########
##.* $.#
# * . #
# *. #
## $.$ #
# $*$$$#
#.. @#
########
and next is hard only if you don't use any estimate func:
########
#. #
#$ $ $ #
#@ $ $ #
# $ $ #
# ****#
#......#
########
Edited by author 17.08.2018 15:25 |
| how to submit in visual C++ 2017 | Shen Yang | 1589. Sokoban | 8 Dec 2017 11:43 | 1 |
visual C++ 2017 can't use gets() too egg hurt |
| admin,please check test case 18 | Shen Yang | 1589. Sokoban | 7 Dec 2017 12:01 | 2 |
I think this is a no solution test
I output empty and pass this test... wa haha AC again,hahahaha two hardest problems |
| there are about 3*10^7 states not consider the position of player. | Shen Yang | 1589. Sokoban | 15 Nov 2016 13:12 | 2 |
if consider the position of player there are about 7.5*10^8(upper_bound),state, we can come up some idea
to compact the states,and use a huge array instead of hash_table to prevent the duplication of states this may far speed up your program
Edited by author 15.11.2016 13:02
Edited by author 15.11.2016 13:02 maybe for every 3*10^7 possible states,we can compact the postion of player and record the number of connected place,and use twice bfs search I think that will reduce the number of states we must store... |
| Hallelujah, how did you solved this problem so quickly? | Orient | 1589. Sokoban | 2 May 2016 16:19 | 2 |
3 days overall. I'm your fan forever.
Edited by author 03.05.2016 14:58 Can you give us some tips on your approach? Thanks in advance.
Edited by author 03.05.2016 14:58 |
| Problem 1589 "Sokoban". New tests added | Vladimir Yakovlev (USU) | 1589. Sokoban | 6 Sep 2011 01:26 | 5 |
The problem is rejudged, one author have lost AC. Thanks to Erop [USU] Yeah, thanks to Erop [USU] :).
I wish to add some tests too.
I’ve sent them to "timus_support@acm.timus.ru". Did you receive them? If it is possible, can I see test #92 (or some similar)? I've spent a lot of time getting "Accepted", but still no idea, what kind of test is it.
Thanks.
P.S. my mail: Oracle@acm.lviv.ua
Edited by author 05.09.2011 11:56
Edited by author 05.09.2011 11:56 What do you mean under "kind of test"? Walls, boxes... as usually.
I think that it's very small to have a "kind".
It has about 110 pushes in push-optimal solution.
But, seems that pushes not a primary factor of hardiness.
Here is the test (very easy) that has 100 pushes in push-optimal solution:
########
#._.*__#
##$_*__#
##__*_*#
##_*__.#
#_$$**$#
#@.____#
########
I suppose that it's hard because of huge amount of states passes through without pruning, and estimation function can't do anything in first 2/3 of search tree because of boxes are placed at goals and removed from them many times.
Here is another test (hard. But, maybe, your solver cracks it instantly) with only 73 pushes:
########
#._.@__#
#$$$*$*#
#._$___#
#.$.*_*#
#_$.$__#
#._.*__#
######## About kind: some boxes should be moved from one "room" to another, a lot of boxes on board, etc.
Really, first test is quite easy (about 2 seconds for my algo on my laptop)... And second is real hell))) On my laptop it takes about 10 seconds to solve it. And solution is found only at the end of the search (all of about 800000 possible states should be tested).
My solution do not give push-optimal solution nor move-optimal solution (and I do not use any estimation function at all), but nevertheless it is also hard for my algo too.
Thanks a lot! |
| to admins | Vasilenko Oleg (South Ural State University) | 1589. Sokoban | 18 Apr 2010 18:37 | 7 |
to admins Vasilenko Oleg (South Ural State University) 20 Jul 2009 09:32 I have a good test. Can you add it? Send it to our support email Re: to admins Vasilenko Oleg (South Ural State University) 20 Jul 2009 13:10 I've sent a test to "timus_support@acm.timus.ru". Have you received it? I have got new good test. Can you add it? Send it to our support email I've sent a test to "timus_support@acm.timus.ru". |
| Question about judge | KiedaP | 1589. Sokoban | 3 Apr 2010 20:07 | 3 |
Hello, i am a newfag at this judge system, and i have some questions:
The output information must be minimalize, or only no longer than 10000 symbols? Different and true solutions are all accepted?
What biggest number 'n' could be?
Edited by author 19.03.2010 03:26 IMHO just no longer than 10000 symbols.
3 ≤ n, m ≤ 8 Yes, any answer, not longer than 10000 symbols will be accepted. |
| to admins | Progbeat | 1589. Sokoban | 4 Dec 2009 11:09 | 8 |
i got ac, but my program can't pass some tests.. can you add these tests?
Edited by author 19.01.2008 01:06 Yes, send your tests to Sandro at Plotinka Ru and we'll add them. i've sent tests to your mail. have you received them? Can you, please, add my tests too? It seems to me, that they are quite hard. I've sent them to "timus_support@acm.timus.ru".
Edited by author 07.11.2009 04:04 Hey, have somebody read my previsious post? Are admins alive? |
| admins : Test 3 is incorrect | Sasha Bar [TNU] | 1589. Sokoban | 26 Jul 2009 21:07 | 2 |
char em[10][20];
int n = 0, m = 0;
...
while (gets(em[n++]) && em[n-1][0]);
--n;
m = (int) strlen(em[0]);
...
this code doesn't pass test 3 and gets WA, but if i insert this line
if (m != strlen(em[1])) while(true);
it gets Time Limit Exceeded !!! check it
Edited by author 16.01.2009 23:18 Lengths of lines may differ, because the spaces at the end of lines are omitted. |
| Is there anyone who accepted? | gnaggnoyil | 1589. Sokoban | 16 Apr 2009 23:18 | 2 |
I always TLE in 9# and 10#.
How shuold I deal with it? |
| WA#7 | shangjingbo | 1589. Sokoban | 27 Nov 2008 10:54 | 1 |
WA#7 shangjingbo 27 Nov 2008 10:54 what's the test#7?
I tried many tests myself.
All is OK except time limit exceed.
Could you give me any tests? |
| WA#3 - can anybody give me some tests? | Oracle | 1589. Sokoban | 26 Nov 2008 17:39 | 5 |
########
#..... #
#$$$$$@#
# .....#
#$$$$$$#
# $.#
#. $.$.#
######## #$$$$$$#
# $.# <----- isn't the wall around the board?
#. $.$.# Ok, the following is good test, I changed spaces to "O"s...
########
#.....O#
#$$$$$O#
#OO...O#
#$$$$$O#
#O.OO$.#
#.O$.$+#
######## |
| About test 3 | Orenburg SU 7 | 1589. Sokoban | 17 Oct 2008 09:41 | 2 |
Why in test 3 input is not table n on m? |
| Problem with checker | 3AbEI/I | 1589. Sokoban | 29 Oct 2007 00:20 | 7 |
There is some problem with checker.
The last two my submitions differs only in priority of directions ('d', 'u', 'r', 'l' and 'r', 'l', 'd', 'u', so result for second example was "dddrrrruLdlUUUluRR" and "rrdddrruLdlUUUluRR" respectively), and the first of this attempts was WA3 while the second one was WA2. Please fix this problem or add some requirements to make the answer to be unique. Are u sure that your second answer is really "rrdddrruLdlUUUluRR"? Checker on my local system outputs 'ok' for 2nd test case on both answers. my answer is
rrdddrruuLrddllluuurDlddrUluRddrruLruLddlluuRlddrruLrruLdldlluururDllddrUluurDlddrrUdlluurRlldRdrUUUluRR
i check it, it is right answer too
but a have WA2 test case #2 is the same test as Sample#2 ? I rechecked answer just now. It was "rrdddrruLdlUUUluRR". Everything seems to be ok now. I've submitted the same solution, and now I have TLE6... Yes, the second test is sample.
There were some problems with checker. Now it's all right.
Old solutions will be rejudged soon. |
