PROBLEM LINK:Author: 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, N1, N2, \ldots, 1]$ has exactly $N$ LISes. (But you can't simply use this because $K \gg N$.) Using these, simply express $K$ in ternary: EXPLANATION:Like many constructionbased 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:
Setter's solutionFor small $K$, a simple solution exists: $[N, N1, N2, \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, N2, N1, N]$ has a LIS length of $N$ and a LIS count of $1$, though this also doesn't help much. LISproduct of arraysAn 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, X1, \ldots, 2, 1, X+Y, X+Y1, \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 _ {m1}, A _ m, m + B _ 1, m + B _ 2, \ldots, m + B _ {n1}, 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:
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 LISproduct of $A$ and $B$, and denote it as $A\cdot' B$. It has the following properties:
The LISproduct 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. LISsum of arraysFortunately, 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 _ {m1}, n + A _ m, B _ 1, B _ 2, \ldots, B _ {n1}, 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:
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 LISsum of $A$ and $B$, and denote it as $A+' B$. It has the following properties:
LISarithmeticBy combining the LISsum with the LISproduct, 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:
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:
Notice that we're simply converting each arithmetic expression directly into a LISarithmetic expression! The solutionThis 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 LISproducts $\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 "LISexponentiation" is defined as repeated LISproducts. 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:AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 03 Jun '16, 06:43

“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. answered 05 Jun '16, 22:20

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 noninteger numbers in the list (we can "uncompress" them later). Start with the list $\{2, 1, 4, 3, \cdots, 2a_n, 2a_n1\}$ (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_{n1}}$ more LIS's. To do this, add any $a_n  a_{n1}$ 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_{n1}+1)$'th block from the right and q is the smaller number in the $a_{n1}$'th block. This ensures that $2^{a_{n1}}$ 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: https://www.codechef.com/viewsolution/10331895 answered 05 Jun '16, 22:24
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 ?
(05 Jun '16, 23:02)

Very similar problem from 5 days ago  https://csacademy.com/contest/betaround6/#task/lis_generator You need to sign in to see the statement. answered 05 Jun '16, 23:10

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. answered 06 Jun '16, 01:03

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 answered 06 Jun '16, 02:17

Hi, How does writing the ternary form differently help? I didn't understand that part. Thanks! answered 06 Jun '16, 12:20

@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 answered 06 Jun '16, 18:38
