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.
int combos(int n, int l, int a) { if (a < 0 || l < 0) return 0; else if (n == 0) return 1; else return combos(n-1,l,2) + combos(n-1,l,a-1) + combos(n-1,l-1,2); }As you say, turning the recursion into a dynamic programming solution is tricky, but this seems to work:
int index(int n, int l, int a) { return 6*n + 3*l + a; } int dynamic(int n) { std::vector<int> s((n+1)*3*2); for (int i = 0; i < 6; i++) s[i] = 1; for (int i = 0; i < n; i++) { for (int l = 0; l < 2; l++) { for (int a = 0; a < 2; a++) { s[index(i+1,l,a+1)] += s[index(i,l,a)]; } int value = s[index(i,l,2)]; for (int a = 0; a < 3; a++) { s[index(i+1,l,a)] += value; if (l == 0) s[index(i+1,1,a)] += value; } } } return s[index(n,1,2)]; }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:
(define (award l a n) (cond ((< l 0) 0) ((< a 0) 0) ((= n 0) 1) (else (+ (award l 2 (- n 1)) (award (- l 1) 2 (- n 1)) (award l (- a 1) (- n 1))))))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:
#!/usr/bin/node "use strict" function combos0(N,L,A) { function aux(n,l,a) { if (a < 0 || l < 0) return 0; else if (n === 0) return 1; else return aux(n-1,l,A) + aux(n-1,l,a-1) + aux(n-1,l-1,A); } return aux(N,L,A); } function sumrange(n,m,f) { var total = 0; for (var i = n; i <= m; i++) { total += f(i); } return total; } function combos1(N,L,A) { // 0 late days, up to a consecutive absences at end. function aux0(n,a) { if (a < 0) return 0; else if (n === 0) return 1; else return aux0(n-1,A) + aux0(n-1,a-1); } // Exactly l late days, up to A consecutive absences at end. // Each n-combination with l > 0 late days is uniquely composed // of an m-combination of l-1 late days, followed by a late day, // followed by a n-m-1 combination with 0 late days. function aux1(n, l) { if (l === 0) return aux0(n,A); else return sumrange(0,n-1, function(i) { return aux1(i,l-1)*aux0(n-1-i,A); }); } return sumrange(0,L, function(l) { return aux1(N,l); }); } var N = parseInt(process.argv[2]) || 20; var l = parseInt(process.argv[3]) || 1; var a = parseInt(process.argv[4]) || 2; console.log("L = " + l + ", A = " + a); for (var n = 0; n <= N; n++) { console.log(n + ": " + combos0(n,l,a) + " " + combos1(n,l,a)); }