LISLDS - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Contest
Practice

Author: Kevin Atienza
Testers: Sergey Kulik and Vasya Antoniuk
Translators: Vasya Antoniuk (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)
Editorialist: Kevin Atienza

DIFFICULTY:

Medium

PREREQUISITES:

Longest increasing subsequence, Erdős–Szekeres theorem

PROBLEM:

Given N, A, and B, find a permutation of [1, 2, 3, \ldots, N] whose longest increasing subsequence has length A and longest decreasing subsequence has length B, or determine if no such permutation exists.

QUICK EXPLANATION:

This permutation exists if A + B - 1 \le N \le AB. If it exists, then it can be obtained as a subsequence of:

[B, B-1, B-2, \ldots, 1, 2B, 2B-1, 2B-2, \ldots, B+1, 3B, 3B-1, 3B-2, \ldots, 2B+1, \ldots, AB, AB-1, AB-2, \ldots, (A-1)B+1]

Specifically, any subsequence of this sequence that contains [B, B-1, B-2, \ldots, 1] and [B, 2B, 3B, \ldots, AB] is valid. So take such a subsequence of length N, and adjust so that the values are in [1\ldots N].

EXPLANATION:

We define the LIS length of an array as the length of its longest increasing subsequence. We also define the LDS length as the length of its longest decreasing subsequence.

If you tried to solve this from first principles, then your solution will probably give you an intuition as to why Erdős–Szekeres theorem is true! The theorem says that a permutation of length > AB either has a LIS length > A or a LDS length of > B. The contrapositive of this is quite useful for us:

An array with LIS length \le A and LDS length \le B must have a length of \le AB.

This means that N must be \le AB, otherwise no such permutation exists!

Another useful observation gives us a lower bound for N to be valid:

An LIS and an LDS can only have at most one element in common.

This can easily be seen by considering two values X_i and X_j, where i \not= j. Either X_i > X_j or X_i < X_j, so X_i and X_j cannot appear in an increasing and decreasing subsequence at the same time.

A corollary of this is:

An array with LIS length = A and LDS length = B must have a length of \ge A + B - 1.

So N must be \ge A + B - 1, otherwise no permutation exists!

But if both conditions hold, i.e., when A + B - 1 \le N \le AB, then does there exist an array with LIS length of A and LDS length of B? The answer is yes, and we’ll describe one such construction.

To describe the solution, we’ll use the same notation as in the Longest Increasing Subsequences (MAKELIS) editorial:

  • For an array A, let |A| be its length.
  • For an array A, let A _ {LIS} be its LIS length.
  • For an array A, let A _ {LDS} be its LDS length.
  • We denote by \mathbf{k'} the array [k, k-1, \ldots, 2, 1]. Thus, \mathbf{k'} _ {LIS} = 1 and \mathbf{k'} _ {LDS} = k.
  • If A and B are arrays of length m and n, respectively, then let’s denote by A\cdot' B the array [A _ 1, \ldots, A _ m, m + B _ 1, \ldots, m + B _ n].

A\cdot' B has the following very useful properties:

  1. |A\cdot' B| = |A| + |B|,
  2. (A\cdot' B) _ {LIS} = A _ {LIS} + B _ {LIS},
  3. (A\cdot' B) _ {LDS} = \max(A _ {LDS}, B _ {LDS}).

The first two are described in the MAKELIS editorial (but are also pretty easy to see), while the third one can be seen by noticing that the first m elements of A\cdot' B are smaller than the last n elements, so no decreasing subsequence can have elements from both parts at the same time.

Now, let’s describe the construction. Note that the array \mathbf{x _ 1'}\cdot'\mathbf{x _ 2'}\cdot' \ldots \cdot'\mathbf{x _ n'} has the following properties:

  • Its length is x _ 1 + x _ 2 + \ldots + x _ n by the first property of \cdot'.
  • Its LIS length is \overbrace{1 + 1 + \ldots + 1}^n = n because of the properties of \mathbf{k'} and \cdot'.
  • Its LDS length is \max(x _ 1, x _ 2, \ldots, x _ n) by the third property of \cdot'.

So our solution is basically constructing an array of that form, i.e., finding a sequence of integers x _ 1, x _ 2, \ldots, x _ n such that:

  • x _ 1 + x _ 2 + \ldots + x _ n = N
  • n = A
  • \max(x _ 1, x _ 2, \ldots, x _ n) = B

But actually, we can be greedy about this! The following algorithm gives us one such sequence:

  1. First, set x _ 1 = B and x _ 2 = x _ 3 = \ldots = x _ A = 1. Note that the second and third conditions are already satisfied, but the sum is currently A + B - 1, which may or may not be equal to N yet. But by assumption, A + B - 1 \le N.
  2. While x _ 1 + x _ 2 + \ldots + x _ A < N, find the smallest index i such that x _ i < B, and increment it by 1.

This works assuming we can always find the index i in the second step. We can prove that. Notice that the procedure doesn’t make any x _ i exceed B. Thus, if no such index i exists, then all x _ i must be equal to B. But by assumption, N \le AB, which means AB = x _ 1 + x _ 2 + \ldots + x _ A < N \le AB, a contradiction. So, i must exist!

This gives us the following algorithm:

def construct(N,A,B):
    
    if not (A + B - 1 <= N <= A*B):
        // impossible
        return -1

    // compute x sequence
    x[1..A]
    x[1] = B
    for i in 2..A:
        x[i] = 1
    total = A + B - 1
    i = 2
    while total < N:
        // find the index
        while x[i] == B:
            i++
        // increment
        x[i]++
        total++

    // construct
    array = []
    start = 0
    for i=1..N:
        for value in start+x[i]..start+1:
            append 'value' at the end of 'array'
        start += x[i]

    return array

This runs in O(N) time! Note that other solutions exist.

For a proof of the Erdős–Szekeres theorem, you can check out its Wikipedia page. Some of the proofs there are very nice. I especially like the first one!

Time Complexity:

O(N \log N) or O(N)

AUTHOR’S AND TESTER’S SOLUTIONS:

setter
tester