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!