December 2005 Problem 'bowl' Analysis

This is a problem from the training pages and from an old IOI. The problem as stated virtually demands a recursive solution. Unfortunately, it quickly becomes clear that such a solution will run far, far too long.

The 'whack on the side of the head' for this one is: solve the problem from the bottom (wide end) of the triangle, not from the top. Look at the pairs of integers and choose the larger of the pair as the choice that must be made by the integer centered above the pair. Once that insight comes through, the rest of the solution is simple and very speedy.

Here is Brian Dean's solution:

#include <stdio.h>

int A[350][350];
#define MAX(i,j) ((i) > (j) ? (i) : (j))

int main(void) 
{
    FILE *fp;
    int N, i, j;
    fp = fopen("bowl.in","r");
    fscanf (fp, "%d", &N);
    for (i=0; i<N; i++)
        for (j=0; j<=i; j++)
            fscanf (fp, "%d", &A[i][j]);
    fclose(fp);
    for (i=N-2; i>=0; i--)
        for (j=0; j<=i; j++)
            A[i][j] = A[i][j] + MAX(A[i+1][j], A[i+1][j+1]);
    fp = fopen("bowl.out","w");
    fprintf (fp, "%d\n", A[0][0]);
    fclose(fp);
}