CHEFVEC - Editorial

cook65
digit-dp
dynamic-programming
editorial
hard
memoization

#1

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


#2

@shahriarsust13

http://pastie.org/10647272


#3

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


#4

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