Show all threads Hide all threads Show all messages Hide all messages |
WA 14 | Mortus | 1325. Dirt | 24 Jul 2023 00:15 | 1 |
WA 14 Mortus 24 Jul 2023 00:15 THIS TEST 6 5 1 3 6 3 11112 22221 11112 22212 21112 22222 ANS:7 1 |
WA17 | andreyDagger | 1325. Dirt | 30 Jan 2022 13:42 | 1 |
WA17 andreyDagger 30 Jan 2022 13:42 I changed my INF to 1e18 and got AC |
hint if you get WA 8 | Balan Catalin | 1325. Dirt | 27 Jul 2019 11:06 | 2 |
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! |
WA7 | alexge50 | 1325. Dirt | 18 Aug 2018 15:24 | 2 |
WA7 alexge50 21 Nov 2015 20:59 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. |
How to solve this problem?I used Djkstra,but I've got TLE. | November Rain | 1325. Dirt | 16 Aug 2017 01:32 | 8 |
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. |
Python got TLE16 on O(m*n) solution, C++ got AC even with Dijkstra. Please add PyPy! | Practician | 1325. Dirt | 4 Oct 2016 14:32 | 1 |
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 |
WA 25! | Ta'al | 1325. Dirt | 12 Apr 2016 09:07 | 2 |
WA 25! Ta'al 20 May 2014 21:44 Re: WA 25! Jane Soboleva (SumNU) 12 Apr 2016 09:07 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... |
The problem was impossible to accept!!! | 黄源河 | 1325. Dirt | 15 May 2014 13:37 | 23 |
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 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. |
I solved it in one BFS | ძამაანთ [Tbilisi SU] | 1325. Dirt | 20 Apr 2014 04:02 | 1 |
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 ?! ) |
hint for WA 2 | alp | 1325. Dirt | 4 Nov 2013 22:00 | 1 |
point is equal. e.g. 3 3 1 1 1 1 111 111 111 answer:1 0 |
Problem 1325 "Dirt". Time limit now is 0.5 sec. | Sandro (USU) | 1325. Dirt | 2 Oct 2012 17:27 | 1 |
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. |
WA 1 ?????? | nr | 1325. Dirt | 3 Jan 2012 22:06 | 2 |
????????????????????????? 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 |
wa 22 and then mysteriously AC: don't know why? | Radi Muhammad Reza | 1325. Dirt | 2 Jan 2012 22:16 | 2 |
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! |
wa 16 give me test please | Baurzhan | 1325. Dirt | 21 Dec 2011 18:16 | 2 |
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. =) |
wa on 16?what's wrong? | boaz | 1325. Dirt | 20 Dec 2011 01:02 | 8 |
did anyone make the same mistake? what's that? 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) |
New tests for this problem. | Teacher30 | 1325. Dirt | 19 Apr 2010 12:09 | 2 |
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 |
need help. | ACM.Anatoliy 'Tolyan_NO' Tolstobroff | 1325. Dirt | 21 Mar 2010 21:44 | 4 |
need help. ACM.Anatoliy 'Tolyan_NO' Tolstobroff 21 Oct 2005 16:10 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 |
You can solve this problem using a solve of 1254 problem, they look similar (-) | Yurchuk Maxim, Rybinsk, Liceum #2 | 1325. Dirt | 13 Jan 2009 13:53 | 6 |
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 WA on test7,who can give me any test datas? | Failed Peter | 1325. Dirt | 21 Aug 2008 03:51 | 2 |
I got TL 7 with O(mn) solution... |
Please give me a faster solution | theNobody { Krasnoyarsk STU } | 1325. Dirt | 16 Aug 2008 20:03 | 1 |
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. |