Editorial for ICPC NAQ 2016 F - Free Desserts

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Use dynamic programming over the digits of $a$ ~a~ and $b$ ~b~, from left to right, to count the number of solutions.
Using a recursive function with memoization (as opposed to an iterative DP), simplifies reconstruction of the pairs of integers we need to output.
The solution proceeds in two steps:
1. Compute the number of solutions to the whole problem and relevant subproblems.
2. To produce the pairs, repeat the recursion and use the memoization table to avoid processing empty branches.
Let's define the subproblem of size $k$ ~k~ as the original problem restricted to the $k$ ~k~ least significant digits of $P$ ~P~.
Let $a', b', P'$ ~a', b', P'~ denote the numbers $a, b, P$ ~a, b, P~ restricted to the $k$ ~k~ least significant digits, including possible leading zeros in $a$ ~a~ and $b$ ~b~.
A subproblem of size $k$ ~k~ also needs the following input:
- $LZa(k)$ ~LZa(k)~, indicating if there is a leading zero in $a'$ ~a'~ at position $k$ ~k~,
- $Cy(k)$ ~Cy(k)~, the carry ( $0$ ~0~ or $1$ ~1~) at position $k$ ~k~ produced by $a'+b'$ ~a'+b'~,
- $Fa(k)$ ~Fa(k)~, the set of forbidden digits for $a'$ ~a'~, and
- $Fb(k)$ ~Fb(k)~, the set of forbidden digits for $b'$ ~b'~.
Note that $Fb(k)$ ~Fb(k)~ is uniquely determined by the other parameters and the digits in $P$ ~P~.
Let's label each recursion level by its corresponding value $k$ ~k~.
The solution of a subproblem of size $k$ ~k~ can be constructed using the solutions of the subproblems of size $k-1$ ~k-1~ as follows:
- At the $k^\text{th}$ ~k^\text{th}~ level of recursion, loop through all acceptable digits of $a'$ ~a'~ and $b'$ ~b'~ at position $k$ ~k~ and through all acceptable values of $Cy(k)$ ~Cy(k)~ and $LZa(k)$ ~LZa(k)~.
- Inside the loop construct the corresponding values of $Fa(k-1)$ ~Fa(k-1)~, $Fb(k-1)$ ~Fb(k-1)~, $Cy(k-1)$ ~Cy(k-1)~ and $LZa(k-1)$ ~LZa(k-1)~ and recurse to the $(k-1)^\text{th}$ ~(k-1)^\text{th}~ level providing these values as input to the recursive call.
- Use the values returned from the $(k-1)^\text{th}$ ~(k-1)^\text{th}~ level and combine them with the acceptable digits at the $k^\text{th}$ ~k^\text{th}~ level to obtain the solution at the $k^\text{th}$ ~k^\text{th}~ level. Or, when computing the number of solutions, just sum up the returned values.
The complete solution of the original problem is composed of the solutions of two subproblems with parameters:
- $k =$ ~k =~ length of $P$ ~P~,
- (1) $LZa(k) = \texttt{true}$ ~LZa(k) = \texttt{true}~ or (2) $LZa(k) = \texttt{false}$ ~LZa(k) = \texttt{false}~,
- $Cy(k) = 0$ ~Cy(k) = 0~,
- $Fa(k) = Fb(k) =$ ~Fa(k) = Fb(k) =~ the set of digits in $P$ ~P~.
The memoization table keeps the number of solutions of subproblems for all combinations of $k$ ~k~, $LZa(k)$ ~LZa(k)~, $Cy(k)$ ~Cy(k)~, $Fa(k)$ ~Fa(k)~, $Fb(k)$ ~Fb(k)~.
The size of the table is at most $18 \cdot 2 \cdot 2 \cdot 1024 \cdot 1024 = 75\,497\,472$ .
The complexity is $\mathcal O(\log P)$ ~\mathcal O(\log P)~. However, the big constant factor of $\approx 10^6$ ~\approx 10^6~ plays a significant role in any implementation.
As there are only $10$ ~10~ digits available, use bitmaps to represent subsets of forbidden digits in $a$ ~a~ and $b$ ~b~.

Comments

There are no comments at the moment.