| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
| an easy method | Celebrate | 1395. Pascal против C++. Версия 2 | 20 авг 2021 13:16 | 1 |
(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 | 1395. Pascal против C++. Версия 2 | 23 сен 2016 15:59 | 2 |
Задачу нельзя сдать на Java, несмотря на условие |
| Что за тест 22? | zer0 | 1395. Pascal против C++. Версия 2 | 26 ноя 2015 02:03 | 1 |
|
| Please, enable Java | Sergey Filipkov | 1395. Pascal против C++. Версия 2 | 10 май 2014 02:54 | 1 |
I strongly dislike being forced to specific languages. Java is too slow to solve the problem? OK. Why ban it? |
| Best complexity | Furtuna Dan Emanuel | 1395. Pascal против C++. Версия 2 | 12 авг 2013 03:58 | 4 |
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. 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 How do u know it is impossible to find faster than O(N^2) |
| Test error | Andrew Suhani | 1395. Pascal против C++. Версия 2 | 30 авг 2011 15:08 | 2 |
Can you tell me plz what is test #3? 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. |
| No subject | r1d1 | 1395. Pascal против C++. Версия 2 | 5 фев 2010 21:02 | 1 |
Edited by author 05.02.2010 22:09 |
| Вопрос для администрации | Aydar Bykeev | 1395. Pascal против C++. Версия 2 | 26 сен 2009 00:43 | 1 |
|
| To Admins(+) | maksay | 1395. Pascal против C++. Версия 2 | 5 ноя 2008 23:25 | 2 |
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 I think that this question not to admins but to forgotten
authorhs of this initiative. |
| Can someone who got AC send your solution to me please? | SerailHydra | 1395. Pascal против C++. Версия 2 | 8 мар 2008 13:59 | 1 |
My E-mail Address:
serailhydra@sina.com
THX a lot! |
| One more rejudge is finished (+) | Dmitry 'Diman_YES' Kovalioff | 1395. Pascal против C++. Версия 2 | 17 авг 2006 12:23 | 1 |
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! |
| Test case 34 WA | Furtuna Dan Emanuel | 1395. Pascal против C++. Версия 2 | 10 авг 2006 16:31 | 6 |
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. Found the bug in my program. Sorry for the post. It is almost impossible to solve it on Pascal. Author's solution passes the TL, but it is incredibly optimized... AC at last but with a little cheat. I'm sure it won't pass all the new tests after you look at it more closely. Gotta optimize some more. |
| What's wrong ? | Yevgeniy | 1395. Pascal против C++. Версия 2 | 4 июл 2006 18:33 | 2 |
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) |
| One more rejudge is finished (+) | Dmitry 'Diman_YES' Kovalioff | 1395. Pascal против C++. Версия 2 | 27 май 2006 10:33 | 1 |
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. |
| One more rejudge is finished (+) | Dmitry 'Diman_YES' Kovalioff | 1395. Pascal против C++. Версия 2 | 22 май 2006 00:40 | 1 |
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 |
| AC again | {AESC USU} UdH-WiNGeR | 1395. Pascal против C++. Версия 2 | 19 май 2006 15:31 | 2 |
AC again {AESC USU} UdH-WiNGeR 19 май 2006 14:27 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... |
| New tests were added and a rejudge has been just finished (+) | Dmitry 'Diman_YES' Kovalioff | 1395. Pascal против C++. Версия 2 | 18 май 2006 02:19 | 1 |
{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! |
| New problem 1395 "Pascal vs. C++. Version 2" has been added to problem set archive! Thanks to authors! | Vladimir Yakovlev (USU) | 1395. Pascal против C++. Версия 2 | 28 апр 2006 08:04 | 1 |
|
