Обсуждение @ 1135. Новобранцы @ Timus Online Judge

Solution O(n^2) normal is?

Послано VyatkaSU#2: Korchemkina, Prozorova, Sukhih 25 авг 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?

Послано [MSU Detritus] freopen 25 авг 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?

Послано VyatkaSU#2: Korchemkina, Prozorova, Sukhih 25 авг 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?

Послано [MSU Detritus] freopen 25 авг 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?

Послано Vedernikoff Sergey (HSE: АОП) 26 авг 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?

Послано VyatkaSU#2: Korchemkina, Prozorova, Sukhih 26 авг 2010 13:22

Where I can read about algorithm or idea?

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

Послано Vedernikoff Sergey (HSE: АОП) 26 авг 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!

Обсуждение задачи 1135. Новобранцы