You are not logged in. Please login at www.codechef.com to post your questions!

×

LISDIGIT - Editorial

2
7

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

Setter
Tester

This question is marked "community wiki".

asked 21 Jan '17, 19:11

alex_2oo8's gravatar image

7★alex_2oo8
3841611
accept rate: 28%

edited 10 Aug '18, 15:45

admin's gravatar image

0★admin ♦♦
19.7k350498541


The setters solution is wrong in the editorial

link

answered 23 Jan '17, 11:40

nickzuck_007's gravatar image

3★nickzuck_007
191621
accept rate: 14%

@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?

link

answered 26 Jan '17, 18:07

vijju123's gravatar image

4★vijju123 ♦♦
15.2k11860
accept rate: 18%

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.

link

answered 27 Jan '17, 08:58

oddant1's gravatar image

0★oddant1
1
accept rate: 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...

link

answered 12 Feb '17, 12:01

trulyacerbic's gravatar image

2★trulyacerbic
1
accept rate: 0%

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

link

answered 13 Feb '17, 20:45

rak_9792's gravatar image

2★rak_9792
112
accept rate: 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.

link

answered 18 Feb '17, 12:15

rgvg's gravatar image

0★rgvg
1
accept rate: 0%

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

link

answered 27 Feb '17, 16:01

ckeshavabs's gravatar image

2★ckeshavabs
1
accept rate: 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

link

answered 20 Jun '17, 22:45

vivek091195's gravatar image

0★vivek091195
1
accept rate: 0%

test cases seem wrong

link

answered 18 Aug '17, 09:24

tomatovspotato's gravatar image

0★tomatovspotato
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); } }

link

answered 21 Aug '17, 15:26

atulpt01's gravatar image

0★atulpt01
1
accept rate: 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.

link

answered 23 Oct '17, 22:53

faded4k's gravatar image

4★faded4k
262
accept rate: 14%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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