| ENG RUS | Timus Online Judge |
Discussion of Problem 1589. SokobanVitalii Arbuzov TL 57 give me some hard test data [5] // Problem 1589. Sokoban 28 Apr 2011 21:14 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! Vitalii Arbuzov Re: TL 57 give me some hard test data [1] // Problem 1589. Sokoban 29 Apr 2011 02:41 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 Vitalii Arbuzov Re: TL 57 give me some hard test data // Problem 1589. Sokoban 1 May 2011 02:17 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 Xinyu Zhou Tim Re: TL 57 give me some hard test data // Problem 1589. Sokoban 9 Jul 2011 11:41 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? Vitalii Arbuzov wrote 28 April 2011 21:14 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! Alexandr Vasilyev Re: TL 57 give me some hard test data // Problem 1589. Sokoban 19 Aug 2016 15:41 ###### ## . # # * # # # .$ # # #$## ## @ # ##### Empted Re: TL 57 give me some hard test data // Problem 1589. Sokoban 17 Aug 2018 14:59 my personal favorites: ######## ##.* $.# # * . # # *. # ## $.$ # # $*$$$# #.. @# ######## and next is hard only if you don't use any estimate func: ######## #. # #$ $ $ # #@ $ $ # # $ $ # # ****# #......# ######## Edited by author 17.08.2018 15:25 |