| ENG RUS | Timus Online Judge |
Discussion of Problem 1395. Pascal vs. C++. Version 2Celebrate an easy method // Problem 1395. Pascal vs. C++. Version 2 20 Aug 2021 13:16 (Please forgive me for my poor English.) First,use Hash to record ai Then,enumerate i,j as the first and the second items in the arithmetic sequence.check if 2*a[i]-a[j] exists.If it exists,we stop it immediately because the arithmetic sequence has been found.Otherwise,we find the arithmetic as brute force and mark the longest arithmetic sequence. At last,it's easy to restore the arithmetic sequence. So we can solve it in O(n^2). Edited by author 20.08.2021 13:43 Akhmat Какая ирония. [1] // Problem 1395. Pascal vs. C++. Version 2 22 Sep 2016 12:03 Задачу нельзя сдать на Java, несмотря на условие bsu.mmf.team Re: Какая ирония. // Problem 1395. Pascal vs. C++. Version 2 23 Sep 2016 15:59 :-D Dead lock zer0 Что за тест 22? // Problem 1395. Pascal vs. C++. Version 2 26 Nov 2015 02:03 Дает WA, хоть тресни... Sergey Filipkov Please, enable Java // Problem 1395. Pascal vs. C++. Version 2 10 May 2014 02:54 I strongly dislike being forced to specific languages. Java is too slow to solve the problem? OK. Why ban it? Furtuna Dan Emanuel Best complexity [3] // Problem 1395. Pascal vs. C++. Version 2 10 Aug 2006 22:40 Can you please tell me the time complexity of the official solution? I now have a correct program that works in about 0.7 seconds and a wrong one that got AC in 0.234 sec. Dmitry 'Diman_YES' Kovalioff A complexity of our solution cannot be defined strictly, but it is impossible to solve this problem faster than O(N^2) (-) [2] // Problem 1395. Pascal vs. C++. Version 2 11 Aug 2006 09:28 maksay Re: A complexity of our solution cannot be defined strictly, but it is impossible to solve this problem faster than O(N^2) (-) [1] // Problem 1395. Pascal vs. C++. Version 2 4 Nov 2008 23:59 Complexity of my solution also can not be defined strictly but I believe it is not slower than O(N^2)... Edited by author 05.11.2008 00:01 Edited by author 05.11.2008 00:02 ძამაანთ [Tbilisi SU] Re: ... but it is impossible to solve this problem faster than O(N^2) ... // Problem 1395. Pascal vs. C++. Version 2 12 Aug 2013 03:58 How do u know it is impossible to find faster than O(N^2) Andrew Suhani Test error [1] // Problem 1395. Pascal vs. C++. Version 2 24 Mar 2011 00:52 Can you tell me plz what is test #3? TUSUR_lxn Re: Test error // Problem 1395. Pascal vs. C++. Version 2 30 Aug 2011 15:08 If you have WA it is very easy to generate tests for you solution. There are many solutions that can't be accepted because of memory or time limits. Write one slow, but correct solution, and generate small tests using it until you find test for you solution. r1d1 No subject // Problem 1395. Pascal vs. C++. Version 2 5 Feb 2010 21:02 Edited by author 05.02.2010 22:09 Aydar Bykeev Вопрос для администрации // Problem 1395. Pascal vs. C++. Version 2 26 Sep 2009 00:43 А призы то еще есть? ;) maksay To Admins(+) [1] // Problem 1395. Pascal vs. C++. Version 2 5 Nov 2008 20:47 I know this question is not a shy one, but I read something about special awards for the fastest solution. Was that information true?=) sorry if my english was not good enough svr Re: To Admins(+) // Problem 1395. Pascal vs. C++. Version 2 5 Nov 2008 23:25 I think that this question not to admins but to forgotten authorhs of this initiative. SerailHydra Can someone who got AC send your solution to me please? // Problem 1395. Pascal vs. C++. Version 2 8 Mar 2008 13:59 My E-mail Address: serailhydra@sina.com THX a lot! Dmitry 'Diman_YES' Kovalioff One more rejudge is finished (+) // Problem 1395. Pascal vs. C++. Version 2 17 Aug 2006 12:23 New tests were added, and cheating solutions failed to pass them. Anyway Furtuna Dan Emanuel got AC with his Pascal solution within 0.578 sec. We have almost nothing to say, because we are just so impressed with it. It is almost impossible to solve this problem on Pascal, but Furtuna Dan Emanuel's solution made it real. Our congratulations! Furtuna Dan Emanuel Test case 34 WA [5] // Problem 1395. Pascal vs. C++. Version 2 10 Aug 2006 12:37 Can someone tell me why this test is special? If I got a TLE I would have known that my program is slow and optimised but now, I don't know what's wrong. Strange that the same program passes the first version of the problem. Furtuna Dan Emanuel Re: Test case 34 WA [4] // Problem 1395. Pascal vs. C++. Version 2 10 Aug 2006 12:53 Found the bug in my program. Sorry for the post. Dmitry 'Diman_YES' Kovalioff Good luck solving this problem (+) [3] // Problem 1395. Pascal vs. C++. Version 2 10 Aug 2006 15:29 It is almost impossible to solve it on Pascal. Author's solution passes the TL, but it is incredibly optimized... Furtuna Dan Emanuel Re: Good luck solving this problem (+) [2] // Problem 1395. Pascal vs. C++. Version 2 10 Aug 2006 16:22 AC at last but with a little cheat. Dmitry 'Diman_YES' Kovalioff Congratulations, your solution is extremely fast. But we will see it and maybe add new tests (-) [1] // Problem 1395. Pascal vs. C++. Version 2 10 Aug 2006 16:26 Furtuna Dan Emanuel Re: Congratulations, your solution is extremely fast. But we will see it and maybe add new tests (-) // Problem 1395. Pascal vs. C++. Version 2 10 Aug 2006 16:31 I'm sure it won't pass all the new tests after you look at it more closely. Gotta optimize some more. Yevgeniy What's wrong ? [1] // Problem 1395. Pascal vs. C++. Version 2 4 Jul 2006 18:00 Who can give me test 21? I don't know, what wrong. IN MY TEST MY PROGRAM solved it not more 0.902 sec, and in test 21 I got TL. Thanks!!! (sorry for my bed English) Dmitry 'Diman_YES' Kovalioff It is the first test with N=10000 (-) // Problem 1395. Pascal vs. C++. Version 2 4 Jul 2006 18:33 Dmitry 'Diman_YES' Kovalioff One more rejudge is finished (+) // Problem 1395. Pascal vs. C++. Version 2 27 May 2006 10:33 Some new-class tests were added, and Rizvanov++ de xXx's solutions failed to pass them. Anyway these solutions are quite effective, more over, we were surprised to see such approach. We believe Rizvanov++ de xXx will be able to find some more optimizations and pass the TL. We are sorry for the rejudges, but we will continue to support this problem, to add new tests and to rejudge it - until true solutions only could pass the TL and get AC. Dmitry 'Diman_YES' Kovalioff One more rejudge is finished (+) // Problem 1395. Pascal vs. C++. Version 2 22 May 2006 00:40 Now the time limit is 1.0 sec. We think it is more than enough to solve this problem since some new optimizations were found, so now we have a C++ solution that works within 0.25 sec. We have also both Pascal and Java solutions that fit the time limit with quite large reserve. P.S. If someone solves this problem we will think about 0.75 sec. time limit ;) Edited by author 22.05.2006 00:43 {AESC USU} UdH-WiNGeR AC again [1] // Problem 1395. Pascal vs. C++. Version 2 19 May 2006 14:27 but slower :( Dmitry 'Diman_YES' Kovalioff Congratulations! Your skills impress us deeply (+) // Problem 1395. Pascal vs. C++. Version 2 19 May 2006 15:31 But there is one thing you should know. The problem is still under construction. Yesterday we found a new class of tests (there are already about 10 classed of tests in the test set) and now are thinking about adding new tests and changing the TL. We are also improving our solutions constantly to reach perfection. So one more rejudge is coming ;) P.S. Could you send your solution to dimanyes@mail.ru for us to investigate it? Maybe you even invented some unknown optimization... Dmitry 'Diman_YES' Kovalioff New tests were added and a rejudge has been just finished (+) // Problem 1395. Pascal vs. C++. Version 2 18 May 2006 02:19 {AESC USU} UdH-WiNGeR's and XYZ's heuristics-based solutions failed to pass the tests. Now the following programmers have AC: - Dmitry 'Diman_YES' Kovalioff - Ilya Grebnov[Ivanovo SPU] - Kit But {AESC USU} UdH-WiNGeR's solution seems to be rather good, so after some further optimization it may fit the TL and get AC. Good luck! Vladimir Yakovlev (USU) New problem 1395 "Pascal vs. C++. Version 2" has been added to problem set archive! Thanks to authors! // Problem 1395. Pascal vs. C++. Version 2 28 Apr 2006 08:04
|