Discussion of Problem 1325. DirtTHIS TEST 6 5 1 3 6 3 11112 22221 11112 22212 21112 22222 ANS:7 1 I changed my INF to 1e18 and got AC I spent about an hour till i figured out that: If it is impossible to get from the computer to the refrigerator, you should output 0 0. !!!! Thank u so much! How should I forget this! Can anybody that had WA7 give me some hints? Thanks Maybe that's because you didn't calculate the right shortest-path with the least boots changed(that is, your first number of the output is wrong, but the other one is right). I've got WA7 because I used only one bfs to calculate both values. 2 bfs should be used. (BTW, some of my classmates said only one bfs could also work??? I'm not sure about this. Lee algorithm. Runs in O(N * M). If you don't know it, here is a short description: you start from starting position (sl, sc) and now you expand this node; in a queue you put all its neighbours. You do this only if you optimize by going to that neighbour, i.e. the current cost is shorter than the previous one. let a[i][j] be a matrix with two fields: boots and length. a[i][j] means: minimum number of boots and minimum length to reach (i, j) from start position. You expand from (x, y) to a neighbour (c, d) when: a[x][y].boots + 1 (if you change boots, 0 else) < a[c][d].boots or a[x][y].boots + 1 = a[c][d].boots and a[x][y].length + 1 < a[c][d].length. Obvious, you take the valid neighbours (not 0s or outside ones) hope it's clear... Can someone explain where is the problem in this solution? I just used the algorithm as you described. But it got tle. Anyway thank you very much. Now I've got it,using heap will help me. Edited by author 19.04.2004 20:55 I wrote the solution with Lee's algorithm, as it was discribed above by Gheorghe Stefan, and got TL on test 16. I doubt it works in O(MN). I test the solution at my local computer - it gaves the correct answers (obviously), but works about 10 times slower, then my solution with Dijkstra! I BFS on number of boots and Dijkstra on walk-length inside odd/even slices. Dijkstra is linear-time here because of same-length edges (front line is kept as bidirectional list in non-descending order of walk-length, insertion position goes only forwards). AC in 0.062 sec :) Edited by author 21.08.2008 21:13 It could be proved that in Dijkstra's algorithm the choice K = E /V is assimptotically optimal. So, applying to our problem, E / V equals to 8. My old C++ solution got AC with optimized Dijkstra, O(v*log(v)), where v = m*n. The timing was 0,406 sec. Evidently, with Python (2.7, 3.4) I got TLE with the same solution. On my machine 500*500 case runs for 4.5 seconds. Then I realized O(m*n) solution and optimized input as much as possible (Python). It still gives TLE16, on my machine - runs for 2.3 seconds. Then I run code under PyPy (5.4.1, Python2.7 compatible) and on my machine it runs for 0.383 seconds only. I hope it would AC if PyPy is able to be selected as a programming language. Please add PyPy! Thanks Gimme some data, please Example test: 8 8 1 1 8 8 22122111 22121122 22212211 11111222 11122211 22212222 22112121 11122221 Distance table of my TLE21 solution: 0 1 2 4 4 5 6 7 1 1 2 3 4 5 6 7 2 2 2 3 4 5 6 7 3 3 3 3 4 5 6 7 4 4 4 7 6 6 6 7 10 9 8 5 7 7 7 8 10 9 6 6 8 8 8 8 8 7 7 9 9 9 9 9 Distance table of my WA25 solution: 0 1 2 4 4 5 6 7 1 1 2 3 4 5 6 7 2 2 2 3 4 5 6 7 3 3 3 3 4 5 6 7 4 4 4 7 6 6 6 7 10 9 8 7 7 7 7 8 10 9 8 8 8 8 8 8 10 9 9 9 9 9 9 9 Gotta investigate it yet... How can you do it, I'am puzzled. Can you solve it today??? Edited by author 23.04.2004 11:29 Dijkstra via STL priority_queue<> ~0.25 sec Dijkstra via hand-written heap implemented with change_priority() function ~ 0.125 sec how? First. You can contract all regions in one vertex. Second. You can find shortest distance by regions. Third. Remove useless regions. BFS what was left. I don't agree your opinion.The method can't work out in time.This method I had used to solve,but fail. First. You can contract all regions in one vertex. Second. You can find shortest distance by regions. Third. Remove useless regions. BFS what was left. I don't agree your opinion.The method can't work out in time.This method I had used to solve,but fail. Why? I have impelemnted in O(N*M) --> AC in 0.359 s It's very nice method! I have got AC in 0.203s Try this test: 6 5 1 3 6 3 11111 12222 11112 12222 11112 22222 Correct answer: 7 1 So, after 1st BFS both components stay alive. What would prevent 2nd BFS from going a vertical line and output "6 1" while assumed path yields "6 5"? I'm sorry, but can anybody describe me 2nd BFS? I spent a lot of time trying, but it give me wrong answer on some tests. Now I know that's used colouration. Edited by author 29.04.2004 16:37 So fast !!!!!! I got TLE on test 16 all the time ........ I don't know what does "colouration" mean . Could you explain ? Could you say your way ? Oberon (Yura Znovyak) had told the method very clarity. So fast !!!!!! I got TLE on test 16 all the time ........ I don't know what does "colouration" mean . Could you explain ? Could you say your way ? Thanks . I just uesd 0.187s to get AC ! but i think it's possible that such condition appears: in the first BFS to find shortest distance by Changing Boots,there may be many ways to get the shortest Changes. but these ways are different in shortest way of Walking. So? I do not understand :( in the first BFS to find shortest distance by Changing Boots,there may be many ways to get the shortest Changes First BFS is for shortest distance by Changing Boots Then we throw away all useless regions and use SECOND BFS for shortest way of Walking Of course for each region we store min boot change to get to it. While finding shortest walking distance we almost ignore regions. Why almost: we make jumps only on regions with higher boot changes. So we can avoid saw-like regions. But still AC in 0.171s :D even with super many optimizations (like not reading matrix, thus reading when needed; putting x's and y's in one integer and so on) come on :D slower than 2 BFS and even slower than dijkstra : \\ I suspect that I heavily use deque is the main reason. How can I replace deque with some other decent data structure that will let me quickly add and remove items? list<> in STL is dumbly slow for little objects ( dafaq who would have thought ?! ) point is equal. e.g. 3 3 1 1 1 1 111 111 111 answer:1 0 Time limit decreased from 1 second to 0.5 second (it corresponds better to the original TL in 2004). The problem was rejudged. Many old solutions with TLE verdict got AC, while all new solutions working in time from 0.5 to 1 second got TLE. ????????????????????????? n=3 and m=7 This is an example test. Please admins correct it ???????????????????????????
Edited by author 07.10.2005 16:30 У меня программа тоже находит такой путь. И я просто к ответу прибавляю всегда 1 Разве путь не : { I also find the program that way. And I just added to the answer is always 1 Is not the way: } 2 1 3 2 2 3 2 4 1 5 2 6 3 7 А пример: {Simple} 2 2 1 1 1 2 11 00 My program returns: 2 0 Right ? Accepted 0.531 Edited by author 03.01.2012 22:24 when trying to update from (ux,uy) to (vx,vy) i was checking if (vx,vy) was already popped from priority_queue. this got me wa 22 many times. later, just out of frustation i removed the check and let (vx,vy) be updated even after it was once popped. and u know what, mysteriously got AC. of course, there has to be some logical explanation behind that. please explain anyone? Thanks in advance. I followed by your advice, and also suprised! i got wa on 16 please give me test# 16, i don't know where my mistake: size of heap and arrays are enough. I get WA 16 too. =) I don't know your mistake, but my mistake is ... I use "short". Never use "short"! Use "long" or "__int64". =) Max. count of "boots changes" == 500*500 > 32000. It's funny. =) did anyone make the same mistake? what's that? o,i see now. Can you tell me?I got the WA on #16,too.Thank you. Yes, I have the same problem... I had WA#16 because of the size of the queue. Me too... When I tryed to change array size, I've got TLE#16, then I do a small optimization, and I've got TLE#16 again. I think used algo is incorrect. Use dijkstra+heap (easy to write) or double BFS (fast speed). ----------------------------- Sorry for bad English Edited by author 16.03.2007 17:56 I used double BFS and got AC) run_id = 2970301 test: 10 10 1 1 10 10 1211211212 2111221212 2221001111 1112112012 2112102112 2111200222 1112021212 2222011211 2112222222 2012122122 right_answer: 12 1 my program produces answer 14 1 I have written 2 programs and both get WA19 It is very strange, I am already tired to write programs to this problem. first 2*BFS secondar Dijkvasta+Heap both got Wa19 i not understand why. Somebody help me? hi I don't understand in english. hwo can explain this question in Azeri or Turkish or in english but with sample sentenceses you just need to do 2 BFS Edited by author 22.03.2010 02:04 Edited by author 22.03.2010 02:04 Strange.. in 1254 a got AC with 3.656, but in 1325 with 0.625.. maybe you use another method. i used heap, and pop element with less distantion. BTW i suppose, that distantion between clear square and dirty is very big, 200000 is enough. And this path is solution of problem. Edited by author 11.01.2009 18:47 strange.. maybe you have mistake in solution. btw i use int64 in heap, with longint i have WA. I got TL 7 with O(mn) solution... I've solved this problem in 0.9 sec, just 0.1 sec berofe TL. But I see that there could be much more efficient solution. Please mail me at wooden@bk.ru with a cpp source, it's very interesting for me. |
|