5
$\begingroup$

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.

PPAPPPPLPPPLPPLLAPPPP

where the letters represent Present, Late, and Absent. A reward is given to the student who satisfies the following criteria,

  1. No more than one absence.
  2. No triple consecutive lateness, e.g. LLL.

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$.

Official Solution

The official solution attempts to build a recurrence relation, starting with this diagram:

enter image description here

It explains: Let $f[n]$ represent the number of rewardable cases for a string of length $n$. Let's divide into two cases,

  1. Strings ending with L.
  2. Strings ending with P. (I don't know why it says N in 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.

However, the 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.

$\endgroup$
  • 2
    $\begingroup$ I think you might mean $8$ for $n=2$ since there are $3^n$ possible records for $n$ days, and thus $9$ records for $n=1$, and with $1$ unacceptable record, there would be $8$ acceptable ones. $\endgroup$ – Franklin Pezzuti Dyer Apr 24 '17 at 22:55
  • $\begingroup$ Yes, that's correct, thanks! $\endgroup$ – Andrew Cheong Apr 25 '17 at 4:44
  • 1
    $\begingroup$ In the cold light of day I am still unable to make sense of this author's method. It may be that it does make sense but because of the lack of clarity, it looks possible that some "fudgery" may have been employed to match the desired answer. I know I'm biased, but I've done a few of these types of recurrences and I feel that my method is, by far, the easiest to understand so I'd stick with that for now if I were you. With a few more different examples you may be able to make sense of our author here but it looks a bit of a mess to me. $\endgroup$ – N. Shales Apr 25 '17 at 12:56
  • 1
    $\begingroup$ Thank you very much, I'll contact the author from here to try to find out what he meant to convey. $\endgroup$ – Andrew Cheong Apr 26 '17 at 8:11
  • $\begingroup$ FYI this is equivalent to problem 191 in project Euler. (there the role of L and A are swapped.) projecteuler.net/problem=191 If you bother to write the code to solve that problem numerically, then you can access their forum to see lots more DIFFERENT recurrences people used to solve this. however IMHO the accepted answer has one of the cleanest explanations. $\endgroup$ – antkam Nov 20 '18 at 14:09
2
$\begingroup$

It really is a lot easier than the author makes out.

You have $3$ possible mutually exclusive and exhaustive endings to valid sequences of length $n$

$$(\text{valid sequence length $n-1$})\, \text{P}$$ $$(\text{valid sequence length $n-2$})\, \text{PL}$$ $$(\text{valid sequence length $n-3$})\, \text{PLL}$$

or, in other words

$$f[n]=f[n-1]+f[n-2]+f[n-3]\tag{Answer 1}$$

with $f[0]=1,\, f[1]=2,\, f[2]=2^2=4$.

But since

$$f[n-1]=f[n-2]+f[n-3]+f[n-4]$$

we have

$$f[n]=2f[n-1]-f[n-4]\tag{Answer 2}$$

with the extra initial value $f[3]=2^2+2+1=7$.


The overall answer (including the possibility of an absence) will be

$$f[n]+\sum_{k=1}^{n}f[k-1]f[n-k]$$

because there are $f[n]$ valid sequences with no absence and $\sum_{k=1}^{n}f[k-1]f[n-k]$ sequences with $1$ absence (the absence A can be in positions $k=1\ldots n$ with a valid sequence of Ps and Ls either side of the A).

$\endgroup$
  • $\begingroup$ Great, thank you. This explanation was perfectly clear and the final answer matches the working solution. Still, were you able to see whether the author's explanation was indeed correct as well? I ask because, I began to suspect it was wrong, and the author was simply trying to fit his own explanation for the Answer 2 formula he actually copied from somewhere else. I don't see how his approach is correct. $\endgroup$ – Andrew Cheong Apr 25 '17 at 4:07
  • $\begingroup$ @AndrewCheong, I have to admit that I only scanned the author's method but it looked a bit over-complicated to me. Still the answer given agrees with mine so it must be right ;) On closer inspection though I'm still not sure, it looks like he did something similar to me but ... hmmm ... no can't see it. Perhaps I'll take another look tomorrow... $\endgroup$ – N. Shales Apr 25 '17 at 4:24
  • $\begingroup$ Thank you again for taking an extra look. Where can I find more information on why it's proper to set f[0] = 1? Is this typical (or a rule) in recurrence relations? Perhaps related to exponents never resulting in 0? $\endgroup$ – Andrew Cheong Apr 28 '17 at 14:49
  • 1
    $\begingroup$ @AndrewCheong. It is convention to have an empty sequence (unless your conditions state explicitly that, say the sequences must be a certain length $\gt 0$). By setting $f[0]=1$ we can calculate $f[3]$ from the recurrence $f[3]=f[2]+f[1]+f[0]$. The $f[0]$ term accounts for the sequence $(\text{valid sequence of length $0$}) \text{PLL}$ or just $\text{PLL}$. If we start with $f[1]$ then we need to state $f[1]$, $f[2]$ and $f[3]$ as initial conditions. But calculating $f[3]$ requires us to use the recurrence anyway by adding the single case of $\text{PLL}$ to $f[1]+f[2]$. $\endgroup$ – N. Shales Apr 28 '17 at 15:46
  • 1
    $\begingroup$ very clear answer +1 much better than the official answer :) or most alternatives in projecteuler.net/problem=191 (an equivalent problem) $\endgroup$ – antkam Nov 20 '18 at 14:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.