ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1589. Sokoban

TL 57 give me some hard test data
Posted by Vitalii Arbuzov 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!
Re: TL 57 give me some hard test data
Posted by Vitalii Arbuzov 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
Re: TL 57 give me some hard test data
Posted by Vitalii Arbuzov 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
Re: TL 57 give me some hard test data
Posted by Xinyu Zhou Tim 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!
Re: TL 57 give me some hard test data
Posted by Alexandr Vasilyev 19 Aug 2016 15:41
 ######
##  . #
# * # #
# .$  #
#  #$##
## @ #
 #####
Re: TL 57 give me some hard test data
Posted by Empted 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