Discussion @ 1135. Recruits @ Timus Online Judge

Solution O(n^2) normal is?

Posted by VyatkaSU#2: Korchemkina, Prozorova, Sukhih 25 Aug 2010 12:32

I passed for G (N ^ 2). Is this normal? What is the asymptotic behavior of a normal solution?

Re: Solution O(n^2) normal is?

Posted by [MSU Detritus] freopen 25 Aug 2010 15:22

Make program, which will find solution for test ><<<<<<<<...(29999 symbols '<'), and send it on timus. If it fails with WA1, then it's normal. If it fails with TL1, then it's weak testing.

Sorry for bad english.

Re: Solution O(n^2) normal is?

Posted by VyatkaSU#2: Korchemkina, Prozorova, Sukhih 25 Aug 2010 19:20

Power of timus server not equal power of contest server. TL on thimus is not indicator.

Re: Solution O(n^2) normal is?

Posted by [MSU Detritus] freopen 25 Aug 2010 20:20

If you got TL then tests on this task should be harder and such solutions must fail.

Re: Solution O(n^2) normal is?

Posted by Vedernikoff Sergey (HSE: АОП) 26 Aug 2010 01:26

Better try test >>>...(15000 times)..>>><<<...(15000 times)..<<< If your solution passes it in time - then limitations of the problem are already too weak for modern computation facilities =( If it gets TL - then timus tests are just weak.
Anyway, there exists correct O(N) algo...

Re: Solution O(n^2) normal is?

Posted by VyatkaSU#2: Korchemkina, Prozorova, Sukhih 26 Aug 2010 13:22

Where I can read about algorithm or idea?

Re: Solution O(n^2) normal is?

Posted by Vedernikoff Sergey (HSE: АОП) 26 Aug 2010 14:39

That's the main idea of the problem - not to read about an algorithm or idea but to turn your brains on and create it. This is possible (and even not difficult), try it!

Discussion of Problem 1135. Recruits