Discussion @ 1395. Pascal vs. C++. Version 2 @ Timus Online Judge

Best complexity

Posted by Furtuna Dan Emanuel 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.

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

Posted by Dmitry 'Diman_YES' Kovalioff 11 Aug 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) (-)

Posted by maksay 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

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

Posted by ძამაანთ [Tbilisi SU] 12 Aug 2013 03:58

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

Discussion of Problem 1395. Pascal vs. C++. Version 2