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

×

CHEFVEC - Editorial

PROBLEM LINK:

Practice
Contest

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

DIFFICULTY:

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:

Author
Tester

This question is marked "community wiki".

asked 20 Dec '15, 23:50

pushkarmishra's gravatar image

4★pushkarmishra
1.3k156381
accept rate: 4%

edited 09 Feb '16, 13:54

admin's gravatar image

0★admin ♦♦
19.0k348495531

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

(22 Dec '15, 19:38) shahriarsust132★

Don't you think the editorial should be more detailed?

link

answered 22 Jan '16, 19:33

rohanagarwal's gravatar image

5★rohanagarwal
1008
accept rate: 5%

link

answered 22 Dec '15, 19:49

mgch's gravatar image

6★mgch
300920
accept rate: 21%

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 ?

link

answered 20 May, 03:55

dgupta's gravatar image

0★dgupta
175
accept rate: 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?

link

answered 20 May, 13:20

dgupta's gravatar image

0★dgupta
175
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:

×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