LISDIGIT - Editorial

PROBLEM LINK:

Contest
Practice

Author: Alexey Zayakin
Testers: Hasan Jaddouh
Editorialist: 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* = 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* \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?

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter
Tester

2 Likes

The setters solution is wrong in the editorial

@nickzuck_007

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?

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*=k to happen is it sufficient that LIS[pk−1]=k−1? It is necessary I see, but how is it sufficient?

Mah brain…

This doesn’t seem to work for the test case:
1121315. Can someone explain.

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.

@rak_9792
we must have a 4 in the LIS[] array before hitting the 5 at the end of the array

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

test cases seem wrong

#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
", 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.