PROBLEM LINK:
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, dynamic programming
PROBLEM:
Given K, output an integer N and a permutation of [1, 2, \ldots, N] that has exactly K longest increasing subsequences (LIS).
QUICK EXPLANATION:
The array [N, N-1, N-2, \ldots, 1] has exactly N LISes. (But you can’t simply use this because K \gg N.)
Given two arrays A and B that have X and Y LISes respectively, you can form an array with X\cdot Y LISes by adding |A| to each element of B and appending them.
Given two arrays A and B that have X and Y LISes respectively, you can form an array with X+Y LISes by adding |B| to each element of A and appending them. This only works if the LIS length is the same in A and B. If not, you can always increase the LIS length without changing the LIS count of any array A by appending |A|+1 at the end.
Using these, simply express K in ternary:
And then apply the principles above to construct a short array with exactly K LISes. For K \le 10^5, you’ll need a length of at most N = 94.
EXPLANATION:
Like many construction-based problems, this one admits many solutions. This editorial will focus on the author’s solution. Feel free to describe yours!
We’ll use the following notation and terms to simplify things:
- For an array A, let |A| be its length.
- For an array A, let A _ {LIS} be the length of the longest increasing subsequence in A. We’ll also call it the LIS length of A.
- For an array A, let A _ {\#} be the number of longest increasing subsequences in A. We’ll also call it the LIS count of A.
Setter’s solution
For small K, a simple solution exists: [N, N-1, N-2, \ldots, 3, 2, 1]. This array has a LIS length of 1 and a LIS count of N. So if we choose N := K, then we have an answer! Unfortunately, due to problem restrictions, this will only work for K \le 100.
In the other extreme, the array [1, 2, 3, \ldots, N-2, N-1, N] has a LIS length of N and a LIS count of 1, though this also doesn’t help much.
LIS-product of arrays
An interesting thing happens in the array [3, 2, 1, 7, 6, 5, 4]. The LIS length of this array is 2. What is its LIS count? There are 3 ways to select the first number ([3, 2, 1]) and 4 ways to select the second number ([7, 6, 5, 4]), so there are 3\cdot 4 = 12 ways to form an increasing subsequence of length 2, so the LIS count is 12.
Notice that we just constructed an array whose LIS count is greater than its length! More generally, [X, X-1, \ldots, 2, 1, X+Y, X+Y-1, \ldots, X+2, X+1] has length X+Y but a LIS count of X\cdot Y. And for X and Y greater than one, X\cdot Y is always \ge X+Y. This lets us answer more K s beyond 100!
Unfortunately, this solution is only good for K \le 50\cdot 50 (the largest product you can get), and even then, there are some K s which are still unachievable, in particular, prime K s.
We can extend the above observation even more: Let A and B be two arrays with lengths m and n, respectively. Consider the following array: [A _ 1, A _ 2, \ldots, A _ {m-1}, A _ m, m + B _ 1, m + B _ 2, \ldots, m + B _ {n-1}, m + B _ n]. Notice that in this array, the last n elements are larger than the first m elements! Thus, to form a longest increasing subsequence, we can construct the longest increasing subsequences in the first m and last n individually, and then combine them. Thus, this array has the following properties:
- It has length m + n
- Its LIS length is the sum of the LIS lengths of A and B; in other words, A _ {LIS} + B _ {LIS}.
- Its LIS count is the product of the LIS counts of A and B; in other words, A _ {\#}\cdot B _ {\#}.
This is pretty useful because it allows us to chain multiplications together! For example, we can form an array for every K that’s a power of 2, e.g. for K = 2^{11} by performing the operation above repeatedly for [2, 1]:
Let’s call the array [A _ 1, \ldots, A _ m, m + B _ 1, \ldots, m + B _ n] the LIS-product of A and B, and denote it as A\cdot' B. It has the following properties:
- |A\cdot' B| = |A| + |B|
- (A\cdot' B) _ {LIS} = A _ {LIS} + B _ {LIS}
- (A\cdot' B) _ {\#} = A _ {\#}\cdot B _ {\#}
The LIS-product allows us to construct answers for some K beyond 50\cdot 50 and even beyond 10^5!
Unfortunately, this still doesn’t help us answer some K s, in particular those where K is prime or has a large prime factor. So far we can only construct LIS counts that can be expressed as products of other LIS counts. It would be nice if we can construct LIS counts that can be expressed as sums of other LIS counts.
LIS-sum of arrays
Fortunately, there is a way! Given two arrays A and B with lengths m and n, respectively, consider the array [n + A _ 1, n + A _ 2, \ldots, n + A _ {m-1}, n + A _ m, B _ 1, B _ 2, \ldots, B _ {n-1}, B _ n]. This time, the first m elements are larger than the last n elements. Thus, we can’t form an increasing sequence that contain elements from both parts. It means that the LIS length of this array is \max(A _ {LIS}, B _ {LIS}). But what’s the LIS count? An interesting thing happens:
- If A _ {LIS} < B _ {LIS}, then the LIS count is B _ {\#} because all increasing subsequences in the first m elements have lengths \le A _ {LIS} < B _ {LIS}.
- If A _ {LIS} > B _ {LIS}, then similarly the LIS count is A _ {\#}.
- If A _ {LIS} = B _ {LIS}, then the LIS count is A _ {\#} + B _ {\#}, because all LISes in both parts have the same length.
The last part is crucial: Notice that we can now form LIS counts that are sums of other LIS counts! But with one restriction though: we can only do that if the LIS lengths are equal. But thankfully, there’s a way to make the LIS lengths equal, at the cost of increasing the lengths by a bit. For an array A, consider the LIS product A\cdot' [1]. The array [1] has LIS length of 1 and LIS count of 1, so according to the properties of LIS product, A\cdot' [1] has a LIS length of A _ {LIS} + 1 and a LIS count of A _ {\#}\cdot 1 = A _ {\#}. Notice that we increased the LIS length without increasing the LIS count! Similarly, A\cdot' [1, 2, \ldots, n] increases the LIS length by n while retaining the LIS count. Thus, if A _ {LIS} \not= B _ {LIS}, we can make them equal using this property!
Thus, for any arrays A and B such that A _ {LIS} = B _ {LIS} we can call the array [n + A _ 1, \ldots, n + A _ m, B _ 1, \ldots, B _ n] the LIS-sum of A and B, and denote it as A+' B. It has the following properties:
- |A+' B| = |A| + |B|
- (A+' B) _ {LIS} = A _ {LIS} = B _ {LIS}
- (A+' B) _ {\#} = A _ {\#} + B _ {\#}
LIS-arithmetic
By combining the LIS-sum with the LIS-product, we can now answer even more K s than before! For example, we can now also construct any K of the form ab + cd, or a + b(c + de), etc… Pretty much any expression involving additions and multiplications! We can do this because of the following crucial properties:
- (A\cdot' B) _ {\#} = A _ {\#}\cdot B _ {\#}
- (A+' B) _ {\#} = A _ {\#}+ B _ {\#}
This allows us to directly convert normal arithmetic into LIS arithmetic! For our primitive element, we can start with the array [1], which has a LIS length of 1 and a LIS count of 1. Let’s denote the array [1] by the symbol \mathbf{1'}.
Here are a few examples:
-
We can form an array with a LIS count of k by doing \overbrace{\mathbf{1'}+'\mathbf{ 1'}+' \ldots +'\mathbf{1'}}^k. This results in the array [k, k-1, \ldots, 2, 1] which we already know above. Let’s denote this array by \mathbf{k'}.
-
We can form an array with a LIS count of 18 by noticing that 18 = (4\cdot 3) + (3\cdot 2). The array (\mathbf{4'}\cdot'\mathbf{3'})+'(\mathbf{3'}\cdot'\mathbf{2'}) has such a LIS count!
This yields the array: [4, 3, 2, 1, 7, 6, 5]+' [3, 2, 1, 5, 4] = [9, 8, 7, 6, 12, 11, 10, 3, 2, 1, 5, 4].
-
We can form an array with a LIS count of 18 by noticing that 18 = (4\cdot 2\cdot 2) + 2. The array (\mathbf{4'}\cdot'\mathbf{2'}\cdot'\mathbf{2'})+'(\mathbf{2'}\cdot'\mathbf{1'}\cdot'\mathbf{1'}) has such a LIS count! Notice the need to “multiply” by \mathbf{1'} in the second term. This is because +' requires that both arrays have the same LIS length.
This yields the array: [4, 3, 2, 1, 6, 5, 8, 7]+'[2, 1, 3, 4] = [8, 7, 6, 5, 10, 9, 12, 11, 2, 1, 3, 4].
Notice that we’re simply converting each arithmetic expression directly into a LIS-arithmetic expression!
The solution
This still leaves the question: how should we represent K to get an array length \le 100? To answer this, notice that there are huge savings in the length of the array if the terms involved have a small sum. An intuitive way to do this is to have as many LIS-products \cdot' as possible.
The first idea is to represent K in binary. This way, we can express K in the form 2^{e _ 1} + 2^{e _ 2} + \ldots + 2^{e _ k}, so we can build the array (\mathbf{2'})^{e _ 1} +' (\mathbf{2'})^{e _ 2} +' \ldots +' (\mathbf{2'})^{e _ k}, where “LIS-exponentiation” is defined as repeated LIS-products. This works, as long as we adjust each array first before applying +', so that they get the same LIS lengths. This is a good solution that gives us a length of < 500 for all K \le 10^5! Unfortunately, this doesn’t pass the problem bounds; the longest one is > 300.
The next idea to reduce the length is to use ternary instead. In other words, if K = a _ 0 + a _ 13^1 + a _ 23^2 + \ldots, then the array we form is \mathbf{a _ 0}' +' \mathbf{a _ 1}'\cdot'(\mathbf{3'})^1 +' \mathbf{a _ 2}'\cdot'(\mathbf{3'})^2 +' \ldots (again remembering to adjust before applying +'). If a _ i = 1, we can skip multiplying by \mathbf{a _ i}' = \mathbf{1'} to shorten the array a bit. We also skip terms with a _ i = 0.
Why is this better? It’s better because in binary, every two elements we include doubles the LIS count, while in ternary, every three elements we include triples the LIS count. Thus, on average, in binary every element multiplies the LIS count by 2^{1/2} while in ternary every element multiplies the LIS count by 3^{1/3}. Since 2^{1/2} < 3^{1/3}, ternary is more efficient. In fact, ternary is the most efficient base among all bases! By using ternary, the maximum length we now need is < 250. Unfortunately, it still a bit far from 100.
The next idea is write the ternary form differently: Instead of writing it as a _ 0 + a _ 13^1 + a _ 23^2 + \ldots, we write it as a _ 0 + 3(a _ 1 + 3(a _ 2 + \ldots)). Thus, the array we form is \mathbf{a _ 0}' + \mathbf{3'}\cdot'(\mathbf{a _ 1}' + \mathbf{3'}\cdot'(\mathbf{a _ 2}' +' \ldots)) (again remembering to adjust before applying +' and to skip a _ i = 0).
As an example, consider K = 80. The ternary form of this is 2 + 2\cdot 3 + 2\cdot 3^2 + 2\cdot 3^3, so you normally you would form the array (\mathbf{2'}\cdot'\mathbf{1'}\cdot'\mathbf{1'}\cdot'\mathbf{1'}) +' (\mathbf{2'}\cdot'\mathbf{3'}\cdot'\mathbf{1'}\cdot'\mathbf{1'}) +' (\mathbf{2'}\cdot'\mathbf{3'}\cdot'\mathbf{3'}\cdot'\mathbf{1'}) +' (\mathbf{2'}\cdot'\mathbf{3'}\cdot'\mathbf{3'}\cdot'\mathbf{3'}), which has length (2+1+1+1)+(2+3+1+1)+(2+3+3+1)+(2+3+3+3) = 32. However, writing the ternary form as 2 + 3\cdot(2 + 3\cdot (2 + 3\cdot 2)), the array would be (\mathbf{2'}\cdot' \mathbf{1'}\cdot' \mathbf{1'}\cdot' \mathbf{1'}) +' \mathbf{3'}\cdot'[(\mathbf{2'}\cdot' \mathbf{1'}\cdot' \mathbf{1'}) +' \mathbf{3'}\cdot'(\mathbf{2'}\cdot'\mathbf{1'} +' \mathbf{3'}\cdot'\mathbf{2'})], which only has length (2+1+1+1)+3+(2+1+1)+3+(2+1)+(3+2) = 23. In general, the smaller the total numbers that appear on your representation, the better.
Using this technique, we are now able to reduce the required length to at most 94, and we’ve now solved the problem!
The ideas above are enough to pass the problem already, but I’m sure with a couple more tricks you can reduce the length even more.
Time Complexity:
[O(N)](https://en.wikipedia.org/wiki/Output-sensitive _ algorithm)