I'm having trouble understanding the solution to a coding contest problem.
Student Attendance Problem
Suppose a student's attendance is recorded as a string, e.g.
where the letters represent Present, Late, and Absent. A reward is given to the student who satisfies the following criteria,
- No more than one absence.
- No triple consecutive lateness, e.g.
Given an attendance record of length $n$, then, how many rewardable records exist?
For example, for $n=2$, only
AA fails to be rewarded, of $3^2$ possible strings, so the answer is $8$.
The official solution attempts to build a recurrence relation, starting with this diagram:
It explains: Let $f[n]$ represent the number of rewardable cases for a string of length $n$. Let's divide into two cases,
- Strings ending with
- Strings ending with
P. (I don't know why it says
Nin the diagram; typo, I think.)
It's easy to see that the second case is rewardable as long as the piece preceding the
P, $f[n-1]$, is rewardable.
L case must be split into four pieces, as shown. There, the author claims that the only troublesome piece is the last, ending the string in
LLL. His exact words are,
Out of the four combinations possible at the end, the fourth combination, ending with a $LL$ at the end leads to an unrewardable string. But, since we've considered only rewardable strings of length $n-3$, for the last string to be rewardable at length $n-3$ and unawardable at length $n-1$, it must be preceded by a $PP$ before the $LL$.
Thus, accounting for the first string [left branch] again, all the rewardable strings of length $n-1$, except the strings of length $n−4$ followed by $PLL$, can contribute to a rewardable string of length $n$. Thus, this string accounts for a factor of $f[n-1] - f[n-4]$ to $f[n]$.
Thus, the recurring relation becomes:
$$f[n] = 2f[n-1] - f[n-4]$$
I was hoping someone could put this explanation in their own words, because I don't understand this author's. And he has made several typos in his explanation already, so I'm not sure I trust this explanation.
Another thing I don't understand is why the first of the four cases isn't also problematic, since if the $n-5$th and $n-4$th characters were
L, then we'd also have an unrewardable string.
Any hints as to untangling the author's explanation would be appreciated. Thank you.
P.S. The author is intentionally ignoring
A at this stage, to be considered separately.