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

×

DIGITLIS - Editorial

1
1

PROBLEM LINK:

Contest
Practice

Author: Alexey Zayakin
Testers: Hasan Jaddouh
Editorialist: Alexey Zayakin

DIFFICULTY:

Easy-Medium

PREREQUISITES:

DP, bitmasks, 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 the count of different $n$-digit numbers that correspond to this $LIS$ array.

QUICK EXPLANATION:

Use dynamic programming (add digits one by one). All the information we want to know about previous digits is for every length $len$ ― the smallest digit $d$ such that there exists a $LIS$ of length $len$ that ends with digit $d$.

EXPLANATION:

Consider the algorithm of finding the longest increasing subsequence described in wikipedia. It processes the digits one by one and all the information stored about the processed digits is the array $M$. Here we will define the array $M$ to store the value $X[k]$ itself instead of the index $k$ as described in wikipedia.

The state of the above mentioned algorithm can be described with length of already processed prefix of digits and the array $M$. Let's try to figure out how big the array $M$ can be. It stores a strictly increasing sequence of digits. As we have only ten different digits, naturally its length cann't be greater than ten. Additionaly, given that array $M$ stores a strictly increasing sequence, all its elements are different and thus it can be threated as a subset of digits. This gives us a nice and convienient way to enumerate all the possible arrays $M$, as well as their total count is just $2^{10} = 1024$.

Now we will build a dynamic programming solution based on the above observations. The state of the DP will be pair $(pref, mask)$, where $pref$ is the length of already processed prefix of digits and $mask$ is a bitmask on ten bits that encodes the array $M$. The value of the DP will answer the question "How many different numbers of length $pref$ will generates an array $M$ that is encoded in $mask$ and have $LIS$ array equal to the one provided in the input?".

Now let's speak about the DP transitions. Any transition will be just one step of the algorithm, i.e. addition of one digit. So, for every state there will be ten different tansitions (using digits $0, 1, \dots, 9$). After fixing the digit we are going to add (denote it with $d$), as per the algorithm, we will search for the largest index $j$ such that $M[j] < d$. This gives us the information that the $LIS$ that ends with a newly added digit $d$ has length $(j + 1)$. Here we should check that this value matches with the one in the provided $LIS$ array (if it doesn't we just ignore this transition). Now we update the array $M$ with $M[j + 1] = d$ and process the transition:
$DP[pref + 1, newmask] \mathrel{+}= DP[pref, mask]$, where $newmask$ is the encoded version of the updated array $M$.

The last thing to discuss are the base/final states. Our DP has just one base state ― $DP[0, 0] = 1$, i.e. at the very beginning we have not processed any digits and the array $M$ is empty. The final states are just $DP[n, mask]$ for every $mask$, beacuse we actually do not care about the final array $M$, we just want for the $LIS$ arrays to match and this is guaranteed by skipping wrong transitions.

Time Complexity:

$\mathcal{O}(2^B \cdot B \cdot n)$ per test case, where $B$ is the base of the numeral system we are working with. In this problem $B = 10$.

AUTHOR'S AND TESTER'S SOLUTIONS:

Setter
Tester

This question is marked "community wiki".

asked 21 Jan '17, 20:41

alex_2oo8's gravatar image

7★alex_2oo8
3841612
accept rate: 28%

edited 23 Jan '17, 00:01

admin's gravatar image

0★admin ♦♦
19.8k350498541


@Alex_2oo8 would you please tell me or give me any use case where i am going wrong with my dp Solution Link

I didn't use bitmask .

link

answered 23 Jan '17, 00:34

selfcompiler's gravatar image

3★selfcompiler
10127
accept rate: 0%

edited 23 Jan '17, 00:35

For example: "1 3 1 2 1", the correct answer is 156.

(23 Jan '17, 01:16) alex_2oo87★

@Alex_2oo8 Can you please explain the above algorithm using an example to make it more understandable?

link

answered 23 Jan '17, 10:02

suraj23patel's gravatar image

3★suraj23patel
112
accept rate: 0%

edited 23 Jan '17, 10:02

@Alex_2oo8 How is 1 3 1 2 1 a valid input? For example, at position 2 the LIS is 3, but before that we've only got just one number so the maximum LIS at position2 would be 2

link

answered 23 Jan '17, 14:50

aditya211935's gravatar image

4★aditya211935
111
accept rate: 0%

The first number is the number of testcases (1), the second is the value of $n$ for the first testcase (3), three following numbers (1 2 1) describe the $LIS$ array.

(23 Jan '17, 15:18) alex_2oo87★

I can't understand how is array M being mapped to bitmask. The array M may contain integers from 0-9 .Can someone explain how is the mapping done in setter's solution.

link

answered 23 Jan '17, 15:06

prayas_sahni's gravatar image

1★prayas_sahni
311
accept rate: 0%

If the array $M$ has length $k$, i.e. the $LIS$ so far is $k$, then it is mapped to bitmask $\displaystyle 2^{M_1} + 2^{M_2} + \dots + 2^{M_k}$.

(23 Jan '17, 15:21) alex_2oo87★

Just to make things clear, when we are updating the array we have to set the bit corresponding to new digit?.

(23 Jan '17, 15:57) prayas_sahni1★

If you update the array as $M[j] = d$, the you should set the bit corresponding to $d$ and unset the bit corresponding to the old value of $M[j]$ (in case there was an old value).

(23 Jan '17, 16:24) alex_2oo87★

I also hard to understand the editorial

link

answered 24 Jan '17, 15:58

liuweiming1997's gravatar image

3★liuweiming1997
1
accept rate: 0%

would you expaint for what is your meaning to init state[][]

link

answered 24 Jan '17, 16:13

liuweiming1997's gravatar image

3★liuweiming1997
1
accept rate: 0%

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,683
×1,672
×281
×52
×36
×2

question asked: 21 Jan '17, 20:41

question was seen: 1,913 times

last updated: 24 Jan '17, 16:13