Обсуждение @ 1395. Pascal против C++. Версия 2 @ Timus Online Judge

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)

Обсуждение задачи 1395. Pascal против C++. Версия 2