Passwords
TCO10 Round 3 · 2010-04-11 · by gojira_tc
TCO10 Round 3 · 2010-04-11 · by gojira_tc · Dynamic Programming, Math
Problem Statement
Problem Statement
A password is a sequence of alphanumeric characters. Count the number of different passwords of length N which contain at least L lowercase characters, at least U uppercase characters and at least D digits. Return this number modulo 1,000,000,009.
Constraints
- N will be between 1 and 200,000, inclusive.
- L will be between 0 and N, inclusive.
- U will be between 0 and N, inclusive.
- D will be between 0 and N, inclusive.
Examples
0)
2 0 0 2 Returns: 100
The only valid passwords are those consisting of digits only. There are 100 2-digit sequences.
1)
3 1 1 1 Returns: 40560
A valid password will contain exactly one lowercase and one uppercase letter and one digit. Since they can come in any order, there are 3!*26*26*10 = 40560 possible combinations.
2)
4 1 1 1 Returns: 5029440
This time, the exact number of characters of each type is undefined.
3)
10 1 3 3 Returns: 818019214
4)
5 2 2 2 Returns: 0
Submissions are judged against all 71 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class Passwords with a public method int countValid(int N, int L, int U, int D) · 71 test cases · 2 s / 256 MB per case