×

# LISDIGIT - Editorial

Author: Alexey Zayakin
Editorialist: Alexey Zayakin

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

This question is marked "community wiki".

3841611
accept rate: 28%

19.7k350498541

 0 The setters solution is wrong in the editorial answered 23 Jan '17, 11:40 191●6●21 accept rate: 14%
 0 @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? answered 26 Jan '17, 18:07 15.2k●1●18●60 accept rate: 18%
 0 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 0★oddant1 1 accept rate: 0%
 0 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 1 accept rate: 0%
 0 This doesn't seem to work for the test case: 1121315. Can someone explain. answered 13 Feb '17, 20:45 2★rak_9792 11●2 accept rate: 0%
 0 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 0★rgvg 1 accept rate: 0%
 0 @rak_9792 we must have a 4 in the LIS[] array before hitting the 5 at the end of the array answered 27 Feb '17, 16:01 1 accept rate: 0%
 0 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 1 accept rate: 0%
 0 test cases seem wrong answered 18 Aug '17, 09:24 1 accept rate: 0%

# 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); } }

0★atulpt01
1
accept rate: 0%

 0 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 4★faded4k 26●2 accept rate: 14%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,498
×1,615
×196
×50
×36
×4

question asked: 21 Jan '17, 19:11

question was seen: 3,376 times

last updated: 10 Aug '18, 15:45