Обсуждение @ 1130. Никифор на прогулке @ Timus Online Judge

Timus Online Judge

Online Judge	Задачи	Авторы	Соревнования
О системе Часто задаваемые вопросы Новости сайта Форум Ссылки	Архив задач Отправить на проверку Состояние проверки Руководство	Регистрация Исправить данные Рейтинг авторов	Текущее соревнование Расписание Прошедшие соревнования Правила

вернуться в форум

Обсуждение задачи 1130. Никифор на прогулке

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

Послано AlMag 15 май 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? (+)

Послано AlMag 16 май 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? (+)

Послано Alexander Kouprin 16 май 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? (+)

Послано AlMag 17 май 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? (+)

Послано Alexander Kouprin 17 май 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? (+)

Послано AlMag 17 май 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? (+)

Послано Alexander Kouprin 17 май 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? (+)

Послано AlMag 18 май 2007 15:36

No result... =(

Not possible

Послано jerzydabczak 23 июл 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)

Послано Tbilsu_Irakli Khomeriki 28 сен 2007 14:18