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 means that you can use a photo for each point of interest: the minimum photo containing point (r_i, c_i) is the square containing points (r_i, r_i) and (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) and (y, y), then it also covers all points between them.
  • Each photo's boundary must be equal to some r_i.

Now we can treat this problem as a dynamic programming problem: cover n points on a line using 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 and remove duplicates. Notice that each photo should cover some contiguous set of points.

  • Let f_{i,j} be the minimum cost to cover the first i points with at most j photos.
  • f_{0,j} = 0 for all 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} contains the answer.
  • \mathcal O(nk) states, calculating transitions from each state takes \mathcal O(n) time.
  • Overall running time: \mathcal O(n^2 k).

Subtask 3 dropped the 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) and (y, y) covers point (r, c) if and only if segment [\min(r, c), \max(r, c)] is fully contained in segment [x, y] (x \le y). So if we consider segments [\min(r_i, c_i), \max(r_i, c_i)] instead of points (r_i, c_i), the problem is reduced to the following: cover all n segments with k larger segments such that their total area (considering intersections) is minimized.

If segment S_i is included in some other segment S_j, then any photo that covers S_j also covers S_i, so we can safely remove S_i. Removing all such segments can be done in \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: r_i < r_j and c_i < c_j. Observations and definition of f_{i,j} are almost identical to the previous solution:

  • f_{0,j} = 0 for all 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 and t (t > 0).
  • f_{n,k} contains the answer.
  • Overall running time: \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) solutions. One possible solution uses Knuth's optimization.

Define A_{i,j} as the optimal 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}

This allows us to prune the search space on each step, reducing the running time to \mathcal O(n^2). If you calculate f_{i,j} in order of increasing j and decreasing i, then at the moment of calculating f_{i,j}, values of A_{i,j-1} and A_{i+1,j} are already known, so you can only check 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) running time. Also, don't forget about 64 bit integers.

Subtask 5 required a different kind of optimization, running in \mathcal O(nk) or \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))

Using the fact that A_{i-1,j} \le A_{i,j} and that all f(*, j) can be calculated from all 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) for all i \in [I_{min}, I_{max}] and a given j using known f(*, j-1).

function Calculate(j, I_min, I_max, T_min, T_max)
    if I_min > I_max then
    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) for all j from 1 to k. The time speedup comes up from the fact that all naive calculations of f_{I_{mid},j} on each level of recursion take \mathcal O(n) in total, because each recursive call splits the segment [T_{min}, T_{max}] into 2 (almost) disjoint segments. The depth of recursion is \mathcal O(\log n), so the running time of each Calculate call is \mathcal O(n \log n). After calculating all k layers in \mathcal O(kn \log n) time, we get the answer.

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

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

\displaystyle \begin{align*}
&= \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}

where C_i = r_{i-1}^2, 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}, evaluated at x = r_{i-1}. Notice that as i increases, M_i decreases and 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. Adding a line and querying a point can be implemented in \mathcal O(1) amortized time, so the total running time is \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} as a function of 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 for each photo. The new cost function \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 can also be expressed only in terms of previous values of g_j (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 can be computed in \mathcal O(n) time using Convex Hull Trick optimization, if all l_i and 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).

Since \tilde f is convex, p(C) is also equal to the minimum 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, so p(C) is monotone. Also if we set C = 0, optimum value of g_n is achieved with the n photos, and if we set C = M^2, then the optimal solution only contains one photo. Combining everything above, we can use binary search to find such C_{opt} that p_1 = p(C_{opt}) \ge k and 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} is a linear function of j on this interval. Since the desired value of 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) iterations of binary search to find C_{opt}, each iteration running in linear time. Total running time: \mathcal O(n \log n + n \log m).


There are no comments at the moment.