Count by state
When the rules look at two things at once, each combination of them is one state, and you count how many paths end in each. About 15 minutes.
A record with two rules
An attendance record is a string with one letter per day: present, absent or late. A record is good if it has fewer than two absences in total, and never three late days in a row. How many good records of length n are there?
You could write out all three-to-the-n strings and test each one, but that is hopeless for long records. Instead, notice that the rules only watch two things.
Six states, three moves
Absences so far is 0 or 1, and lates at the end is 0, 1 or 2. That gives six states, and for each one you keep how many good records end in it. Adding a day moves records along arrows.
A present day resets the lates to zero. A late day adds one to the lates, but is not allowed from two. An absent day is only allowed from zero absences, and it moves the record to one absence with zero lates. The answer is the total of all six counts, taken modulo 1,000,000,007 because the numbers grow huge.
MOD = 10**9 + 7 cnt = [[1, 0, 0], [0, 0, 0]]
One day: present (no absence, 0 late), late (no absence, 1 late) or absent (one absence, 0 late). That is 3 good records.
A record has one absence and ends with two late days. A present day follows. Which state is it in afterwards?
- AOne absence, 0 late
- BOne absence, 2 late
- CNo absences, 0 late
Show the answer
One absence, 0 late. A present day resets the late streak to zero, and the absence count does not change.
Attendance records
An attendance record is a string with one letter per day: P (present), A (absent) or L (late). A record is good if it has fewer than two A's in total and never has three L's in a row. Given the length n, return how many good records there are, modulo 1,000,000,007.
n = 3 → 19
1 ≤ n ≤ 100,000