USACO number triangle

Question

The question is as follows

Consider the number triangle shown below. Write a program that calculates the highest sum of numbers that can be passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right.

        7

      3   8

    8   1   0

  2   7   4   4

4   5   2   6   5

In the sample above, the route 7 -> 3 -> 8 -> 7 -> 5 produces the highest sum: 30.

I had the following error

 Execution error: Your program (`numtri') used more than the
    allotted runtime of 1 seconds (it ended or was stopped at 1.674
    seconds) when presented with test case 6. It used 6080 KB of
    memory. 

My program works for the for the input <=8 triangle size. But, it fails for when triangle size is more than 8. why it is happening i don't know. please help.

Here is my code:

#define MAX 1000

int max=0,a[MAX][MAX];

void dfs(int i,int j,int end,int sum)
{
 if(i<=end)
 {   
      sum += a[i][j];
      dfs(i+1,j,end,sum);
      dfs(i+1,j+1,end,sum);
 }
 else 
 {
      if(sum>max)  
      max = sum;

 }
}

int main () {

FILE *fin  = fopen ("numtri.in", "r");
FILE *fout = fopen ("numtri.out", "w");
int r,i,j;

fscanf(fin,"%d",&r);

for(i = 1;i<=r;i++)
 for(j = 1;j<=i;j++)
  fscanf(fin,"%d",&a[i][j]);

dfs(1,1,r,0);

fprintf(fout,"%d\n",max);

fclose(fin);
fclose(fout);
return 0;
}

It works for the first 5 test cases but fails on 6th which has 199 triangle size.

Answer 1

Instead of using dp it can be done with BFS since when you encounter a visited node you can simply change its value since you have not traversed until the end of the graph but you have to be very careful about the memory. Here is my code which does work when in the USACO Grader:

#include <bits/stdc++.h>
    using namespace std;
    
    typedef long long ll;
    typedef long double ld;
    typedef vector<long long> vi;
    typedef pair<long long,long long> pi;
    typedef vector<pi> vpi;
    
    #define FOR(i, a, b) for(ll i=ll(a); i<ll(b); i++)
    #define ROF(i, a, b) for(ll i=ll(a); i>=ll(b); i--)
    #define f first
    #define s second
    #define pb emplace_back
    #define mp make_pair
    #define SQ(a) (a)*(a)
    #define all(a) (a).begin(), (a).end()
    
    
    int main() {
    ifstream cin("numtri.in");
    ofstream cout("numtri.out");
    int n;
    
    int adjacency_list[500500];
    int matrix[1005][1005];
    
    bool visited[500500];
    int value[500500];
    
    int total[500500];
    int maxnum=0;
    
    cin>>n;
    int s=0,x=0;
    for(int i=0;i<n;i++){
    s++;
    for(int j=0;j<s;j++){
      cin>>value[x];
      total[x]=0;
      matrix[i][j]=x;
    x++;
    }
    }
    s=0;
    
    
    for(int i=0;i<n-1;i++){
    s++;
    for(int j=0;j<s;j++){
      adjacency_list[matrix[i][j]]=(matrix[i+1][j]);
    
    }
    }
 
    
     
    total[0]=value[0];
    queue<int>q;
    q.push(0);
    while(!q.empty()){
      int current=q.front();
      q.pop();
    
    if(current<((n*(n+1) )/2)-1-(n-1 )  ){
    
    int i =adjacency_list[current];
      if(!visited[i]){
        q.push(i);
        total[i]=total[current]+value[i];
        //cout<<total[i];
      }
      else{
    if(total[current]+value[i]>total[i]){
      total[i]=total[current]+value[i];
    }
      }
      maxnum=max(total[i],maxnum);
      visited[i]=1;
    
    i =adjacency_list[current]+1;
      if(!visited[i]){
        q.push(i);
        total[i]=total[current]+value[i];
       
      }
      else{
    if(total[current]+value[i]>total[i]){
      total[i]=total[current]+value[i];
    }
      }
      maxnum=max(total[i],maxnum);
      visited[i]=1;
    }
    }
    
    cout<<maxnum<<endl;
        return 0;
    }

Answer 2

Every time your program encounters a specific point in the pyramid, it calculates the optimum path to the bottom. However, you can make the observation that each point is encountered more than once, thus the optimum path is calculated several times. Therefore, your program runs in exponential time.

If you instead save the maxmimum sum achievable at some point in the triangle (here in dp[i][j]), and reuse that value instead of recomputing it once you hit that point again, your program will be much faster. That's because this algorithm only visits each point in the pyramid once. This is called top-down dynamic programming.

#include<string.h>
#include<stdio.h>
#define MAX_N 1005

int a[MAX_N][MAX_N];
int dp[MAX_N][MAX_N];

int max(int a, int b)
{
  return a > b ? a : b;
}

int dfs(int i,int j,int end)
{
  if(dp[i][j] != -1)
  {
    return dp[i][j];
  }
  else if(i <= end)
  {
    return dp[i][j] = a[i][j] + max(dfs(i+1,j,end), dfs(i+1,j+1,end));
  }
  else
  {
    return 0;
  }
}

int main () {
  FILE *fin  = fopen ("numtri.in", "r");
  FILE *fout = fopen ("numtri.out", "w");
  int r,i,j;

  memset(dp, -1, sizeof dp);

  fscanf(fin,"%d",&r);

  for(i = 1;i<=r;i++)
    for(j = 1;j<=i;j++)
      fscanf(fin,"%d",&a[i][j]);

  fprintf(fout,"%d\n", dfs(1,1,r));

  fclose(fin);
  fclose(fout);
  return 0;
}

Answer 3

Using a DFS for this problem is inefficient for the following reason: Consider one path that goes first right, then left, and another path that goes first left, then right. These paths are now in the same spot, and the paths leading from this spot will be calculated twice. At lower levels of the pyramid the situation is even worse, giving exponential runtime.

What you need to do is called dynamic programming. We use the fact that this problem exhibits optimal substructure (for a path to be maximal all subpaths must be maximal), and overlapping subproblems (the behavior described above). This allows us to avoid doing unneccessary work.

There are two possible approaches to this.

1. Top-down with memoization: Do your dfs, but save the computed value for a given cell when you return. That way when you visit a cell again you don't have to do a dfs from that cell, and can just return immediately.

2. Bottom-up: Start at the bottom row, and keep a list of the maximum sum achievable starting from each cell in the current row. To begin with this is just the numbers at the bottom. Then, for the next rows, cell j of row i will have max sum: a[i][j] + max(maxsum[i+1][j], maxsum[i+1][j+1])

For more info read up on dynamic programming on wikipedia or in your favorite algorithms book.

Answer 4

The recursion in your dfs() routine gives dfs a runtime that is exponential in the depth of search, with most of the work it does being redundant. For this problem there's a simple non-recursive solution. Instead of recursing into dfs, maintain a vector v of current-level path maxima values. To go one level deeper, copy v to a work vector w; then set each element v[j] to a[i][j] plus the larger of w[j] and w[j+1].