## 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[ni−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.

Pages: 1 2

### 10 Responses to “School Awards”

1. matthew said

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.

2. programmingpraxis said

@Matthew: I wrote exactly the same combos function you did; mine didn’t work, and neither does yours. Your dynamic function looks correct.

3. matthew said

Are you sure? Both functions give the same result for n = 0 to 20 (and they agree with your numbers above).

4. programmingpraxis said

@Matthew: I don’t have a C++ compiler on my computer at work, so I quickly translated to Python:

```>>> def combos(n, l, a):
...     if a < 0 or l >> for n in xrange(1,20):
...     print n, combos(n, 1, 3)
...
1 3
2 8
3 20
4 45
5 99
6 212
7 444
8 917
9 1871
10 3780
11 7576
12 15081
13 29847
14 58776
15 115240
16 225081
17 438123
18 850224
19 1645452```

Did I do something wrong somewhere?

5. matthew said

Something went wrong with the formatting there for sure.

6. matthew said

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))))))
```
7. programmingpraxis said

I’ll try that again:

```>>> def combos(n, l, a):
...     if a < 0 or l *lt; 0: return 0
...     if n == 0: return 1
...     return combos(n-1,l,2) + combos(n-1,l,a-1) + combos(n-1,l-1,2)
...
>>> for n in xrange(1,20):
...     print n, combos(n, 1, 3)
...
1 3
2 8
3 20
4 45
5 99
6 212
7 444
8 917
9 1871
10 3780
11 7576
12 15081
13 29847
14 58776
15 115240
16 225081
17 438123
18 850224
19 1645452```
8. matthew said

Ah, actually, I see the problem, the top level call needs to be “combos(n,1,2)”, not “combos(n,1,3)”

9. programmingpraxis said

That works. Thank you.

10. matthew said

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);
}
}

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) || 20;
var l = parseInt(process.argv) || 1;
var a = parseInt(process.argv) || 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));
}
```