ENG  RUSTimus 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
back to board

Discussion of Problem 1359. Construction

Dmitry 'Diman_YES' Kovalioff Mine is O(N^4) dp (-) [4] // Problem 1359. Construction 23 Mar 2005 18:09
Dmitry 'Diman_YES' Kovalioff Of course... (+) [2] // Problem 1359. Construction 23 Mar 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?
Ilya Rasenstein (Lyceum #40) Re: Of course... (+) [1] // Problem 1359. Construction 4 Sep 2005 11:15
Not parabola, but cycloid! It's variational stuff :)!
Kirin Vladislav Re: Of course... (+) // Problem 1359. Construction 3 Oct 2006 21:16
What is cycloid's formula?