Minimal Subset Difference
Contest: VK Cup 2018 - Round 2
Difficulty rating: 3200
Tags: dp

We call a positive integer x a k-beautiful integer if and only if it is possible to split the multiset of its digits in the decimal representation into two subsets such that the difference between the sum of digits in one subset and the sum of digits in the other subset is less than or equal to k. Each digit should belong to exactly one subset after the split.

There are n queries for you. Each query is described with three integers l, r and k, which mean that you are asked how many integers x between l and r (inclusive) are k-beautiful.

Input format:
The first line contains a single integer n (1 ≤ n ≤ 5·104), indicating the number of queries.

Each of the next n lines describes a query, containing three integers l, r and k (1 ≤ l ≤ r ≤ 1018, 0 ≤ k ≤ 9).

Output format:
For each query print a single number — the answer to the query.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
If 1 ≤ x ≤ 9, integer x is k-beautiful if and only if x ≤ k.

If 10 ≤ x ≤ 99, integer x = 10a + b is k-beautiful if and only if |a - b| ≤ k, where a and b are integers between 0 and 9, inclusive.

100 is k-beautiful if and only if k ≥ 1.

Example input:
10
1 100 0
1 100 1
1 100 2
1 100 3
1 100 4
1 100 5
1 100 6
1 100 7
1 100 8
1 100 9

Example output:
9
28
44
58
70
80
88
94
98
100

Example input:
10
1 1000 0
1 1000 1
1 1000 2
1 1000 3
1 1000 4
1 1000 5
1 1000 6
1 1000 7
1 1000 8
1 1000 9

Example output:
135
380
573
721
830
906
955
983
996
1000

Editorial:
Let f(x) be the minimal subset difference mentioned in the problem statement. The problem seems like a regular digit DP problem. However, it's a bit hard to reduce the number of DP states. Let's take a careful consideration.
For a given integer x, we can use knapsack DP to determine f(x). Denote the sum of digits of x as s(x). You can just calculate whether there is a subset such that the sum of the subset is a fixed number y, and then find the maximal y $$( 0 \leq y \leq \frac { s ( x ) } { 2 } )$$ which concludes f(x) = s(x) - 2y. By the way, this type of knapsack DP could be implemented by bitwise operation.
If we defined dp(len, sum, state) as the number of integers x such that the length of x is len, the digit sum is sum, and the knapsack DP array is state (an array only consisting 0 and 1, which could be represented as bit vector), the problem would be difficult to solve. For example, to represent x = 88888888899999999, a case of f(x) = 0, the length of state might be 73, which is a bit long vector. Although most of states satisfy dp(len, sum, state) = 0, there are still many states which might be used.
You may notice the order of digits is unnecessary for the knapsack DP. If we defined state as the number of appearance of digits 1, 2, ..., 9 (digit 0 is unnecessary), the number of states would be $${ \binom { 18 + 9 } { 9 } } \approx 5 \cdot 10 ^ { 6 }$$. Hence, we can apply knapsack DP for each state first and then calculate for digit DP.
Here are more details. Let's redefine dp(len, k, state) as the number of ways to arrange the lowest len digits of x such that f(x) = k and the other digits (higher than the lowest len digits) form the state (i. e. the number of appearance of digits 1, 2, ..., 9). We firstly search all the states such that the total number of appearance  ≤ 18 and f(x) = k, and then set dp(0, k, state) = 1. After searching, we calculate dp(len, k, new state) from dp(len - 1, k, state) > 0 by enumerating the len-th digit.
However, the number of dp(len, k, state) > 0 is still too large to calculate for digit DP. You should notice that in decimal representation it always has 0 ≤ f(x) ≤ 9 for any integer x. Furthermore, because of the distribution of digits, most of states are in cases of f(x) = 0, 1 (you can make a knapsack DP to prove). In addition, it is easy to show f(x) and s(x) always have the same parity, so we can apply inclusion-exclusion principle to solve the problem only in the cases of f(x) ≥ 2 and another counting problem with fixed parity of s(x).
The total time complexity in above is $$\mathcal{O}\left(\binom{L+D}{D}\right) + LDS \log S + n(9-k)L D \log S$$, where L ( = 18) is the maximal length of x, D ( = 9) is the maximal digit, and S ( ≈ 3·104) is the number of distinct states such that there exists dp(len, k, state) > 0 (0 ≤ len ≤ L, 2 ≤ k ≤ 9). However, it can hardly pass the tests with n = 5·104, because we have some fairly worse tests to maximize the times of dp access (e. g. l and r have a lot of 9 as digits and k = 1).
We could make a tradeoff between pretreatment and queries by several ways. For example, define dp(len, k, state, upp) as the similar but it memorizes that the len-th digit is less than upp. If we did that, the total time complexity would be $${ \mathcal { O } } \left( { \binom { L + D } { D } } \right) + LDS\log S + n(9-k)L\log S$$, which is acceptable.
The aforementioned solution is not easy to code; you can use some advanced approach to get accepted, though. Here are bonuses for advanced solutions.
Bonus 1. Solve the problem in case of n = 5·105, 1 ≤ l ≤ r ≤ 1018 with the same limits of time and memory.
Bonus 2. Solve the problem in case of n = 105, 1 ≤ l ≤ r ≤ 10100 (answer in modulo some 32-bit integer) with the same limits of time and memory.