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
The y-intercept optimization problem
Given a set of pairs $(x_1, y_1), ..., (x_k, y_k)$, and a number $a$, how do we find: $min \{ax_i+y_i\} $
This problem can be viewed geometrically as the following.
Consider $(x_1, y_1), ..., (x_k, y_k)$ as points on the plane.
For a given $a$, the line equation of the line passing through $(x_i, y_i)$ with slope $-a$ is:
$y = a(x_i-x) + y_i$
When $x=0$, $y=ax_i + y_i$, thus $ax_i+y_i$ is the y-intercept of the line passing through $(x_i, y_i)$ with slope $-a$
Our problem becomes to find the minimum y-intercept of the lines passing through $(x_i, y_i)$ with slope $-a$
It can be proved (and intuitively) that we only need to keep the convex hulls of $(x_1, y_1), ..., (x_k, y_k)$
The problem of maximizing the y-intercept is similar.
For the minimization problem, we only need to keep the lower hull. It is a set of connected segments with increasing slopes:
If we need to query the minimum intercept of lines with slope $a$, the optimum point $(x_i, y_i)$ is the point such that $a$ lies between the slope of the segment $(i-1), i$ and the segment $i, (i+1)$ (see figure above).
In other words, to query the minimum intercept, we can use binary search on the sequence of slopes.
If we know that the slope being queried is always increasing, we can just go through the set of segments linearly.
To keep track of the lower hull, if the given points are in increasing order of x, we could use a stack and obtain linear time amortized complexity:
A direct application of this problem is the task "Line Country" from NUS Selection Test #2, 2009. Since the slope being queried is not always increasing, we need to use binary search to obtain a O(nlogn) algorithm.
Implementation
This problem can be viewed geometrically as the following.
Consider $(x_1, y_1), ..., (x_k, y_k)$ as points on the plane.
For a given $a$, the line equation of the line passing through $(x_i, y_i)$ with slope $-a$ is:
$y = a(x_i-x) + y_i$
When $x=0$, $y=ax_i + y_i$, thus $ax_i+y_i$ is the y-intercept of the line passing through $(x_i, y_i)$ with slope $-a$
Our problem becomes to find the minimum y-intercept of the lines passing through $(x_i, y_i)$ with slope $-a$
It can be proved (and intuitively) that we only need to keep the convex hulls of $(x_1, y_1), ..., (x_k, y_k)$
The problem of maximizing the y-intercept is similar.
For the minimization problem, we only need to keep the lower hull. It is a set of connected segments with increasing slopes:
If we need to query the minimum intercept of lines with slope $a$, the optimum point $(x_i, y_i)$ is the point such that $a$ lies between the slope of the segment $(i-1), i$ and the segment $i, (i+1)$ (see figure above).
In other words, to query the minimum intercept, we can use binary search on the sequence of slopes.
If we know that the slope being queried is always increasing, we can just go through the set of segments linearly.
To keep track of the lower hull, if the given points are in increasing order of x, we could use a stack and obtain linear time amortized complexity:
for i ← 1 to k do
while (size(s)>2 and (s[top-1], s[top], p[i]) is a right turn
pop(s)
s.push(p[i])
A direct application of this problem is the task "Line Country" from NUS Selection Test #2, 2009. Since the slope being queried is not always increasing, we need to use binary search to obtain a O(nlogn) algorithm.
Implementation
Subscribe to:
Posts (Atom)
