| ENG RUS | Timus Online Judge |
Обсуждение задачи 1589. СокобанGrandmaster Sokoban visualizer // Задача 1589. Сокобан 6 июн 2022 01:52 https://soucupb.github.io/Sokoban-Solver/ I will leave this here. It is a visualizer to test your solution. Maybe somebody will find this useful. † SiriuS † Has anyone calculated the maximum possible number of boxes? // Задача 1589. Сокобан 25 мар 2022 18:19 My max value is 13: ######## #@ $.$.# # $.$.# #$ $.$.# #. $.$.# #$ $.$.# #. $.# ######## Has anybody found more? Oracle[Lviv NU] TLE #62 [4] // Задача 1589. Сокобан 3 ноя 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 Oracle[Lviv NU] Re: TLE #62 [3] // Задача 1589. Сокобан 7 ноя 2009 03:54 AC finally. Vitalii Arbuzov Re: TLE #62 [2] // Задача 1589. Сокобан 30 апр 2011 23:13 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? Oracle[Lviv NU] Re: TLE #62 [1] // Задача 1589. Сокобан 19 май 2011 02:05 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. adityarev Re: TLE #62 // Задача 1589. Сокобан 6 июн 2019 05:54 Hi Oracle, can u give us some cases that considered as a bad position? I have a prunning issue also on my solution adityarev Any other suggestion? [1] // Задача 1589. Сокобан 17 апр 2019 16:35 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 :) 🦄Imosk72🦄∭GTGU∭ Re: Any other suggestion? // Задача 1589. Сокобан 5 июн 2019 12:53 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 Shen Yang give a configuration, is there O(P) sol to judge it has a sol?? [1] // Задача 1589. Сокобан 13 янв 2019 12:39 I think the answer is probablye Yes... Shen Yang Re: give a configuration, is there O(P) sol to judge it has a sol?? // Задача 1589. Сокобан 13 янв 2019 12:42 I think it is relating to the number of inverse pairs of permuation.. Vitalii Arbuzov TL 57 give me some hard test data [5] // Задача 1589. Сокобан 28 апр 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] // Задача 1589. Сокобан 29 апр 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 // Задача 1589. Сокобан 1 май 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 // Задача 1589. Сокобан 9 июл 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 писал(a) 28 апреля 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 // Задача 1589. Сокобан 19 авг 2016 15:41 ###### ## . # # * # # # .$ # # #$## ## @ # ##### Empted Re: TL 57 give me some hard test data // Задача 1589. Сокобан 17 авг 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 Shen Yang how to submit in visual C++ 2017 // Задача 1589. Сокобан 8 дек 2017 11:43 visual C++ 2017 can't use gets() too egg hurt Shen Yang admin,please check test case 18 [1] // Задача 1589. Сокобан 6 дек 2017 12:17 I think this is a no solution test I output empty and pass this test... Shen Yang Re: admin,please check test case 18 // Задача 1589. Сокобан 7 дек 2017 12:01 wa haha AC again,hahahaha two hardest problems Shen Yang there are about 3*10^7 states not consider the position of player. [1] // Задача 1589. Сокобан 15 ноя 2016 13:00 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 Shen Yang Re: there are about 3*10^7 states not consider the position of player. // Задача 1589. Сокобан 15 ноя 2016 13:12 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... Orient Hallelujah, how did you solved this problem so quickly? [1] // Задача 1589. Сокобан 2 май 2016 16:18 3 days overall. I'm your fan forever. Edited by author 03.05.2016 14:58 Orient Hallelujah, how did you solved this problem so quickly? // Задача 1589. Сокобан 2 май 2016 16:19 Can you give us some tips on your approach? Thanks in advance. Edited by author 03.05.2016 14:58 Vladimir Yakovlev (USU) Problem 1589 "Sokoban". New tests added [4] // Задача 1589. Сокобан 14 июл 2011 15:18 The problem is rejudged, one author have lost AC. Thanks to Erop [USU] Dest Re: Problem 1589 "Sokoban". New tests added // Задача 1589. Сокобан 27 авг 2011 20:32 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? Oracle[Lviv NU] Re: Problem 1589 "Sokoban". New tests added [2] // Задача 1589. Сокобан 5 сен 2011 01:05 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 Dest Re: Problem 1589 "Sokoban". New tests added [1] // Задача 1589. Сокобан 5 сен 2011 13:12 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: ######## #._.@__# #$$$*$*# #._$___# #.$.*_*# #_$.$__# #._.*__# ######## Oracle[Lviv NU] Re: Problem 1589 "Sokoban". New tests added // Задача 1589. Сокобан 6 сен 2011 01:26 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! Vasilenko Oleg (South Ural State University) to admins [6] // Задача 1589. Сокобан 20 июл 2009 09:32 I have a good test. Can you add it? Vladimir Yakovlev (USU) Re: to admins [5] // Задача 1589. Сокобан 20 июл 2009 12:32 Send it to our support email Vasilenko Oleg (South Ural State University) Re: to admins [4] // Задача 1589. Сокобан 20 июл 2009 13:10 I've sent a test to "timus_support@acm.timus.ru". Have you received it? Vladimir Yakovlev (USU) Problem is rejudged. Thank you [3] // Задача 1589. Сокобан 25 июл 2009 20:21 Vasilenko Oleg (South Ural State University) Re: Problem is rejudged. Thank you [2] // Задача 1589. Сокобан 15 апр 2010 14:38 I have got new good test. Can you add it? Vladimir Yakovlev (USU) Re: Problem is rejudged. Thank you [1] // Задача 1589. Сокобан 17 апр 2010 12:09 Send it to our support email Vasilenko Oleg (South Ural State University) Re: Problem is rejudged. Thank you // Задача 1589. Сокобан 18 апр 2010 18:37 I've sent a test to "timus_support@acm.timus.ru". KiedaP Question about judge [2] // Задача 1589. Сокобан 19 мар 2010 03:25 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 † Ленин † [Yaroslavl SU] Re: Question about judge // Задача 1589. Сокобан 22 мар 2010 10:03 IMHO just no longer than 10000 symbols. 3 ≤ n, m ≤ 8 Oracle[Lviv NU] Re: Question about judge // Задача 1589. Сокобан 3 апр 2010 20:07 Yes, any answer, not longer than 10000 symbols will be accepted. Progbeat to admins [7] // Задача 1589. Сокобан 19 янв 2008 01:04 i got ac, but my program can't pass some tests.. can you add these tests? Edited by author 19.01.2008 01:06 Sandro (USU) Re: to admins [6] // Задача 1589. Сокобан 22 янв 2008 14:36 Yes, send your tests to Sandro at Plotinka Ru and we'll add them. Progbeat Re: to admins [5] // Задача 1589. Сокобан 23 янв 2008 13:28 i've sent tests to your mail. have you received them? Vladimir Yakovlev (USU) Your tests have been added. Submissions will be rejudged soon (-) [4] // Задача 1589. Сокобан 23 янв 2008 14:03 Vladimir Yakovlev (USU) Problem has been rejudged (-) [3] // Задача 1589. Сокобан 28 янв 2008 23:42 Oracle[Lviv NU] Re: Problem has been rejudged (-) [2] // Задача 1589. Сокобан 7 ноя 2009 03:33 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 Oracle[Lviv NU] Re: Problem has been rejudged (-) [1] // Задача 1589. Сокобан 13 ноя 2009 22:46 Hey, have somebody read my previsious post? Are admins alive? Vladimir Yakovlev (USU) Your tests were added. Problem rejudged. Thank you! // Задача 1589. Сокобан 4 дек 2009 11:09 Sasha Bar [TNU] admins : Test 3 is incorrect [1] // Задача 1589. Сокобан 11 янв 2009 16:03 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 Vladimir Yakovlev (USU) Re: admins : Test 3 is incorrect // Задача 1589. Сокобан 26 июл 2009 21:07 Lengths of lines may differ, because the spaces at the end of lines are omitted. gnaggnoyil Is there anyone who accepted? [1] // Задача 1589. Сокобан 21 янв 2009 16:45 I always TLE in 9# and 10#. How shuold I deal with it? DK [Samara SAU 1: X2008] Re: Is there anyone who accepted? // Задача 1589. Сокобан 16 апр 2009 23:18 And I have TLE-55 ;) shangjingbo WA#7 // Задача 1589. Сокобан 27 ноя 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? Oracle WA#3 - can anybody give me some tests? [4] // Задача 1589. Сокобан 30 окт 2007 00:49 Nazgul Re: WA#3 - can anybody give me some tests? [3] // Задача 1589. Сокобан 25 ноя 2008 13:42 I need too...-_-! Vedernikoff Sergey (HSE: EconomicsForever!) Re: WA#3 - can anybody give me some tests? [2] // Задача 1589. Сокобан 25 ноя 2008 15:54 ######## #..... # #$$$$$@# # .....# #$$$$$$# # $.# #. $.$.# ######## Nazgul Re: WA#3 - can anybody give me some tests? [1] // Задача 1589. Сокобан 26 ноя 2008 10:40 #$$$$$$# # $.# <----- isn't the wall around the board? #. $.$.# Vedernikoff Sergey (HSE: EconomicsForever!) Re: WA#3 - can anybody give me some tests? // Задача 1589. Сокобан 26 ноя 2008 17:39 Ok, the following is good test, I changed spaces to "O"s... ######## #.....O# #$$$$$O# #OO...O# #$$$$$O# #O.OO$.# #.O$.$+# ######## Orenburg SU 7 About test 3 [1] // Задача 1589. Сокобан 7 апр 2008 01:39 Why in test 3 input is not table n on m? Nazgul Re: About test 3 // Задача 1589. Сокобан 17 окт 2008 09:41 I need test3 too... 3AbEI/I Problem with checker [6] // Задача 1589. Сокобан 28 окт 2007 22:22 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. Sergey Pupyrev [USU] Re: Problem with checker [5] // Задача 1589. Сокобан 28 окт 2007 23:00 Are u sure that your second answer is really "rrdddrruLdlUUUluRR"? Checker on my local system outputs 'ok' for 2nd test case on both answers. Alias (Alexander Prudaev) Re: Problem with checker [1] // Задача 1589. Сокобан 28 окт 2007 23:37 my answer is rrdddrruuLrddllluuurDlddrUluRddrruLruLddlluuRlddrruLrruLdldlluururDllddrUluurDlddrrUdlluurRlldRdrUUUluRR i check it, it is right answer too but a have WA2 Alias (Alexander Prudaev) Re: Problem with checker // Задача 1589. Сокобан 28 окт 2007 23:56 test case #2 is the same test as Sample#2 ? 3AbEI/I Re: Problem with checker [2] // Задача 1589. Сокобан 29 окт 2007 00:06 I rechecked answer just now. It was "rrdddrruLdlUUUluRR". 3AbEI/I Re: Problem with checker // Задача 1589. Сокобан 29 окт 2007 00:18 Everything seems to be ok now. I've submitted the same solution, and now I have TLE6... Sergey Pupyrev [USU] Re: Problem with checker // Задача 1589. Сокобан 29 окт 2007 00:20 Yes, the second test is sample. There were some problems with checker. Now it's all right. Old solutions will be rejudged soon.
|