×

# CHEFVEC - Editorial

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$.

# COMPLEXITY:

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

# SAMPLE SOLUTIONS:

This question is marked "community wiki".

1.3k156481
accept rate: 4%

19.6k349497539

(22 Dec '15, 19:38)

 1 Don't you think the editorial should be more detailed? answered 22 Jan '16, 19:33 100●9 accept rate: 5%
 0 answered 22 Dec '15, 19:49 6★mgch 345●11●27 accept rate: 23%
 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,182
×2,020
×1,321
×107
×105
×66

question asked: 20 Dec '15, 23:50

question was seen: 1,647 times

last updated: 20 May, 13:20