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 non-zero digits.
Time Complexity:
\mathcal{O}(n) per test case.
Bonus:
Can you solve this problem with constraints n \le 100?
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.
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?
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.
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
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);
}
}
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.