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

×

# PROBLEM LINK:

Author: Misha Chorniy
Tester: Jingbo Shang
Editorialist: Pushkar Mishra

Medium-Hard

# PREREQUISITES:

Dynamic Programming

# PROBLEM:

Given are two arrays $S[1..N]$ and $X[1..N]$. We have to tell how many vectors $V$ of length $N$ exist such that $V_i \geq X_i$ if $S_i = 1$ and $V_i \leq X_i$ if $S_i = 0$.

# EXPLANATION:

The key insight for this problem is that we can write the given $N$ numbers into a matrix of $N*D$ size, where $D = 18$ and then do a digit-by-digit DP.

We maintain a 6 state DP $dp[mask][now][pos][pre][sum][exist]$. The states are:

• $mask$ ($0$ to $2^8-1$): We need a $2^N$ mask to record whether the $i^{th}$ number satisfies the contraints based on $S_i$ and $X_i$, i.e., the greater than or lesser than constraint.
• $now$ and $pos$: putting ($now + 1$) digits in first $pos$ elements and $now$ digits in last ($N - pos$) elements.
• $pre$: carry bit from $now^{th}$ digit to ($now+1)^{th}$ digit, i.e., $(V[1]["now"] + V[2]["now"] + ... + V[n]["now"])$ $div$ $10$.
• $sum$: sum of digits which stand on $now^{th}$ position in the first $pos$ elements.
• $exist$: Can be one of three types: 2 if there was 47, 1 if digit in $now+1$ is 4, 0 otherwise.

We can now give the rucurrence for this DP.
When $pos = N$, we should iterate the carry bit(add) from ($now-1)^{th}$ digit to $now^{th}$ digit and check if $(sum+add)/10$ = $pre$. If yes, then the transition is correct. If it is, then we add the DP for $now-1$ to an accumulating variable $ret$. We finally return $ret$ return.

When $pos < N$, we have the following recurrences:

• If $S[pos] = 0$
Let $r$ = $now^{th}$ digit in $pos^{th}$ number, then
$dp[mask][now][pos][pre][sum][exist]$ += $dp[mask$^ $(1 << pos)][now][pos+1][pre][sum + digit][exist]$
for $digit$ = 0 to $r$.

• If $S[pos] = 1$
Let $l$ = $now^{th}$ digit in $pos^{th}$ number, then
$dp[mask][now][pos][pre][sum][exist]$ += $dp[mask$^ $(1 << pos)][now][pos+1][pre][sum + digit][exist]$
for $digit$ = $l+1$ to $9$.

Please follow Setter's solution for implementation details.

# COMPLEXITY:

$\mathcal{O}(2^N*N^3*D)$ which a constant of complexity equivalent to 300.

# SAMPLE SOLUTIONS:

This question is marked "community wiki".

asked 20 Dec '15, 23:50

1.3k156381
accept rate: 4%

0★admin ♦♦
19.0k348495531

Author and Tester solution link is not working. Any alternate link please?

(22 Dec '15, 19:38)

 1 Don't you think the editorial should be more detailed? answered 22 Jan '16, 19:33 100●8 accept rate: 5%
 0 answered 22 Dec '15, 19:49 6★mgch 300●9●20 accept rate: 21%
 0 What is the meaning of the following line? now and pos: putting (now+1) digits in first pos elements and now digits in last (N−pos) elements. Why are we doing this? What happens on incrementing the now + 1 th digit ? answered 20 May, 03:55 0★dgupta 17●5 accept rate: 0%
 0 now and pos: putting (now+1) digits in first pos elements and now digits in last (N−pos) elements.This step is not clear .optimal substructure is not explained .Can anyone explain this step? answered 20 May, 13:20 0★dgupta 17●5 accept rate: 0%
 toggle preview community wiki:
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:

×14,366
×1,754
×1,206
×105
×104
×66

question asked: 20 Dec '15, 23:50

question was seen: 1,510 times

last updated: 20 May, 13:20