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

Best complexity

Послано Furtuna Dan Emanuel 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.

A complexity of our solution cannot be defined strictly, but it is impossible to solve this problem faster than O(N^2) (-)

Послано Dmitry 'Diman_YES' Kovalioff 11 авг 2006 09:28

Re: A complexity of our solution cannot be defined strictly, but it is impossible to solve this problem faster than O(N^2) (-)

Послано maksay 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

Re: ... but it is impossible to solve this problem faster than O(N^2) ...

Послано ძამაანთ [Tbilisi SU] 12 авг 2013 03:58

How do u know it is impossible to find faster than O(N^2)

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