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.
Submitting an official solution before solving the problem yourself is a bannable offence.
- Use dynamic programming over the digits of
and
, 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:
- Compute the number of solutions to the whole problem and relevant subproblems.
- To produce the pairs, repeat the recursion and use the memoization table to avoid processing empty branches.
- Let's define the subproblem of size
as the original problem restricted to the
least significant digits of
.
- Let
denote the numbers
restricted to the
least significant digits, including possible leading zeros in
and
.
- A subproblem of size
also needs the following input:
, indicating if there is a leading zero in
at position
,
, the carry (
or
) at position
produced by
,
, the set of forbidden digits for
, and
, the set of forbidden digits for
.
- Note that
is uniquely determined by the other parameters and the digits in
.
- Let's label each recursion level by its corresponding value
.
- The solution of a subproblem of size
can be constructed using the solutions of the subproblems of size
as follows:
- At the
level of recursion, loop through all acceptable digits of
and
at position
and through all acceptable values of
and
.
- Inside the loop construct the corresponding values of
,
,
and
and recurse to the
level providing these values as input to the recursive call.
- Use the values returned from the
level and combine them with the acceptable digits at the
level to obtain the solution at the
level. Or, when computing the number of solutions, just sum up the returned values.
- At the
- The complete solution of the original problem is composed of the solutions of two subproblems with parameters:
length of
,
- (1)
or (2)
,
,
the set of digits in
.
- The memoization table keeps the number of solutions of subproblems for all combinations of
,
,
,
,
.
- The size of the table is at most
.
- The complexity is
. However, the big constant factor of
plays a significant role in any implementation.
- As there are only
digits available, use bitmaps to represent subsets of forbidden digits in
and
.
Comments