Editorial for COCI '21 Contest 1 #5 Volontiranje

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.

We use 'LIS' as a shorthand for a longest increasing subsequence.

The first subtask can be solved by finding every LIS, and then find via dynamic programming with bitmasks a set of them which do not overlap.

For the rest of the subtasks, some more insight into the structure of the longest increasing subsequences is needed. The solution in short is the following: we can remove the subsequences one by one, each time greedily building the lexicographically smallest LIS. A naive implementation of that would be too slow, so it is necessary to do some backtracking and removing of certain elements for which we are sure that they will not help with the solution, so that the time complexity gets reduced.

A more detailed description and proofs of the observations are given, but first we will mention a couple of general properties of this type of configuration, which are common in these types of tasks.

For each index $i$ $i$ $(1 \le i \le n)$ $(1 \leq i \leq n)$ , let's define $LIS[i]$ $L I S [i]$ as the length of the longest increasing subsequence ending at index $i$ $i$ . This can be calculated with the formula $LIS[i] = 1 + \max\{LIS[j] : 1 \le j < i, p_j < p_i\}$ $L I S [i] = 1 + max {L I S [j] : 1 \leq j < i, p_{j} < p_{i}}$ using standard algorithms for finding a LIS. Furthermore, let $l$ $l$ denote the length of a LIS, i.e. $l = \max_{1 \le i \le n} LIS[i]$ $l = max_{1 \leq i \leq n} L I S [i]$ . Also, for a fixed positive integer $k$ $k$ , let's define $S_k$ $S_{k}$ to be the set of all indices $i$ $i$ for which $LIS[i] = k$ $L I S [i] = k$ . Two important observations are:

Claim
For all positive integers $k$ $k$ , if we look at the values corresponding to the indices of $S_k$ $S_{k}$ , they will be decreasing.

Proof
If there were $a, b \in S_k$ $a, b \in S_{k}$ such that $a < b$ $a < b$ and $p_a < p_b$ $p_{a} < p_{b}$ , the longest increasing subsequence ending at $a$ $a$ could be extended to $b$ $b$ and then $LIS[a] < LIS[b]$ $L I S [a] < L I S [b]$ . □
Claim
For each LIS $x_1, x_2, \dots, x_l$ $x_{1}, x_{2}, \dots, x_{l}$ (where $x_1 < x_2 < \dots < x_l$ $x_{1} < x_{2} < \dots < x_{l}$ ), it holds that $LIS[x_i] = i$ $L I S [x_{i}] = i$ for all $1 \le i \le l$ $1 \leq i \leq l$ . In other words, if we look at a fixed index $j$ $j$ , it will always find itself at the same position in every LIS (precisely at position $LIS[j]$ $L I S [j]$ ).

Proof
Just as in the previous claim, we conclude that $LIS[x_1] < \dots < LIS[x_l]$ $L I S [x_{1}] < \dots < L I S [x_{l}]$ . Noting that $LIS[x_1] = 1$ $L I S [x_{1}] = 1$ and $LIS[x_l] = l$ $L I S [x_{l}] = l$ , these $l$ $l$ numbers must be exactly $1, 2, \dots, l$ $1, 2, \dots, l$ . □

The things mentioned so far can be visualized in the following way (see image below): the given permutation can be interpreted as a set of points $(i, p_i)$ $(i, p_{i})$ in coordinate plane, and increasing subsequences can be thought of as path going through the points, moving 'up and to the right'. Having in mind the claims mentioned above, the sets $S_k$ $S_{k}$ come in layers, and a LIS (red arrows) pass through one point in each layer.

Between every two neighbouring layers, blue edges are drawn between pairs of points where an increasing subsequence of the first point can be extended to the second point (those are actually pairs of points where the second point is 'up and to the right' of the first point). Thus, a LIS is any path using the blue edges which starts in the first layer and ends in the last layer. Also, for each point, all of its neighbours form a segment of points in the next layer.

Now we will mention the claims specific to the problem.

Claim 1:

Assume that in the optimal solution, the number of LIS's is equal to $m$ $m$ , and that the indices of the $i^\text{th}$ $i^{th}$ LIS are denoted by $x_{i,1}, x_{i,2}, \dots, x_{i,l}$ $x_{i, 1}, x_{i, 2}, \dots, x_{i, l}$ . Then, there exists an optimal solution such that for each $j$ $j$ , it holds that $x_{1,j} < x_{2,j} < \dots < x_{m,j}$ $x_{1, j} < x_{2, j} < \dots < x_{m, j}$ .

On the image, this corresponds to the fact that it is possible to choose the red paths so that they do not intersect.

Proof:

Let's look at a situation where the paths intersect and let's label the points as in the image. Since the edges $\overline{AA'}$ $\overset{―}{A A^{'}}$ and $\overline{BB'}$ $\overset{―}{B B^{'}}$ intersect, the points $A'$ $A^{'}$ and $B'$ $B^{'}$ have to be in the intersection of the 'fields of vision' of the points $A$ $A$ and $B$ $B$ . Thus, instead of the current edges, we can take the edges $\overline{AB'}$ $\overset{―}{A B^{'}}$ and $\overline{BA'}$ $\overset{―}{B A^{'}}$ , untangling the paths. Using a sequence of such untanglings, we can make it so that the paths do not intersect. □

Since there exists an optimal solution in which the paths do not intersect, the idea comes to mind of trying to pick paths from left to right (it is possible to make a solution in the opposite direction) such that we take the paths that are 'as left as possible' so that we would have more room for the remaining paths. The following claim shows that the right choice is in fact the lexicographically smallest LIS, i.e. that it leaves the most room.

Claim 2:

Assume that from each layer, we have removed a prefix of points, so that only the remaining points are allowed to be used when constructing a LIS. The lexicographically smallest LIS of the remaining points will then be the smallest for each layer separately.

Proof

Assume not. Denote the lexicographically smallest LIS by $P$ $P$ . By the assumption, there exists a path $Q$ $Q$ such that in the first layer it begins at the same point or later than $P$ $P$ , but which finds itself earlier than $P$ $P$ in some other layer. The first place where this happens is actually a crossing, which by claim 1, we can untangle, obtaining a lexicographically smaller path than $P$ $P$ . □

A consequence of claim 2 is that each point that is to the left of the lexicographically smallest LIS (in any layer) can never be used for building a LIS. Thus, the solution can be obtained if at every step, we choose the lexicographically smallest LIS and remove all of the points on or to the left of it. A solution that goes through all of the remaining points for each step and finds the desired LIS solves the second subtask.

To solve the third subtask, the searching process should be sped up. Say we're trying to build our current LIS and that we are currently at node $v$ $v$ (the LIS is built in order from smaller to larger values, and we have so far built a prefix of the LIS). By the things mentioned, node $v$ $v$ is the leftmost node in the current layer that has the possibility of being extended to a LIS. All of the nodes in the next layer which are to the left of $v$ $v$ can immediately be deleted, because if we can't reach them now, we won't be able to reach them in the future. Then, if from $v$ $v$ we cannot reach the leftmost node in the next layer (i.e. if that node is below $v$ $v$ ), then no path from $v$ $v$ can continue to the last layer. For that reason, we should remove node $v$ $v$ , and the new current vertex will become $v$ $v$ 's predecessor, from which we repeat the process. Of course, if it is possible to go from $v$ $v$ to the leftmost node in the next layer, the path will continue through it.

After we make the division into layers, which can be done with time complexity $\mathcal O(n \log n)$ $O (n \log n)$ , the mentioned searching procedure works in $\mathcal O(n)$ $O (n)$ , which is enough for the third subtask.

Comments

There are no comments at the moment.