PROBLEM LINK:
Author and Editorialist: Hussain Kara Fallah
Tester: Michael Nematollahi
PREREQUISITES:
dynamic programming, inclusion-exclusion
PROBLEM:
You are given N intervals [L_1, R_1], [L_2, R_2], \ldots, [L_N, R_N].
Consider N integers x_1, x_2, \ldots, x_N such that:
-
x_i \in [L_i, R_i] for each valid i
-
all decimal digits of S = x_1 + x_2 + x_3 + \ldots + x_N (without leading zeroes) lie between A and B inclusive
In how many different ways can you pick the sequence x_1, x_2, \ldots, x_N? Since this number may be very large, compute it modulo 10^9+7.
- 1 \le N \le 7
- 0 \le A \le B \le 9
- 0 \le L_i \le R_i \lt 10^9 for each valid i
EXPLANATION:
Let’s try to make our problem simpler.
Let’s say we have N numbers (R_1,R_2,R_3\, ,..., \,R_n) and we want to choose x_1, x_2, \ldots, x_N such that:
x_i \leq R_i for each valid i
Now we have N conditions also.
The i^{th} condition states that x_i \geq L_i and must be satsified.
This reformulation of the problem was written so the problem makes sense in the context of inclusion-exclusion. If you are not familiar with it, you should read about it. Otherwise, the solution won’t be clear.
So if we counted tuples (x_1, x_2, \ldots, x_N) satisfying x_i \leq R_i for each valid i, obviously some of them won’t satisfy some of the conditions. So for each subset of conditions, we should count how many tuples violating the whole subset of conditions.
For each subset of conditions S (maybe me empty as well).
we count how many tuples (x_1, x_2, \ldots, x_N) satisfying x_i \leq V_i for each valid i
In case i^{th} condition is present in the subset V_i=L_i-1
Otherwise, V_i=R_i
Of course, in all mentioned cases we keep the condition the tuples must satisfy that all decimal digits of S = x_1 + x_2 + x_3 + \ldots + x_N (without leading zeroes) lie between A and B inclusive.
This isn’t enough explanation if you don’t know inclusion-exclusion. It makes it possible to the sum the tuples for each subset such that we get our final answer in the end.
Now how to solve the smaller problem (will be solved for each subset)?
First, extend all V_i so all of them contain 9 digits. Let’s imagine our numbers (x_1,x_2,x_3 \ldots) stacked on top of each other.
Let’s build our sum digit by digit, from least significant digit to most. So our recursive function will process each column of digits (assuming numbers are stacked). For each column we assign digits to our numbers one by one. This approach gives us the possibility to come up with a DP solution.
What do we need to keep track of?
DP[pos][current][mask][sum][carry]
pos denotes the index of the digit we are building in our sum (which column we are processing).
current denotes which number we are setting its digit corresponding to the current column.
mask we keep the state of each number with respect to its correponding boundary in this mask. It represents N boolean flags with each bit acting as one. i^{th} bit would be set to 1 if x_i \leq V_i otherwise it’s set to 0. Because we need to make sure that our numbers don’t exceed the fixed boundary. Since we are building numbers column by column we need to know the state of each number in the step before, so when we proceed to next column we pass this information.
sum denotes the current digit of the sum, which is the sum of all assigned digits in the current column modulo 10, so it has only 10 possible states [0 \ldots 9].
We can now make sure our sum’s digits belong to the given interval [A,B] by checking the sum we have after finishing each column.
carry denotes the carry, we modify it according to our sum changes, the normal way we sum numbers on paper. In fact it would be the sum of all digits divided by 10 (integer division). Carry has 7 possible states in our case [0 \ldots 6]
At each state we run a loop [0 \ldots 9] to set a digit to the current number in the being processed column.
Since we are building our sum from least significant digit to most. We should handle the case when we have leading zeroes in our sum and (A>0). In such case we cannot just break or return 0 in our dp because leading zeroes are discarded. In my implementation I added another dimension \big[ 2 \big] to the dp so I avoid writing a lot of ifs. However it’s not needed.
Complexity: (2^N * (9 \, * \, N \, * \, 2^{N} \, * \, 10 \, * \, 6 \, * \, 10))