PROBLEM LINK:Author: Alexey Zayakin DIFFICULTY:Cakewalk PREREQUISITES:Constructive algorithms, longest increasing subsequence PROBLEM:For an $n$digit number $x$ we define the $LIS$ array as follows: $i$th element of the array is the length of the longest strictly increasing subsequence of numbers $x$ digits that ends with the $i$th digit. Given the $LIS$ array of some $n$digit number, find any $x$ that corresponds to this $LIS$ array. QUICK EXPLANATION:We can interpret the array in the input as array of digits of $x$, i.e. the $i$th digit of $x$ will be equal to the $i$th element of the $LIS$ array. EXPLANATION:Let's denote the $i$th digit of number $x$ with $d_i$, i.e. $x = \overline{d_1 d_2 \dots d_n}$. What does it means that $LIS[i] = k$? It means that there exists a sequence $p_1 < p_2 < \dots < p_{k  1} < i$ such that $LIS[p_1] = 1, LIS[p_2] = 2, \dots, LIS[p_{k  1}] = k  1$ and digits $d_{p_1}, d_{p_2}, \dots, d_{p_{k  1}}, d_i$ form a strictly increasing sequence. The simplest way to make this sequence increasing is to simply assign $d_{p_1} = 1, d_{p_2} = 2, \dots, d_{p_{k  1}} = k  1, d_i = k$ or in other words $d_j = LIS[j]$. Given that $n \le 9$, it follows that $1 \le LIS[i] \le 9$ and thus all the values of the $LIS$ array are indeed nonzero digits. Time Complexity:$\mathcal{O}(n)$ per test case. Bonus:Can you solve this problem with constraints $n \le 100$? AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 21 Jan '17, 19:11

The setters solution is wrong in the editorial answered 23 Jan '17, 11:40

I ran setters code and it IS giving me right answer. Further I also checked it on the test cases given in satisfy. Further, I solved the problem myself and can warrant that the solution is correct. Did you read the editorial to understand the logic? answered 26 Jan '17, 18:07

The setter's code shows that this isn't so much a programming problem as it is a problem testing your ability to understand the concept presented in the problem. All the code does is reprint the given input because in order for the input to be valid it must itself fulfill the output requirements. If it didn't it would be impossible to create a valid output. answered 27 Jan '17, 08:58

I fail to comprehend the explanation. Can someone show me full mathematical proof? I understand part where "p1 < p2 < ⋯< pk−1 < i and digits dp1,dp2,…,dpk−1,di form a strictly increasing sequence"  this is basically definition of increasing subseq. But why for LIS[i]=k to happen is it sufficient that LIS[pk−1]=k−1? It is necessary I see, but how is it sufficient? Mah brain... answered 12 Feb '17, 12:01

This doesn't seem to work for the test case: 1121315. Can someone explain. answered 13 Feb '17, 20:45

What's the difference between index 1 and 6 in test case 5? Why does index 6 recognize 0 1 as a valid sequence but index 1 does not, when the 1st and 6th digits are the same. answered 18 Feb '17, 12:15

Isn't this question too basic? What I have done is just read the input, and display it as it is, and it gets accepted. For e.g., if the input is 1,2,3,4,2,1,3,5 then, one of the possible outcome can be same as the input, that is 12342135 answered 20 Jun '17, 22:45

include <stdio.h>int main() { int t; scanf("%d", &t); while(t) { int temp, i, n, s; scanf("%d", &n); for(i = 0, s = 0; i < n; i++) { scanf("%d", &temp); s = 10 * s + temp; } printf("%d\n", s); } } answered 21 Aug '17, 15:26

The trick is, the LIS array itself is a number that satisfies the LIS array(the number itself). You just take and store the LIS array and then print it out(without the spaces ofcourse) to get a correct answer and is the fastest way. It is possible to derive other solutions as well but that would obviously take more time after a little research you can infer it. ****But the converse is false. Also the value of a LIS array member has to lie between 0 and (highest number occurred to its left+1) for its validity. eg. [1 2 5] is an invalid LIS array as the 3rd element can only have values between 0 and (2+1)=3 where it has value of 5. answered 23 Oct '17, 22:53
