UpdownNumbers
SRM 829 · 2022-05-10 · by misof
Problem Statement
A number is an up-number if we can erase all but S of its digits in such a way that the remaining S digits form a strictly increasing sequence.
For example, 12141176 is an up-number if S = 4 (e.g., we can produce the sequence 1 2 4 6) but it's no longer an up-number if S = 5.
Similarly, a number is a down-number if we can do the same for a strictly decreasing sequence of S digits.
And finally, a number that is both an up-number and a down-number is called an updown-number.
Count all positive integers with exactly D decimal digits that are updown-numbers. Return that count modulo 10^9 + 7.
Constraints
- D will be between 1 and 100, inclusive.
- S will be between 1 and 10, inclusive.
1 1 Returns: 9
For S = 1 each number is an updown-number. There are nine positive integers with exactly 1 digit: the numbers 1 through 9.
3 2 Returns: 525
For S = 2 the numbers that are not updown-numbers are precisely the numbers with digits in sorted order (counting both non-decreasing and non-increasing order as "sorted"). We can enumerate and check all three-digit integers to verify this answer.
20 2 Returns: 986881317
We can also be smarter and get the answers for S = 2 by doing some combinatorics to count the numbers with digits in sorted order, and then subtracting that count from the count of all D-digit numbers.Make sure to compute and return the answer using the right modulus.
8 5 Returns: 0
It's reasonably easy to show that there cannot be any 8-digit updown-numbers for S = 5: if we color any 5-digit increasing subsequence red and any 5-digit decreasing subsequence blue, there cannot be more than one number that's both red and blue.
8 3 Returns: 73017588
Submissions are judged against all 76 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class UpdownNumbers with a public method int count(int D, int S) · 76 test cases · 2 s / 256 MB per case