PROBLEM LINK:Author: 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: 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:
$A\cdot' B$ has the following very useful properties:
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:
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:
But actually, we can be greedy about this! The following algorithm gives us one such sequence:
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:
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:
This question is marked "community wiki".
asked 12 Jun '16, 07:22
