PROBLEM LINK:
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.