CodeChef Easy Problem: Sums in a Triangle


Still practicing for Facebook Hacker Cup 2013. The problem below is a classic, although I wouldn’t necessarily classify it as “easy” as the guys from CodeChef did. Anyway here you go:

———-
Let’s consider a triangle of numbers in which a number appears in the first line, two numbers appear in the second line, three in the third line, etc. Develop a program which will compute the largest of the sums of numbers that appear on the paths starting from the top towards the base, so that:
on each path the next number is located on the row below, more precisely either directly below or below and one place to the right;
the number of rows is strictly positive, but less than 100
all numbers are positive integers between O and 99.

Input

In the first line integer n – the number of test cases (equal to about 1000).
Then n test cases follow. Each test case starts with the number of lines which is followed by their content.

Output

For each test case write the determined value in a separate line.
Example

Input:
2
3
1
2 1
1 2 3
4
1
1 2
4 1 2
2 3 1 1

Output:
5
9
———-

My Solution

Solving this problem with a brute force approach is possible, especially if the input is small, as in this case. However, as the input size grows the brute force approach stops working, as the number of possible paths you’ll need to calculate grows exponentially.

There’s a rather clever way to solve this in linear time: start with the second to last row. Then for each of the numbers there calculate what is the maximum value they can achieve going down, which is basically the numbers themselves plus the max out of the two numbers below. Then repeat this process going up the pyramid, and once you get on top that will be your answer.

#include <stdio.h>

int mat[100][100];

int max(int x, int y){
  if(x>y)
    return x;
  else
    return y;
}

int solve(int x){
  int k,l;

  if(x==1)
    return mat[0][0];
  
  for(k=x-2;k>=0;k--){
    for(l=0;l<=k;l++){
      mat[k][l] += max(mat[k+1][l],mat[k+1][l+1]);
    }
  }

  return mat[0][0];
}

int main(){
  int i,j,k,l,w;
  scanf("%d",&j);
  int x;

  for (i=0;i<j;i++){
    scanf("%d",&x);    
    for(k=0;k<x;k++){
      for(l=0;l<k+1;l++){
        scanf("%d",&w);  
        mat[k][l]=w;
      }
    }
    printf("%dn",solve(x));
  }  

return 0;
}

One thought on “CodeChef Easy Problem: Sums in a Triangle

  1. Gage

    Nice blog – @this problem, I approached it the same way in Java but keep getting time limit exceptions from CodeChef even though my solutions on my own computer work fine. Any idea of what I can do to fix this? Thanks,
    public class SumsInATriangle {

    public static void main(String[] args){

    java.util.Scanner input = new java.util.Scanner(System.in);

    int[][] triangle = new int[0][0];
    int cases = input.nextInt();

    int[] solutions = new int[cases];
    int sI = 0;

    for(int i = 0; i < cases; i += 1){

    int lines = input.nextInt();
    triangle = new int[lines][lines];
    int level = 1; //top of triangle is level 1 and level increases as works towards base

    for(int y = 0; y < lines; y += 1){
    for(int x = 0; x < level; x += 1){
    triangle[y][x] = input.nextInt();
    }
    level += 1;
    }
    //save outputs in array until all inputs are processed
    solutions[sI] = findGreatestRouteValue(triangle);
    sI += 1;
    }

    for(int i = 0; i = 0; y -= 1){
    optimizedRow = new int[optimizedRow.length – 1]; //reduce level to level before base
    for(int x = 0; x tri[y][x] + tri[y+1][x+1] ? tri[y][x] + tri[y+1][x] : tri[y][x] + tri[y+1][x+1];
    optimizedRow[x] = a;
    }

    level -= 1;
    tri[y] = optimizedRow;
    }//end for y

    return optimizedRow[0]; //last remaining number is the greatest route value

    }
    }

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *