| ENG RUS | Timus Online Judge |
Discussion of Problem 1325. DirtPage 2 Mortus WA 14 // Problem 1325. Dirt 24 Jul 2023 00:15 THIS TEST 6 5 1 3 6 3 11112 22221 11112 22212 21112 22222 ANS:7 1 andreyDagger WA17 // Problem 1325. Dirt 30 Jan 2022 13:42 I changed my INF to 1e18 and got AC Practician Python got TLE16 on O(m*n) solution, C++ got AC even with Dijkstra. Please add PyPy! // Problem 1325. Dirt 4 Oct 2016 14:32 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 alexge50 WA7 [1] // Problem 1325. Dirt 21 Nov 2015 20:59 Can anybody that had WA7 give me some hints? Thanks Myrcella Re: WA7 // Problem 1325. Dirt 18 Aug 2018 15:24 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. Ta'al WA 25! [1] // Problem 1325. Dirt 20 May 2014 21:44 Gimme some data, please Jane Soboleva (SumNU) Re: WA 25! // Problem 1325. Dirt 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... ძამაანთ [Tbilisi SU] I solved it in one BFS // Problem 1325. Dirt 20 Apr 2014 04:02 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 ?! ) alp hint for WA 2 // Problem 1325. Dirt 4 Nov 2013 22:00 point is equal. e.g. 3 3 1 1 1 1 111 111 111 answer:1 0 Sandro (USU) Problem 1325 "Dirt". Time limit now is 0.5 sec. // Problem 1325. Dirt 2 Oct 2012 17:27 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. Radi Muhammad Reza wa 22 and then mysteriously AC: don't know why? [1] // Problem 1325. Dirt 14 Aug 2011 15:11 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. shad Re: wa 22 and then mysteriously AC: don't know why? // Problem 1325. Dirt 2 Jan 2012 22:16 I followed by your advice, and also suprised! Teacher30 New tests for this problem. [1] // Problem 1325. Dirt 25 Mar 2010 16:08 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 Sandro (USU) Your test was added (-) // Problem 1325. Dirt 19 Apr 2010 12:09 Balan Catalin hint if you get WA 8 [1] // Problem 1325. Dirt 5 Oct 2009 16:04 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. !!!! Hans Tocsin Re: hint if you get WA 8 // Problem 1325. Dirt 27 Jul 2019 11:06 Thank u so much! How should I forget this! Baurzhan wa 16 give me test please [1] // Problem 1325. Dirt 10 Aug 2009 22:20 i got wa on 16 please give me test# 16, i don't know where my mistake: size of heap and arrays are enough. IgorKoval(from Pskov) Re: wa 16 give me test please // Problem 1325. Dirt 21 Dec 2011 18:16 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. =) Page 1 Yurchuk Maxim, Rybinsk, Liceum #2 You can solve this problem using a solve of 1254 problem, they look similar (-) [5] // Problem 1325. Dirt 7 Jan 2009 23:02 OpenGL I got AC in 1254 with 0.265 but on this problem I got TLE 21 [4] // Problem 1325. Dirt 11 Jan 2009 15:16 Yurchuk Maxim, Rybinsk, Liceum #2 Re: I got AC in 1254 with 0.265 but on this problem I got TLE 21 [3] // Problem 1325. Dirt 11 Jan 2009 18:43 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 OpenGL No, I used the same method [2] // Problem 1325. Dirt 11 Jan 2009 19:02 Yurchuk Maxim, Rybinsk, Liceum #2 Re: No, I used the same method [1] // Problem 1325. Dirt 12 Jan 2009 10:37 strange.. maybe you have mistake in solution. btw i use int64 in heap, with longint i have WA. OpenGL Most likely. I got WA 5 and WA 19 now :) // Problem 1325. Dirt 13 Jan 2009 13:53 theNobody { Krasnoyarsk STU } Please give me a faster solution // Problem 1325. Dirt 16 Aug 2008 20:03 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. Pavlov Sergey Help me. WA 12. // Problem 1325. Dirt 4 Jan 2008 17:44 Give me tests please. Zeva [USU] WAwaWA 25 // Problem 1325. Dirt 18 Apr 2006 23:42 Help, me. Pleassse... ....... Now I AC 0.203s, but 4422 KB This test help me: 5 7 1 1 3 5 1011111 1211101 1222221 1020101 1111110 5 1 Edited by author 19.04.2006 01:21 Edited by author 19.04.2006 21:02 boaz wa on 16?what's wrong? [7] // Problem 1325. Dirt 7 Apr 2006 11:52 did anyone make the same mistake? what's that? boaz Re: wa on 16?what's wrong? [6] // Problem 1325. Dirt 7 Apr 2006 17:12 o,i see now. edison Re: wa on 16?what's wrong? [5] // Problem 1325. Dirt 28 May 2006 13:44 Can you tell me?I got the WA on #16,too.Thank you. Samsonov Alex [USU] Re: wa on 16?what's wrong? [4] // Problem 1325. Dirt 28 Jul 2006 22:08 Yes, I have the same problem... AlexF [USTU] Re: wa on 16?what's wrong? [3] // Problem 1325. Dirt 1 Feb 2007 13:26 I had WA#16 because of the size of the queue. Izual Re: wa on 16?what's wrong? [2] // Problem 1325. Dirt 16 Mar 2007 17:55 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 AlexF [USTU] Re: wa on 16?what's wrong? [1] // Problem 1325. Dirt 16 Mar 2007 19:33 I used double BFS and got AC) Roman Furko Re: wa on 16?what's wrong? // Problem 1325. Dirt 20 Dec 2011 01:02 what mean double BFS? Liu Lanzheng WA on 20,give me some data // Problem 1325. Dirt 21 Oct 2005 19:16 ACM.Anatoliy 'Tolyan_NO' Tolstobroff need help. [3] // Problem 1325. Dirt 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? Lotl_kamran Re: need help. [2] // Problem 1325. Dirt 26 Jan 2006 16:24 hi I don't understand in english. hwo can explain this question in Azeri or Turkish or in english but with sample sentenceses botl_ayhan in Azeri or Turkish?!!! // Problem 1325. Dirt 26 Jan 2006 17:23 its funny. Sania Re: need help. // Problem 1325. Dirt 21 Mar 2010 21:44 you just need to do 2 BFS Edited by author 22.03.2010 02:04 Edited by author 22.03.2010 02:04 nr WA 1 ?????? [1] // Problem 1325. Dirt 7 Oct 2005 16:26 ????????????????????????? n=3 and m=7 This is an example test. Please admins correct it ??????????????????????????? Edited by author 07.10.2005 16:30 uu_Innk Re: WA 1 ?????? Accepted 0.531 // Problem 1325. Dirt 3 Jan 2012 22:06 У меня программа тоже находит такой путь. И я просто к ответу прибавляю всегда 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
|