Discussion @ 1130. Nikifor's Walk @ Timus Online Judge

Timus Online Judge

Online Judge	Problems	Authors	Online contests
About Online Judge Frequently asked questions Site news Webboard Links	Problem set Submit solution Judge status Guide	Register Update your info Authors ranklist	Current contest Scheduled contests Past contests Rules

Discussion of Problem 1130. Nikifor's Walk

I've read about O(N^2)... (+)

Posted by AlMag 15 May 2007 20:00

[ There was a stupid question :) ]

I have TLE#5. Why? My program looks like

...
Input();
while (abs(x)>l || abs(y)>l)
{
for(i=0;i<n;++i)
   if (...)
   {
    ...
   }
}
Output();

And that's all!

Edited by author 15.05.2007 20:21

Edited by author 15.05.2007 20:32

Have no ideas about TLE#12. Can U tell me? (+)

Posted by AlMag 16 May 2007 20:51

subj...
Here's my prog.

[code deleted]

Edited by author 17.05.2007 19:48

Re: Have no ideas about TLE#12. Can U tell me? (+)

Posted by Alexander Kouprin 16 May 2007 22:36

Read my message
http://acm.timus.ru/forum/thread.aspx?space=1&num=1130&id=15382&upd=633147869028442500

It's very useful hint. :)
But it's REALLY works.

Re: Have no ideas about TLE#12. Can U tell me? (+)

Posted by AlMag 17 May 2007 00:01

Thank U, but I have just seen Nazarov Denis's subject. XueMao has the same algo as mine. But His AC vs My TLE#12.
I want to understand my mistake...

Re: Have no ideas about TLE#12. Can U tell me? (+)

Posted by Alexander Kouprin 17 May 2007 04:03

Ha-ha!
You can try to solve it from O(n^2) but I think you never get AC if you using this algorithm!
XueMao have TLE#12 too! http://acm.timus.ru/author.aspx?id=16378
Thanks a lot to Sandro's rejudge!!! :))))))))

P.S. It can be solved more faster like O(n).

Re: Have no ideas about TLE#12. Can U tell me? (+)

Posted by AlMag 17 May 2007 19:30

I think I'll try to find O(N) algo than to write O(2^n)
solution. In this case I'd learn nothing.

Re: Have no ideas about TLE#12. Can U tell me? (+)

Posted by Alexander Kouprin 17 May 2007 21:59

Try to sort from any parameters:
x+y;
abs(x)+abs(y);
abs(x)-abs(y) - it's strange sort, but it helped me;

Try to move not from first to last, but from first and last at the same time.

Use the SHAMANISM! :)

Re: Have no ideas about TLE#12. Can U tell me? (+)

Posted by AlMag 18 May 2007 15:36

No result... =(

Not possible

Posted by jerzydabczak 23 Jul 2007 02:46

Edited by author 11.02.2008 22:30

At least I got AC :) , I solved it by DP in time O(N*L)

Posted by Tbilsu_Irakli Khomeriki 28 Sep 2007 14:18