MAKELIS - Editorial

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, 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:

K = a _ 0 + 3\cdot (a _ 1 + 3\cdot (a _ 2 + 3\cdot (a _ 3 + \ldots)))

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]:

[2, 1, 4, 3, 6, 5, 8, 7, 10, 9, 12, 11, 14, 13, 16, 15, 18, 17, 20, 19, 22, 21]

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:

  1. 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'}.

  2. 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].

  3. 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)

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter
Tester

5 Likes

“I loved solving this question.”

The constraint is very restrictive, just use numbers very efficiently.

So, I tried to make a LIS’s of length equal to MSB of K (for K = 4, length = 3). Now you need exactly K such LIS’s, so now try to create LIS’s in powers of two starting from the least power of 2 present, if power of 2 p, then create p pairs of numbers so that you can select only one of them in LIS (basically these numbers will be consecutive numbers with greater number coming first like 2 1) and to make for the rest of LIS add the remaining bigger numbers.

Let’s say you need to create for p = 2 and MSB is 4, then (2 1) (4 3) [5 6], only one number in round bracket can be selected but all numbers in square brackets should be selected. Now do this for all powers of 2 present in K. This will give a solution with lesser numbers but the constraint is more restrictive, basically at worst case you will need 17*16 numbers (K <=10^5).

Now, other optimization is to use the round bracket pairs used previously for the higher powers of 2 as well. This leads to a solution within worst 46 digits used for 65535. I will leave this optimisation as an exercise.

P.S : No, need of ternary as we can use the same trick with ternary for binary as well.

2 Likes

Here’s a solution that uses 48 numbers in the worst case: say n= 2^{a_0} + 2^{a_1} + \cdots + 2^{a_n} where a_1 < a_2 < ...< a_n. For the time being let’s assume that we are allowed to put non-integer numbers in the list (we can “uncompress” them later). Start with the list \{2, 1, 4, 3, \cdots, 2a_n, 2a_n-1\} (basically a_n blocks, where the i’th block consists of \{i+1, i\}). There are 2^{a_n} LIS’s in it with length a_n. We now want to add 2^{a_{n-1}} more LIS’s. To do this, add any a_n - a_{n-1} distinct real numbers in the range [p, q] to the left of the list in increasing order, where p is the larger number in the (a_{n-1}+1)'th block from the right and q is the smaller number in the a_{n-1}'th block. This ensures that 2^{a_{n-1}} new LIS’s are formed, each starting with the newly added numbers. Similarly add these numbers for the rest of the bits. The total number of numbers used will be approximately 3b(n) where b(n) is the number of bits in n. Code: CodeChef: Practical coding for everyone

1 Like

Very similar problem from 5 days ago - https://csacademy.com/contest/beta-round-6/#task/lis_generator

You need to sign in to see the statement.

1 Like

I tried a different approach, can someone help me where I went wrong?

I represented the number in terms of 2,3,5 and 7

suppose the number is 97 it can be written as( 3 * 2 * 2 * 2 * 2 * 2 + 1 ) i.e. 96 +1

so, a way to represent an array with 96 LIS is {(2 1) (4 3) (6 5) (8 7) (10 9) (13 12 11)} brackets help to identify the permutations.

and then for 97 I add another LIS with numbers greater than others in the begining thus the result was :

14 15 16 17 18 19 2 1 4 3 6 5 8 7 10 9 13 12 11

Similarly for 102 = 2 * 3 * 17 = 2 * 3 * (16 +1) = 2 * 3 * (2 * 2 * 2 * 2 + 1)

The result was : (2 1) (5 4 3) [14 15 16 17 (7 6) (9 8) (11 10) (13 12) ]
i.e 2 X 3 X ( 1 + 2 X 2 X 2 X 2 )

can someone help me to figure out why I am getting WA? I tried a lot of test cases even for a large number with a lot of prime numbers(which increase the size of array as in my case) like 1026454 but the number was still under 71. I am sharing the code, though it is not a well written one, please try to read it.

CodeChef: Practical coding for everyone

I am trying to implement solution as per the editorial but still getting WA
https://www.codechef.com/viewsolution/10351800
I am not able to figure out the error?? Plz Help

Hi,

How does writing the ternary form differently help? I didn’t understand that part.

Thanks!

@joylal4896 I used similar approach just add 11(take 2,3,5 ,7and 11 instead of just 2,3,5 and 7) and you will get ac

Isn’t p > q in your explanation. I think you meant range [q,p]. Also shouldn’t the numbers be added on the right of list. For example, if k=82835
k = 2^16 + 2^14 …
We start with the list [2,1,4,3…32,31]
and then we add 27.5 and 28.5 to the right side which results in [2,1,…32,31,27.5,28.5]. Is this correct or am I missing something ?

dammit I gave this contest…how could i not remember this T-T

It fails this test : 19199

received length : 108.