PROBLEM LINK:Author and Editorialist: Hussain Kara Fallah PREREQUISITES:dynamic programming, inclusionexclusion 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:
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$.
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 inclusionexclusion. 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_i1$ 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 inclusionexclusion. 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))$ AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 24 Dec '18, 17:14

LL dp[7][9000005]; //why this will not work as index and sum ? answered 10 Feb, 11:04
