Lucky in a range
Tickets are numbered with numbers of 2n digits, with leading zeros: for n = 3 the first ticket is 000000 and the last 999999. A ticket is lucky if the sum of its first n digits equals the sum of its last n. For each query, how many lucky tickets have numbers from L to R inclusive.
Input
The first line holds n and q (1 ≤ n ≤ 9, 1 ≤ q ≤ 5 · 10⁴). Then q lines: L and R (0 ≤ L ≤ R < 10²ⁿ), written without leading zeros.
Output
For each query, the number of lucky tickets on a separate line. It is less than 10¹⁷.
Examples
Example 1
3 5 0 999999 123456 654321 700000 700999 123456 123456 123501 123501
55252 31607 36 0 1
Example 2
1 4 0 99 10 20 55 55 0 0
10 1 1 1
Limits
- Time · Python
- 5000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 8 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
The answer for [L, R] is the difference of the answers for [0, R] and [0, L − 1]. How do you count the lucky numbers from 0 to x without trying them?
2Hint 2
A number is smaller than x if at the first position where they differ its digit is smaller. So the numbers can be split into batches “matches x up to position i, has a smaller digit d at position i, anything after”. How many lucky ones are in such a batch depends only on the sums of the digits already placed.
3The idea
Digit DP. The table ways[r][b] is the number of ways to write r digits with sum b. A batch in the right half: the left half has collected a, the right one already c + d, and the remaining r digits must give a − c − d, which is ways[r][…]. A batch in the left half: the left half has collected s, and r more digits of the left half and the whole right half are free: there are Σt ways[r][t] · ways[n][s + t] lucky ones.
4Walkthrough
There are up to 5 · 10⁴ queries, two passes per query. For a pass to cost O(n) rather than O(10n · 9n), compute in advance for the left half the numbers H[r][s] and their prefix sums over s: the digits d = 0 … xi − 1 give consecutive values of s, and their contribution is one difference. For the right half, prefix sums of ways[r] itself. If on the “tight” path the difference of the sums goes negative, there are no more lucky ones.
4+Solution
5Complexity
Preparation is O(n³ · 100), a query O(n). The numbers are at most 3.3 · 10¹⁶ and fit in 64 bits.
6Common mistakes
- Trying the numbers. This is
wrong.py: on short ranges of six-digit tickets it is fast enough, but already in the fourth test the ranges are wider, and in the fifth the numbers have eighteen digits. - Forgetting R itself. The batches count numbers strictly smaller than x; x is checked at the end of the path.
- L = 0. The answer up to −1 is zero.
- A number without leading zeros. An input of 123 with n = 3 is the ticket 000123: pad it with zeros to 2n digits.