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

Обсуждение задачи 1359. Стройка

Hello everyboby! I found solution in O(n^4), what about others? (-)
Послано Victor Barinov (TNU) 23 мар 2005 17:40
Mine is O(N^4) dp (-)
Послано Dmitry 'Diman_YES' Kovalioff 23 мар 2005 18:09
But it is very slow! Is it possible to accelerate it without precalculation? (-)
Послано Victor Barinov (TNU) 23 мар 2005 20:23
Of course... (+)
Послано Dmitry 'Diman_YES' Kovalioff 23 мар 2005 20:46
The fastest solution is precalc (as usual :] ), but you can make your solution very fast without it. It is clear that there is some physical dependence in this problem - the line of optimal movement is some function (a parabola, I presume). So you can look for several nearest points with integer coordinates and use dp only for them. But it is much more difficult and unsafe, isn't it?
Re: Of course... (+)
Послано Ilya Rasenstein (Lyceum #40) 4 сен 2005 11:15
Not parabola, but cycloid! It's variational stuff :)!
Re: Of course... (+)
Послано Kirin Vladislav 3 окт 2006 21:16
What is cycloid's formula?