School Awards
November 3, 2015
This problem is magical, with a brilliant explanation by Brian Scott at math.stackexchange.com/questions/1279610/. Considering the input as a string containing n characters L, A or O, one per day, Scott begins by counting the strings that contain no Ls, and finds there are 1, 2, 4, 7, 13, 24, 44, 81, 149, … of them; these are the tribonacci numbers (A000073) offset by 2. Then the desired number of awards for n days is the nth tribonacci number S[n] plus the product of S[i] and S[n−i−1] for i < n:
(define (award days) (if (= days 1) 3 (let loop ((xs (list 4 2 1)) (days days)) (if (< 2 days) (loop (cons (+ (car xs) (cadr xs) (caddr xs)) xs) (- days 1)) (+ (car xs) (sum (map * (cdr xs) (reverse (cdr xs)))))))))
The loop builds up the tribonacci numbers in xs, then computes the result in the final line. Special handling is required when days is 1, because the initial list of tribonacci numbers is too long. Here are the first few members of the sequence:
> (do ((n 1 (+ n 1))) ((< 20 n)) (display n) (display #\tab) (display (award n)) (newline)) 1 3 2 8 3 19 4 43 5 94 6 200 7 418 8 861 9 1753 10 3536 11 7077 12 14071 13 27820 14 54736 15 107236 16 209305 17 407167 18 789720 19 1527607 20 2947811
I’m surprised not to find that sequence in OEIS. If you’re not as good a mathematician as Scott, you can build up the answer using dynamic programming, although I’ll confess I never got that to work. The basic idea is that (award l a n)
is (award l a (- n 1))
if the student is on-time the first day, (award (- l 1) a (- n 1))
if the student is late the first day, and (award l (- a 1) (- n 1))
if the student is absent the first day, with the recursion the sum of the three.
You can run the program at http://ideone.com/heFCdS.
Here’s a nice recursive solution, combos(n,l,a) returns number of ways of being late no more than l times, with at most a absences.
As you say, turning the recursion into a dynamic programming solution is tricky, but this seems to work:
Tribonacci solution is nice, but it’s not clear to me how to generalize it to other values of a and l.
@Matthew: I wrote exactly the same combos function you did; mine didn’t work, and neither does yours. Your dynamic function looks correct.
Are you sure? Both functions give the same result for n = 0 to 20 (and they agree with your numbers above).
@Matthew: I don’t have a C++ compiler on my computer at work, so I quickly translated to Python:
Did I do something wrong somewhere?
Something went wrong with the formatting there for sure.
If you want some Scheme, this seems to work:
I’ll try that again:
Ah, actually, I see the problem, the top level call needs to be “combos(n,1,2)”, not “combos(n,1,3)”
That works. Thank you.
After a little more thought, here’s a generalization of the recurrence in the Tribonacci solution. For a change, this one is is Javascript: