| ENG RUS | Timus Online Judge |
Обсуждение задачи 1395. Pascal против C++. Версия 2Celebrate an easy method // Задача 1395. Pascal против C++. Версия 2 20 авг 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] // Задача 1395. Pascal против C++. Версия 2 22 сен 2016 12:03 Задачу нельзя сдать на Java, несмотря на условие bsu.mmf.team Re: Какая ирония. // Задача 1395. Pascal против C++. Версия 2 23 сен 2016 15:59 :-D Dead lock zer0 Что за тест 22? // Задача 1395. Pascal против C++. Версия 2 26 ноя 2015 02:03 Дает WA, хоть тресни... Sergey Filipkov Please, enable Java // Задача 1395. Pascal против C++. Версия 2 10 май 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] // Задача 1395. Pascal против C++. Версия 2 10 авг 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] // Задача 1395. Pascal против C++. Версия 2 11 авг 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] // Задача 1395. Pascal против C++. Версия 2 4 ноя 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) ... // Задача 1395. Pascal против C++. Версия 2 12 авг 2013 03:58 How do u know it is impossible to find faster than O(N^2) Andrew Suhani Test error [1] // Задача 1395. Pascal против C++. Версия 2 24 мар 2011 00:52 Can you tell me plz what is test #3? TUSUR_lxn Re: Test error // Задача 1395. Pascal против C++. Версия 2 30 авг 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 // Задача 1395. Pascal против C++. Версия 2 5 фев 2010 21:02 Edited by author 05.02.2010 22:09 Aydar Bykeev Вопрос для администрации // Задача 1395. Pascal против C++. Версия 2 26 сен 2009 00:43 А призы то еще есть? ;) maksay To Admins(+) [1] // Задача 1395. Pascal против C++. Версия 2 5 ноя 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(+) // Задача 1395. Pascal против C++. Версия 2 5 ноя 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? // Задача 1395. Pascal против C++. Версия 2 8 мар 2008 13:59 My E-mail Address: serailhydra@sina.com THX a lot! Dmitry 'Diman_YES' Kovalioff One more rejudge is finished (+) // Задача 1395. Pascal против C++. Версия 2 17 авг 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] // Задача 1395. Pascal против C++. Версия 2 10 авг 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] // Задача 1395. Pascal против C++. Версия 2 10 авг 2006 12:53 Found the bug in my program. Sorry for the post. Dmitry 'Diman_YES' Kovalioff Good luck solving this problem (+) [3] // Задача 1395. Pascal против C++. Версия 2 10 авг 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] // Задача 1395. Pascal против C++. Версия 2 10 авг 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] // Задача 1395. Pascal против C++. Версия 2 10 авг 2006 16:26 Furtuna Dan Emanuel Re: Congratulations, your solution is extremely fast. But we will see it and maybe add new tests (-) // Задача 1395. Pascal против C++. Версия 2 10 авг 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] // Задача 1395. Pascal против C++. Версия 2 4 июл 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 (-) // Задача 1395. Pascal против C++. Версия 2 4 июл 2006 18:33 Dmitry 'Diman_YES' Kovalioff One more rejudge is finished (+) // Задача 1395. Pascal против C++. Версия 2 27 май 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 (+) // Задача 1395. Pascal против C++. Версия 2 22 май 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] // Задача 1395. Pascal против C++. Версия 2 19 май 2006 14:27 but slower :( Dmitry 'Diman_YES' Kovalioff Congratulations! Your skills impress us deeply (+) // Задача 1395. Pascal против C++. Версия 2 19 май 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 (+) // Задача 1395. Pascal против C++. Версия 2 18 май 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! // Задача 1395. Pascal против C++. Версия 2 28 апр 2006 08:04
|