This task is an application of the y-intercept optimization problem in the previous post.
From an initial $O(n^3)$ DP algorithm, we could speed up to $O(n^2logn)$, which still got TLE on SPOJ.
Since for each hull, all the query slopes are decreasing, we could speed up the algorithm further to $O(n^2)$.
See the USACO analysis for more details.
Sunday, November 1, 2009
Subscribe to:
Post Comments (Atom)
hai buddy if you can post on this it will be helpful.
ReplyDeletehttp://www.spoj.pl/status/DIVREL,blackdiamond/
i am not getting how to implement kong's theorem
(Duc) I don't know about Kong's theorem. Could you post a link to it? I used bipartite matching for this problem.
ReplyDelete