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

×

what is the problem in my code ?

Hi I am trying to solve SUMTRIAN problem it is work good in my computer but when i put the code in the website I have the time limit problem this is my code if any one can help me ,plz? * I am sorry about my English Language

package codechef;
import java.util.Scanner;
class SUMTRIAN {
private static int Trian[][];
//private static int SumTrian[];
private static int rows;
public static void main(String[] args) {
    Scanner input = new Scanner(System.in);
    int case1 = input.nextInt();
    for (int s = 0;s<case1;s++){
        rows= input.nextInt();
        Trian = new int[rows*rows][rows*rows];
        //SumTrian = new int[rows];
        for(int row = 0;row <rows;row++)
            for (int col = 0;col<=row;col++)
                Trian[row][col]=input.nextInt();
        System.out.println(solve(0,0));

    }
}
public static int solve(int row,int col){
    if(row>rows-1)
        return 0;
    else{
        int t1 = solve(row+1,col);
        int t2 = solve(row+1,col+1);
        int t = Trian[row][col]+max(t1,t2);
        return t;
    }
}
public static int max(int t1,int t2){
    int max = t1;
    if(t2>max)
        max = t2;
    return max;

}
}

asked 27 May '16, 11:58

omar61's gravatar image

0★omar61
2313
accept rate: 0%


Your algorithm is doing an exhaustive search and runs in exponential time, that's why it's getting TLE. Try doing a dynamic programming approach :) Good luck! Let me know if you want me to explain how to use DP approach in this problem.

link

answered 27 May '16, 14:43

mightymercado's gravatar image

4★mightymercado
2826
accept rate: 11%

edited 27 May '16, 14:43

(27 May '16, 14:44) mightymercado4★

I learned it from tutorial in the code chef by using recursion approach

https://www.codechef.com/wiki/recursion-sums-triangle

I will try to solve it by DB approach

(27 May '16, 17:33) omar610★

Okay brother, good luck :) @omar61

(27 May '16, 17:52) mightymercado4★
link

answered 21 Nov '16, 17:19

mathecodician's gravatar image

6★mathecodician
2.6k323
accept rate: 8%

edited 21 Nov '16, 17:19

Also, besides DP, you should take care to never name any package while submitting it on any online judge.

link

answered 02 Mar, 17:21

akashbhalotia's gravatar image

3★akashbhalotia
39911
accept rate: 0%

Economics Assignment Help discusses the subject in much detail facilitation on many topics relating to economics, for instance invisible hand; Malthus thoughts about population growth; scarcity, choice, and self-interest within economics and other topics like demand side economics, socio-economics, macroeconomics, microeconomics, aggregate supply, aggregate demand and much more.

link

answered 14 Apr, 17:44

cubi's gravatar image

0★cubi
-5
accept rate: 0%

link

answered 29 Jun, 15:32

fitensity's gravatar image

0★fitensity
-3
accept rate: 0%

include<iostream>

using namespace std; long a[100][100]; long sum[100]; int temp,temp1,k; int main() { int m,i,j,n,N; temp=0; temp1=1; k=0; cin>>n; while(n>0) {
cin>>N; for(i=0;i<n;i++) for(j="0;j&lt;=i;j++)" {="" cin="">>a[i][j]; } for(i=1;i<=N;i++) { j=0; temp=a[i][j]; for(j=0;j<=i;j++) { if(temp<=a[i][j]) { temp=a[i][j]; } } temp1=temp1+temp; if(i==(N)) { sum[k]=temp1; if(k==0) { --sum[k]; } k++; temp1=0; } } n--; } for(i=0;i<k;i++) { cout<<sum[i]<<"\n"; } return 0; } What's Wrong with my code?

link

answered 11 Aug, 18:23

abhyuday18's gravatar image

0★abhyuday18
1
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:

×1,064
×47
×38

question asked: 27 May '16, 11:58

question was seen: 3,020 times

last updated: 11 Aug, 18:23