Editorial for IOI '16 P6 - Aliens - DMOJ: Modern Online Judge

Editorial for IOI '16 P6 - Aliens

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Subtask 1. $k = n$ ~k = n~ means that you can use a photo for each point of interest: the minimum photo containing point $(r_i, c_i)$ ~(r_i, c_i)~ is the square containing points $(r_i, r_i)$ ~(r_i, r_i)~ and $(c_i, c_i)$ ~(c_i, c_i)~. Constraints in this subtask were small enough to iterate over all cells in that square and mark them as photographed. After processing all photos, calculate and return the number of cells which have been marked at least once.

Subtask 2 required the participants to come up with a dynamic programming solution. Some important observations:

If a photo covers two points $(x, x)$ ~(x, x)~ and $(y, y)$ ~(y, y)~, then it also covers all points between them.
Each photo's boundary must be equal to some $r_i$ ~r_i~.

Now we can treat this problem as a dynamic programming problem: cover $n$ ~n~ points on a line using $k$ ~k~ segments such that the sum of squares of their lengths is as small as possible. Start with preprocessing the input data: sort all points by $r_i$ ~r_i~ and remove duplicates. Notice that each photo should cover some contiguous set of points.

Let $f_{i,j}$ ~f_{i,j}~ be the minimum cost to cover the first $i$ ~i~ points with at most $j$ ~j~ photos.
$f_{0,j} = 0$ ~f_{0,j} = 0~ for all $0 \le j \le k$ ~0 \le j \le k~.
$f_{i,j} = \min_{t<i} f_{t,j-1}+(r_{i-1}-l_t+1)^2$ .
$f_{n,k}$ ~f_{n,k}~ contains the answer.
$\mathcal O(nk)$ ~\mathcal O(nk)~ states, calculating transitions from each state takes $\mathcal O(n)$ ~\mathcal O(n)~ time.
Overall running time: $\mathcal O(n^2 k)$ ~\mathcal O(n^2 k)~.

Subtask 3 dropped the $r_i = c_i$ ~r_i = c_i~ restriction. We'll describe a similar DP solution for this subtask. It's possible to prove that a photo containing points $(x, x)$ ~(x, x)~ and $(y, y)$ ~(y, y)~ covers point $(r, c)$ ~(r, c)~ if and only if segment $[\min(r, c), \max(r, c)]$ ~[\min(r, c), \max(r, c)]~ is fully contained in segment $[x, y]$ ~[x, y]~ ( $x \le y$ ~x \le y~). So if we consider segments $[\min(r_i, c_i), \max(r_i, c_i)]$ ~[\min(r_i, c_i), \max(r_i, c_i)]~ instead of points $(r_i, c_i)$ ~(r_i, c_i)~, the problem is reduced to the following: cover all $n$ ~n~ segments with $k$ ~k~ larger segments such that their total area (considering intersections) is minimized.

If segment $S_i$ ~S_i~ is included in some other segment $S_j$ ~S_j~, then any photo that covers $S_j$ ~S_j~ also covers $S_i$ ~S_i~, so we can safely remove $S_i$ ~S_i~. Removing all such segments can be done in $\mathcal O(n \log n)$ ~\mathcal O(n \log n)~ time:

First, sort all the segments in order of increasing left endpoint.
In case of equality, sort them in order of decreasing right endpoint.
Iterate over all segments in this order.
If the current segment is included in the last non-removed segment, remove it. Otherwise keep it.

Now, since all left endpoints are increasing and no segment is included in the other, then for all $i < j$ ~i < j~: $r_i < r_j$ ~r_i < r_j~ and $c_i < c_j$ ~c_i < c_j~. Observations and definition of $f_{i,j}$ ~f_{i,j}~ are almost identical to the previous solution:

$f_{0,j} = 0$ ~f_{0,j} = 0~ for all $0 \le j \le k$ ~0 \le j \le k~
$f_{i,j} = \min_{t<i} f_{t,j-1} + (r_{i-1}-l_t+1)^2 - \max(0, r_{t-1}-l_t+1)^2$ (1)
Last term in this formula accounts for the intersection of segments $t-1$ ~t-1~ and $t$ ~t~ ( $t > 0$ ~t > 0~).
$f_{n,k}$ ~f_{n,k}~ contains the answer.
Overall running time: $\mathcal O(n^2 k)$ ~\mathcal O(n^2 k)~.

Subtasks 4 and 5. Here you were required to come up with an optimization of the DP solution described above. Subtask 4 allowed $\mathcal O(n^2)$ ~\mathcal O(n^2)~ solutions. One possible solution uses Knuth's optimization.

Define $A_{i,j}$ ~A_{i,j}~ as the optimal $t$ ~t~ in (1) and $cost(t, i) = (r_{i-1}-l_t+1)^2 - \max(0, r_{t-1}-l_t+1)^2$ .

Lemma: $A_{i,j-1} \le A_{i,j} \le A_{i+1,j}$ ~A_{i,j-1} \le A_{i,j} \le A_{i+1,j}~

This allows us to prune the search space on each step, reducing the running time to $\mathcal O(n^2)$ ~\mathcal O(n^2)~. If you calculate $f_{i,j}$ ~f_{i,j}~ in order of increasing $j$ ~j~ and decreasing $i$ ~i~, then at the moment of calculating $f_{i,j}$ ~f_{i,j}~, values of $A_{i,j-1}$ ~A_{i,j-1}~ and $A_{i+1,j}$ ~A_{i+1,j}~ are already known, so you can only check $t \in [A_{i,j-1}, A_{i+1,j}]$ ~t \in [A_{i,j-1}, A_{i+1,j}]~.

It can be rather difficult to prove the correctness formally, but it's easy to be convinced this is true. A possible strategy for the competition would be to implement this solution without a formal proof, then test the hypothesis on smaller inputs using the solution for subtask 3. It is known that this optimization results in $\mathcal O(n^2)$ ~\mathcal O(n^2)~ running time. Also, don't forget about 64 bit integers.

Subtask 5 required a different kind of optimization, running in $\mathcal O(nk)$ ~\mathcal O(nk)~ or $\mathcal O(nk \log n)$ ~\mathcal O(nk \log n)~ time. Implementing any of the two following optimizations was enough to pass all the tests from this subgroup.

Divide and Conquer optimization ( $\mathcal O(nk \log n)$ ~\mathcal O(nk \log n)~)

Using the fact that $A_{i-1,j} \le A_{i,j}$ ~A_{i-1,j} \le A_{i,j}~ and that all $f(*, j)$ ~f(*, j)~ can be calculated from all $f(*, j-1)$ ~f(*, j-1)~, we can apply divide and conquer optimization.

Consider this recursive function Calculate $(j, I_{min}, I_{max}, T_{min}, T_{max})$ that calculates all $f(i, j)$ ~f(i, j)~ for all $i \in [I_{min}, I_{max}]$ ~i \in [I_{min}, I_{max}]~ and a given $j$ ~j~ using known $f(*, j-1)$ ~f(*, j-1)~.

function Calculate(j, I_min, I_max, T_min, T_max)
    if I_min > I_max then
        return
    I_mid ← (I_min + I_max) / 2
    calculate f_{I_mid,j} naively, let T_opt be the optimal t ∈ [T_min, T_max]
    Calculate(j, I_min, I_mid - 1, T_min, T_opt)
    Calculate(j, I_mid + 1, I_max, T_opt, T_max)

The initial call to this function will be Calculate $(j, 1, n, 0, n)$ ~(j, 1, n, 0, n)~ for all $j$ ~j~ from $1$ ~1~ to $k$ ~k~. The time speedup comes up from the fact that all naive calculations of $f_{I_{mid},j}$ ~f_{I_{mid},j}~ on each level of recursion take $\mathcal O(n)$ ~\mathcal O(n)~ in total, because each recursive call splits the segment $[T_{min}, T_{max}]$ ~[T_{min}, T_{max}]~ into 2 (almost) disjoint segments. The depth of recursion is $\mathcal O(\log n)$ ~\mathcal O(\log n)~, so the running time of each Calculate call is $\mathcal O(n \log n)$ ~\mathcal O(n \log n)~. After calculating all $k$ ~k~ layers in $\mathcal O(kn \log n)$ ~\mathcal O(kn \log n)~ time, we get the answer.

Convex Hull Trick optimization ( $\mathcal O(nk)$ ~\mathcal O(nk)~)

Another possible optimization is called Convex Hull Trick. Let's expand (1):

$\displaystyle \begin{align*} f_{i,j} &= \min_{t<i} f_{t,j-1} + (r_{i-1}-l_t+1)^2 - \max(0, r_{t-1}-l_t+1)^2 \\ &= \min_{t<i} f_{t,j-1} + r_{i-1}^2 - 2(l_t-1)r_{i-1} + (l_t-1)^2 - \max(0, r_{t-1}-l_t+1)^2 \\ &= C_i + \min_{t<i} M_t r_{i-1} + B_{t,j} \end{align*}$

where $C_i = r_{i-1}^2$ ~C_i = r_{i-1}^2~, $M_t = -2(l_t-1)$ ~M_t = -2(l_t-1)~, $B_{t,j} = f_{t,j-1} + (l_t-1)^2 - \max(0, r_{t-1}-l_t+1)^2$ .

We see that the formula can be expressed in terms of minimum of linear functions $M_t x + B_{t,j}$ ~M_t x + B_{t,j}~, evaluated at $x = r_{i-1}$ ~x = r_{i-1}~. Notice that as $i$ ~i~ increases, $M_i$ ~M_i~ decreases and $r_i$ ~r_i~ increases. That allows us to maintain the lower envelope of these linear functions using a stack and query the minimum value at a given $x$ ~x~. Adding a line and querying a point can be implemented in $\mathcal O(1)$ ~\mathcal O(1)~ amortized time, so the total running time is $\mathcal O(nk)$ ~\mathcal O(nk)~. This technique is often referred to as the Convex Hull Trick. We will also use it to get the 100 point solution for this problem.

Subtask 6. Let's look at $f_{i,k}$ ~f_{i,k}~ as a function of $k$ ~k~ and study the differences between two adjacent values. The following theorem states that these differences are non-increasing. We'll call such functions convex.

Theorem: $f_{i,j-1}-f_{i,j} \ge f_{i,j}-f_{i,j+1}$

Let's assign some constant penalty $C$ ~C~ for each photo. The new cost function $\tilde f_{i,j} = f_{i,j} + j C$ ~\tilde f_{i,j} = f_{i,j} + j C~ is still convex, because $\tilde f_{i,j-1} - \tilde f_{i,j} = f_{i,j-1}-f_{i,j}-C$ .

Let's introduce another optimization problem without the restriction on the number of photos.

$\displaystyle g_i = \min_{k=1}^n \tilde f_{i,k} = \min_{k=1}^n (f_{i,k} + k C)$

This equation for $g_i$ ~g_i~ can also be expressed only in terms of previous values of $g_j$ ~g_j~ ( $j < i$ ~j < i~).

$\displaystyle g_i = \min_{t<i} g_t + (r_{i-1}-l_t+1)^2 - \max(0, r_{t-1}-l_t+1)^2 + C$

Using this formula, all $g_i$ ~g_i~ can be computed in $\mathcal O(n)$ ~\mathcal O(n)~ time using Convex Hull Trick optimization, if all $l_i$ ~l_i~ and $r_i$ ~r_i~ are sorted beforehand. The solution from subtask 5 can also be modified to find the minimum number of photos required to achieve the optimum, call it $p(C)$ ~p(C)~.

Since $\tilde f$ ~\tilde f~ is convex, $p(C)$ ~p(C)~ is also equal to the minimum $x$ ~x~ such that $\tilde f_{n,x} - \tilde f_{n,x+1} \le 0$ which is equivalent to $f_{n,x}-f_{n,x+1} \le C$ ~f_{n,x}-f_{n,x+1} \le C~, so $p(C)$ ~p(C)~ is monotone. Also if we set $C = 0$ ~C = 0~, optimum value of $g_n$ ~g_n~ is achieved with the $n$ ~n~ photos, and if we set $C = M^2$ ~C = M^2~, then the optimal solution only contains one photo. Combining everything above, we can use binary search to find such $C_{opt}$ ~C_{opt}~ that $p_1 = p(C_{opt}) \ge k$ ~p_1 = p(C_{opt}) \ge k~ and $p_2 = p(C_{opt}+1) \le k$ ~p_2 = p(C_{opt}+1) \le k~.

This means that all differences $(f_{n,p_2}-f_{n,p_2+1}), (f_{n,p_2+1}-f_{n,p_2+2}), \dots, (f_{n,p_1-1}-f_{n,p_1})$ are equal, and $f_{n,j}$ ~f_{n,j}~ is a linear function of $j$ ~j~ on this interval. Since the desired value of $f_{n,k}$ ~f_{n,k}~ is somewhere in this interval, it's possible to calculate it just by linear interpolation, because all slopes are equal.

This solution requires sorting the segments once and doing $\mathcal O(\log m)$ ~\mathcal O(\log m)~ iterations of binary search to find $C_{opt}$ ~C_{opt}~, each iteration running in linear time. Total running time: $\mathcal O(n \log n + n \log m)$ ~\mathcal O(n \log n + n \log m)~.

Comments

There are no comments at the moment.