USACO OCT06 2006 Problem 'pie1' Analysis

by Rob Kolstad

This is a variant of the 'numtri' problem from the USACO training pages. The trick is to avoid the use of recursion, which ends up in a combinatorial explosion since it recalculates various answers over and over again. The atractiveness is that the solution could be just like the solution to the 'skate' problem, with a depth-first search; below is a Pascal version of such a search from one of the competitors with added commands by Coach Rob:

procedure find (r , c, total:integer);	
begin
    total := total + a[r,c];		{ add in this square }
    if (r=r) and (c=c) then begin	{ are we done? }
        if max<total then max:=total;   { tally maximum sum if better }
        exit;				{ exit = 'return' in C/C++/Java }
    end;
    if (r>1) and (c<c) then		{ legal to search at r-1,c+1? }
	find(r-1,c+1,total);		{ check next column right }
    if (c<c) then			{ legal to search at r,c+1? }
	find(r,c+1,total);		{ check }
    if (r<r) and (c<c) then		{ legal for r+1,c+1? }
	find(r+1,c+1,total);		{ check }
end;
Unfortunately, the recursive calls end up repeatedly touching the same squares (and the number of recursions is just astonishingly large).

What to do?

One way is simply to work the problem backwards, touching each square only a very few times. The best result possible for column C-1 (the next-to-last one) is entirely dependent on the values in column C-1 and C. Inductively, this takes one all the back to column 1, where the answer pops out of the R=1,C=1 element.

This is a sort of 'Dynamic Programming', though perhaps is not as illuminating for the general case as one would hope. The complete JAVA solution below is from USA's Justin Hsu and implements the backwards-working algorithm (read on later for other interesting solutions). Comments are by Coach Rob:

import java.io.*;
import java.util.*;

class pie1 {
    public static void main (String [] args) throws IOException {
    
    BufferedReader in = new BufferedReader (new FileReader ("pie1.in"));
    PrintWriter out = new PrintWriter (new BufferedWriter new FileWriter("pie1.out")));
    StringTokenizer st;
	
    int[][] max = new int[102][102];
    int[][] field = new int[102][102];
    
    st = new StringTokenizer(in.readLine());
    int R = Integer.parseInt(st.nextToken());	/* problem parameters */
    int C = Integer.parseInt(st.nextToken());
    
    /* Read the pie values: */
    for(int r = 0; r <= R+1; r++) {
    	if(r != 0 && r <= R)
            st = new StringTokenizer(in.readLine());
        for(int c = 0; c <= C+1; c++) {
            max[r][c] = 0;
			/* don't read into inappropriate squares: */
            if(r == 0 || c == 0) continue;
            if(r > R || c > C) continue;
            field[r][c] = Integer.parseInt(st.nextToken());
        }
    }
    
    max[R][C] = field[R][C];
    /* working backwards from column C-1: */
    for(int c = C-1; c >= 0; c--) {
        for(int r = 1; r <= R; r++) {   /* for each row */
			/* don't tabulate inappropriate squares: */
            if(!((r <= c) && (c-r <= C-R))) continue;
	    /* calculate best that square r,c can be: */
            max[r][c] = field[r][c] + Max3 (max[r-1][c+1], max[r][c+1], max[r+1][c+1]);
        }
    }
    
    out.println(max[1][1]);
    in.close();
    out.close();                                
    System.exit(0);                             
  }
  
  public static int Max3(int a, int b, int c) {
          return Max(Max(a, b),c);
  }
  
  public static int Max(int a, int b) {
          if(a > b) return a;
          else return b;
  }
}

But clever folks can create a forward-looking dynamic programming solution that is amazing in its brevity and cleverness. Here is South Africa coach Bruce Merry's C++ solution that reverses the calculations of the program above so that the answer pops out of R,C instead of 1,1:

#include <fstream>
#include <algorithm>

using namespace std;

#define MAXR 105
#define MAXC 105

int main() {
    int coins[MAXR][MAXC] = {{0}};
    int dp[MAXR][MAXC] = {{0}};
    int R, C;
    ifstream in("pie1.in");

    in >> R >> C;
    /* read in all the coin values: */
    for (int i = 1; i <= R; i++)
        for (int j = 1; j <= C; j++)
            in >> coins[i][j];
    /* dynamic programming: */
    for (int j = 1; j <= C; j++)
        for (int i = 1; i <= j && i <= R; i++)
            dp[i][j] = coins[i][j] + (dp[i - 1][j - 1] >? dp[i][j - 1] >? dp[i + 1][j - 1]);

    ofstream out("pie1.out");
    out << dp[R][C] << "\n";
    return 0;
}