 # 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["now"] + V["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
for digit = 0 to r.

• If S[pos] = 1
Let l = now^{th} digit in pos^{th} number, then
for digit = l+1 to 9.

### COMPLEXITY:

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

2 Likes