PERMSLCS - Editorial

editorial
, , , , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: Anton Trygub
Developer: Anton Trygub
Editorialist: Anton Trygub

DIFFICULTY:

3621

Subtask 1

Let’s notice the simple property:

Let a, b be any sequences of length n consisting of integers from 1 to n, and p be any permutation of integers from 1 to n. Then, we have the following property:

  • LCS(a, b) = LCS((p_{a_1}, p_{a_2}, \ldots, p_{a_n}), (p_{b_1}, p_{b_2}, \ldots, p_{b_n}))

Indeed, we don’t care about which element is larger than which. We only care about which element is equal to which.

With that in mind, we might notice that if there is such a triple of permutations p, q, r, then there also is such a triple with p = (1, 2, \ldots, n). This allows us to fit the brute force in time.

Let’s try all candidates for permutations q, r (there are (n!)^2 such pairs), and for each pair of candidates, candidate pairwise $LCS$s (we can find the LCS of two permutations in O(n^2), for example). For each triple (a, b, c) that we saw, memorize any triple of permutations (p, q, r) that produced it. This allows us to solve the subtask with preprocessing, taking O((6!)6^2), which passes easily.

Subtask 2

Note that if LCS(q, r) = n, we must have q = r, so we also must have a = b. We are still considering p = (1, 2, \ldots, n). Also, note that LCS((1, 2, \ldots, n), q) is just equal to the length of the longest increasing subsequence of q.

Now, we need to check if there exists a permutation with LIS(q) = a (from now on, by LIS(q) I will denote the length of the longest increasing subsequence of q). It turns out that it exists for each 1 \le a \le n. Indeed, it’s enough to consider q = (n, n-1, \ldots, a+2, a+1, 1, 2, \ldots, a).

Subtask 3

If LCS(p, q) = 1, then q must be the reverse of p. In our case, we would have p = (1, 2, \ldots, n), q = (n, n-1, \ldots, 1). Note that LCS((n, n-1, \ldots, 1), r) = LDS(r) for any permutation, where by LDS(r) we denote the length of the longest decreasing subsequence of r.

So, we just need to determine if there exists a permutation of length n with LIS = b and LDS = c. Here, the Erdős–Szekeres theorem might be useful. It states that in any sequence with length (r-1)(s-1), there is an increasing subsequence of length r, or a decreasing subsequence of length s. We will use it in the following form: LIS(p)LDS(p)\ge n (indeed, if LIS(p)LDS(p) \le n-1, then the subsequence of length n would have an increasing subsequence of length LIS(p)+1, or a decreasing subsequence of length LDS(p)+1.

So, we must have bc \ge n. Is this condition sufficient? Sadly, no. Consider b = c = n, for example. We would have to have p = q = r, but p \neq q (for n>1).

Then, we might notice the second condition: LCS(p)+LDS(p)\le n+1 for any permutation p of length n. Indeed, any increasing subsequence may have at most 1 common element with any decreasing one, so at most one of n elements can contribute to both LCS and LDS, and others can contribute to at most one of them.

So, we get: b+c \le n+1, bc \ge n. Are these conditions sufficient? Turns out, yes. Consider permutation c, c-1, \ldots, 1, 2c, 2c-1, \ldots, c+1, 3c, \ldots, bc, bc-1, \ldots, bc - c + 1 of integers from 1 to bc. It’s easy to see that its LIS is b, and its LDS is c. (For example, the argument for LDS: it clearly has an increasing subsequence c, 2c, \ldots, bc, but also is split into b decreasing blocks, none of which can contain more than one element from LIS).

Consider some subsequence of this permutation, which contains elements c, 2c, \ldots, bc, as well as elements c, c-1, \ldots, 1 (c in written twice, yes) ~— n-1 elements in total. Any such subsequence will have LIS = b and LDS = c. As b+c-1 \le n \le bc, we can take some extra n-(b+c-1) elements of this permutation, and obtain a sequence with LIS = b and LDS = c of length n. Then, we can just “compress” the sequence to the permutation by mapping different values to 1, 2, \ldots, n in the relative order.

Subtask 4

In some sense, this subtask was included so that participants would be able to check if their criteria were correct, basically guessing before getting to the actual construction. That’s what we are going to do here, leaving the proof and the construction for the subtask 5.

Let’s try to guess these criteria. We already know some criteria for the case a = 1. Maybe we can generalize them somehow?

First, let’s try to get something similar to LIS(p) + LDS(q) \le n+1. Consider common subsequences of (p, r) and (q, r). If their lengths are b, c correspondingly, they must have at least b+c-n elements in common. These common elements would form a common subsequence of p, q, so b + c - n \le a, or b+c\le a+n.

Now, let’s try to get something similar to LIS(p)LDS(p) \ge n. I claim, that LCS(p, q)LCS(q, r)LCS(p, r)\ge n. Proof: suppose that abc \le n. As p = (1, 2, \ldots, n), we get that LIS(q) = a \implies LDS(q) \ge \frac{n}{a} \ge bc + 1. Consider some decreasing subsequence of q of length bc+1. Let’s look at how the elements of this subsequence are situated in r. No b+1 of these elements can form an increasing subsequence in r (as then we would have LCS(p, r) \ge b+1. No c+1 of these elements can form a decreasing subsequence in r (as then we would have LCS(q, r) \ge c+1. But at least one of these has to hold, by the Erdős–Szekeres theorem! Contradiction.

So, we found two necessary conditions:

  • b + c \le a + n

  • abc \ge n

It turns out that these conditions are actually sufficient. We will prove this in the next section.

Subtask 5

Let’s prove that for such a, b, c, n there always exists such a triple of permutations. We will prove this by induction. We already know this is the case if a = 1, and it’s clear for n = 1. Now, suppose that it’s true for all tuples (a_1, b_1, c_1, n_1) with a_1\le a, b_1 \le b, c_1 \le c, n_1 \le n.

Suppose that b+c\le a+n and abc \ge n. If a>1 and (a-1)(b-1)(c-1) \ge n-1, then we know that there is such a triple of permutations for tuple (a-1, b-1, c-1, n-1) as well. Consider these permutations p_1, q_1, r_1. Let’s append n to each of them. Clearly, the LCS of each pair will increase by precisely 1, so we would get the desired outcome.

Now, let’s provide a construction for the case abc = n. Let’s take:

  • p = (1, 2, \ldots, abc)

  • q = (abc-a+1, abc-a+2, \ldots, abc, abc-2a+1, abc-2a+2, \ldots, abc-a,\ldots, 1, 2, \ldots, a) (bc increasing blocks, each of length a)

  • r = (ac, ac-1, \ldots, 1, 2ac, 2ac-1, \ldots, ac+1, \ldots, abc, abc-1, \ldots, abc-ac+1) (b decreasing blocks, each of length ac)

It’s easy to see that LIS(q) = a and LIS(r) = b, it only remains to prove that LCS(q, r) = c. Sequence ac, (a-1)c, \ldots, 2c, c is a subsequence of both. Suppose that some sequence of length c+1 is a subsequence of both. If some two elements x<y of it are from different blocks of length ac (here I mean blocks [ac, ac-1, \ldots, 1], [2ac, 2ac-1, \ldots, ac+1], \ldots, [abc, abc-1, \ldots, abc-ac+1], then in q x goes after y, and in r before, which is impossible. So, they all must be from the same block, say, [kac, kac-1, \ldots, (k-1)ac+1]. Then, this subsequence must be decreasing. However, the elements [kac, kac-1, \ldots, (k-1)ac+1] in q go in order ([kac-a+1, kac-a+2, \ldots, kac], [kac-2a+1, kac-2a+2, \ldots, kac-a], \ldots, [(k-1)ac+1, (k-1)ac+2, \ldots, (k-1)ac + a]) ~— that is, c increasing blocks, each of size a. So, it can’t have decreasing subsequence of length c+1 (as some two elements would have to be in the same block). Contradiction.

How to use this construction for n = abc to get construction for smaller n, the same way as we did in the case a = 1? Let’s select elements 1, 2, \ldots, a, 1, ac+1, 2ac+1, \ldots, (b-1)ac+1, ac-c+1, ac-2c+1, \ldots, 1 (1 appears in all 3 of these sequences). We want to take some subset of size n of integers from 1 to abc, containing all the a+b+c-2 elements above, and remove from each of p, q, r all elements not contained in this subset (and later “compress” by mapping k-th largest number among selected to k). If we do this, we will get precisely LCS(p, q) = a, LCS(p, r) = b, LCS(q, r) = c). We can do this when a+b+c-2 \le n.

If we haven’t succeeded, we have the following conditions:

  • (a-1)+(b-1)+(c-1) \ge n

  • (a-1)(b-1)(c-1) \le n-2

When is xyz \le x+y+z-2 possible in general for positive integers x\le y \le z? If x\ge 2, we get xyz \ge 4z > x + y + z > x + y + z - 2, so we must have x = 1, or yz \le y+z-1. For y\ge 2, we get yz \ge 2z \ge y+z > y+z-1, so we must have y = 1. In this case, we get a = b = 2, and c+1 \ge n, c-1\le n-2, implying c = n-1. So, the only remaining case is (2, 2, n-1, n) (when n \ge 3).

For this case, there is a simple construction:

  • p = (1, 2, \ldots, n)

  • q = (n, n-1, \ldots, 5, 4, 3, 1, 2)

  • r = (n, n-1, \ldots, 5, 4, 1, 3, 2)

We have covered all cases, and provided an algorithm how to construct such permutations, so we are done.