You are not logged in. Please login at www.codechef.com to post your questions!

×

SUMTRIAN - implementing memoization

I have spent many hours trying to solve the SUMTRIAN problem (http://www.codechef.com/problems/SUMTRIAN/) I know how my program works, I am implementing recursion, and I am doing my best to implement memoization (this is new for me). The code works perfectly fine for small triangles. However, every submission to CodeChef exceeds the time limit. Can anyone give me any pointers, please?

Thanks,

public class Main {

private static int[][] triangle = new int[0][0]; 
private static int[][] computedPaths = new int[0][0]; //for memoization

public static void main(String[] args){

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

    int cases = input.nextInt();

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

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

        int lines = input.nextInt();
        triangle = new int[lines][lines];
        computedPaths = 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[solutionsIndex] = findGreatestRouteValueRecursively(0,0);
        solutionsIndex += 1;
    }

    for(int i = 0; i < solutions.length; i += 1){
        System.out.println(solutions[i]);
    }

}//end main

public static int findGreatestRouteValueRecursively(int y, int x){
    if(y >= triangle.length)
        return 0;
    else if(computedPaths[y][x] == 0){
        int value1 = findGreatestRouteValueRecursively(y+1, x);
        int value2 = findGreatestRouteValueRecursively(y+1, x+1);
        computedPaths[y][x] = Math.max(value1, value2) + triangle[y][x];
    }
    return computedPaths[y][x];

}//end findGreatestRouteValueRecursively()
}

asked 28 Jun '14, 06:49

slaynen's gravatar image

2★slaynen
12
accept rate: 0%


bump - any tips on how to memoize this would be greatly appreciated! the only code to rly look at is the findGreatestRouteValueRecursively at the bottom

link

answered 28 Jun '14, 18:32

slaynen's gravatar image

2★slaynen
12
accept rate: 0%

Solved - for anyone curious, what made the difference was changing my input from Scanner to BufferedReader and InputStreamReader. Lesson learned :)

Code below: public class SumsInATriangle {

private static int[][] triangle = new int[0][0]; 
private static int[][] computedPaths = new int[0][0]; //for memoization

public static void main(String[] args) throws java.io.IOException{

    java.io.BufferedReader reader = new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
    String[] in = reader.readLine().split(" ");

    int cases = Integer.parseInt(in[0]);

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

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

        in = reader.readLine().split(" ");

        int lines = Integer.parseInt(in[0]);
        triangle = new int[lines][lines];
        computedPaths = 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){
            in = reader.readLine().split(" ");
            for(int x = 0; x < level; x += 1){
                triangle[y][x] = Integer.parseInt(in[x]);
            }
            level += 1;
        }

        //save outputs in array until all inputs are processed
        solutions[solutionsIndex] = findGreatestRouteValueRecursively(0,0);
        solutionsIndex += 1;
    }

    for(int i = 0; i < solutions.length; i += 1){
        System.out.println(solutions[i]);
    }

    //      int level = 1; //print triangle
    //      for(int y = 0; y < triangle[0].length; y += 1, level += 1){
    //          for(int x = 0; x < level; x += 1){
    //              System.out.print(triangle[y][x] + " ");
    //          }
    //          System.out.println();
    //      } 
}//end main

public static int findGreatestRouteValueRecursively(int y, int x){
    if(y >= triangle.length)
        return 0;
    else if(computedPaths[y][x] == 0){
        int value1 = findGreatestRouteValueRecursively(y+1, x);
        int value2 = findGreatestRouteValueRecursively(y+1, x+1);
        computedPaths[y][x] = Math.max(value1, value2) + triangle[y][x];
    }
    return computedPaths[y][x];

}//end findGreatestRouteValueRecursively()

}//end class

link

answered 28 Jun '14, 21:34

slaynen's gravatar image

2★slaynen
12
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×3,486
×1,214
×107
×53

question asked: 28 Jun '14, 06:49

question was seen: 1,179 times

last updated: 28 Jun '14, 21:34