Sums in a Triangle

first i used recursion, then it exceeded time limit. so, i use memoization.

i cannot understand how the path has to be recognised?

The question is not clear... the path has been described as starting from the top and then either directly below or below and one place to the right. Following this instruction, for the first test case the path should be "1-2-2" which gives 5(correct). But for the second case the path should be "1-2-2-1" which gives 6(incorrect).

Is the instruction saying this or is it just finding the largest number on each level and adding them(excluding the first level).... because this seems to give the right answer for the sample test case provided.

u hav to find d largest sum not just add the largest number.. the path to follow in 2nd test case wud be 1-1-4-3 which wud giv 9.. correct answer!!!

I have tested the problem on different sizes, but it still shows wrong answer.. i am using dev c . I am taking the input as in to get a value i use scanf and then u have to press the enter... is this not the way i should take input for this problem ...??

The way you are taking input is fine.

Almost everyone is taking 0.72 seconds to solve this problem in C/C . How is it that a Java solution notched up 0.49 seconds??? Admins can you please investigate? Also, I would love to know how Lucasz managed to notch up 0.20 seconds for this problem.

@Admin .. so what can be the problem with it ...?

In the forum it is written that content of any line n should not be greater than n except the last line i.e. n=100.
Is it true cause its no where mentioned

None of the numbers will be greater than 99. Only the last line will have 'n' numbers. So if 'n' is 100, the last line for that test case will have 100 numbers.

Sorry, 'n' is always less than 100. The maximum value of 'n' would be 99.

can anyone go through my solution and point out how to optimise my code further, because I have tried my best and I am still getting TLE.
@admin : Please help

First try finding the complexity of your solution and then see if it will run within time based on your calculations.

i am not using recursion and yet I still always exceed the time limit. Is this problem not possible to accomplish in a language like python in the time limit specified. I compute the solution bottom up inside a for loop. I looked on the list of successful solutions for this problem and there was only one python submissions that was on there and it took more than the specified 3 second time limit.

Currently the time limit for Python is 2 times that for C/C

Hint : you only need to find the largest sum, not necessarily the path.

No, you need to re-read the problem statement.

I just compiled my prog in MVC (.h , .cpp) successfully.But it threw errors in gcc

You don't need a .h file, just the .cpp file that takes the input, processes it and prints the output is to be submitted.

Hey, can i get some help? its my first code here :) and i think my algo is correct but i'm getting the result as a wrong answer (as you can see). So is there any specific case that i'm missing??

Hey, can anyone suggest me why my code is giving me the compile error?? i have developed the code using turbo c++....and it is working fine there???

Pls help me!!

Read the FAQ.

(We can't see your code anyway, unless you post it in the forum).

 

hi admin,

what is the method of inputting i.e can i use 'cin' for numbers in the  line or some other way to do it.

You have to read the numbers from stdin and output your answers to stdout. You can use cin.

 @admin

can i get more testcases for this problem , my code runs correctly with provided testcases but chef says it gives incorrect result.

help.

We use this problem for recruitment purposes and as such we can't give out specific test cases. :(

i'm nt gettin link f solution fr dis prblm??

The solutions are not public for this problem.

can some one please make me understand this question!!!!!!!!!!!

if the max no of lines in each case is 99 at worst case, then it would contain 4950 integers in the triangle.

in this case it wud need 19800 bytes to storage.

but acc to the problem statement the resources is restricted to 5000bytes.

That limit is on the length of your code, not the memory your code consumes.

ohh, thx

Does that mean there is no restriction on the space complexity of the code.?

No, read the FAQ for more info on that.

This code working fine on my system. but here its showing compiler error. please let me know whats the problem import java.util.Scanner; public class Sum { public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.println("Enter The Total Number of Rows : "); int rows=sc.nextInt(); int[][] arr= new int[rows][]; for(int i=0;i0;i--){ for(int j=0;j arr[i][j+1])? arr[i][j]: arr[i][j+1]); } } System.out.println("OUTPUT : " + arr[0][0]); } }

I am using java.util.Scanner class to read the input.

import java.util.Scanner; public class Sum { public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.println("Enter The Total Number of Rows : "); int rows=sc.nextInt(); int[][] arr= new int[rows][]; for(int i=0;i0;i--){ for(int j=0;j arr[i][j+1])? arr[i][j]: arr[i][j+1]); } } System.out.println("OUTPUT : " + arr[0][0]); } }

Read the FAQ and www.codechef.com/help for more information on a sample solution in Java.

plz help ..i have tried my best to minimize the iterations but still the tym limit is exceeding...here is the code..

#include<iostream>
using namespace std;
main()
{
int t;
cin>>t;
int k[t],n[t],j;
double o[t];
for(int i=0;i<t;i++)
{cin>>n[i]>>k[i];
o[i]=n[i]-1;
j=n[i]-2;
while(j>n[i]-k[i])
{
o[i]*=j;
j--;
}   
j=k[i]-1;
while(j>0)
{
o[i]/=j;
j--;
}
cout<<o[i]<<"n";
}
}

 

plz help...

o sorru admin this code was for the problem marbels..plz consider it..

o sorry admin this code was for the problem marbels..plz consider it..

Im getting a runtime error. Im not sure what it is but it could be that im using too much memory. If any one knows how to use less memory or if the error could be somthing else plz help. Im using Java

No, you shouldn't get an NZEC error for using too much memory. Your code will likely be throwing some sort of exception.

You might want to check if your I/O is in accordance with the input and output specifications.

ok so i think i got it, there are spaces between each number and each number can be up to 2 digits long.

does the input method have to be different for space separated numbers . i am using separate cin for each number in a row and for each row . is tht wrong

If you are taking one number at a time, then you should be fine.

@Admin can you please let me know why I am encountering runtime error (NZEC) from my latest submitted solution.

@apt2D

NZEC appear to me for input problems... are you reading the standard input ?

@German Gonzalez

I am reading standard input, when I use Scanner to read input it throws time limit exceeded so I changed to read by BufferedReader it bounces with runtime error(NZEC)

@apt2D

 

here you have official information: http://blog.codechef.com/2009/02/24/54/

where it has a link to the forums with different languages solution, and yes, for Java use BufferedReader

hi

I have the solution but it is showing time limit exceeded ...

.

I am using a recursive algo .

anyone can please suggest what sort of optimisation can be done

 

hi

I have the solution but it is showing time limit exceeded ...

.

I am using a recursive algo .

anyone can please suggest what sort of optimisation can be done

 

don't use recursion at all. You mst figure out another lineal solution.

If u use recursion , make sure u memoize. It will run within time.

the unused array trick sped my C# program up from 2.69 to .07 seconds, an increase of 38 times... unbelievable.

in case you didn't catch my posts on this before, the trick consists of adding a huge array to the stack (or heap, I don't know how csharp does things internally) like so:

int[] data = new int[1000000];

whether you use it or not (if you don't, the compiler might give you a warning; ignore it) it speeds up programs like crazy. if anyone can explain this, please do!

After using memoization , my code's execution time improved but it is still long.

can anyone suggest me how to optimize it furthur.

i tried out a simple non-recursive solution and it was accepted !!

@ Admin

My working all right on my PC but when I submit it here it shows runtime error. Please check and let me know the problem.

regards

Harpreet

I mean my solution is working........

 

y dere is no tutorial for this ques.......... how  do we solve this....

 

sir i cnt understand d problem tht wht i have to do.

pls explain me in detail:

my_id:rajesh91bhatia@gmail.com 

Can somebody give me a few more test cases ? My code works fine for the cases given and Code chef say "Wrong Answer' for my code.

You should be able to make up cases just as well as anyone else can.

My code's working for the test cases and i believe it works for other cases also. Still it is showing runtime error. The code in Python is as follows:

#Sums in a Triangle
l=[]
sum=[]
n=input()
for i in xrange(1,n+1):
k=input()   
for j in xrange(0,k):
l.append([])
l[j]=raw_input().split(' ')
l=[map(int,x) for x in l]
for m in xrange(0,j):
if j>=1:
if m==0:
l[j][m]=int(l[j][m])+int(l[j-1][0])
elif m==j-1:
l[j][m]=int(l[j][m])+int(l[j-1][m-1])
else:
l[j][m]=int(l[j][m])+int(max(int(l[j-1][m-1]),int(l[j-1][m])))       
sum.append(max(l[k-1]))
for i in sum:
print i

Are negative integers also allowed?

@Haritosh: no, negative numbers will not be given, according to the problem statement. Some suggestions: although you _can_ use "sum" as a variable name, it is inadvisable because it is also has meaning as a part of the language. I doubt that is what's causing the error, but you might as well fix that. And you might get rid of unnecessary int() calls, for clarity's sake. And please read the FAQ for information on how to post your code the correct way (as a link, not here in the comments section of the problem pages).

plz clarify

what does Memory-2000 means is it byte or megabyte

Hi admin,

I have submitted a code and it seems that the code is exceeding the time limit. Can you please help me point out which part of my code is consuming more time?

You obviously haven't tried testing your program!

Not only does it appear to be giving the wrong answer for small inputs, including the sample input, but it is going to take forever on any large input. Try testing your program with 1 input with 99 rows and you will see why. By my calculations, your code would take over 100000000000000 years to finish running :)

(Also, read the FAQ if you haven't already, as it explains how to test your program.)

What the output of that test case

2

5

1

2 1

1 2 3

1 2 3 4

1 1 1 1 1

4

1

1 2

4 1 3

2 3 1 1

Plz anybody help me.

Hello All ,

I'm new to this forum , i found this intersting i wanna ask u will this problem require any datasturucture or it is crude implementation

 

pls leave a reply

@ Najmuzzaman  According to me, the answers of the test cases should be 10 and 9 respectively.

is it necessary to take input in the format as specified in the problem. i mean, cant we input one number at a time???

I am taking one no. at a time & the prog. is working fine for all the test cases i have considered till now. But still i get a runtime error (NZEC) when i submit it.

#include<stdio.h>

int main(){

int i,j,k,n,t;
double val[1000],kal[1000],a;
kal[0] = 0;
scanf("%d",&n);
while(n--){
scanf("%d",&t);
a = 0;
for(i=0; i<t; i++){
val[i] = 0;
for(j=0; j<=i; j++){

if(j>0) kal[j] = val[j-1] - k;

scanf("%d",&k);
val[j] += k;    //sum of direct below in a row.
kal[j] += k;    //sum of direct below & one right most.
}
a += k;     //sum of the otivuj.
}
kal[0] = 0;

for(i=0; i<t; i++){
if(a<val[i]) a = val[i];
else if(a<kal[i]) a = kal[i];
}
printf("%.0fn",a);
}
return 0;
}

someone plz help. i didn't find any wrong, for test case. But i found wrong answer.

@ Admin How did Saurabh manage a solution which takes 0.00 time and 0.00 memory ????

im getting this error! what do i do????

/sources/tested.cpp:1:21: error: iostream.h: No such file or directory

That message is pretty clear. There is no such thing as iostream.h.

@ asloob...use #include<iostream> instead.

hi can anyone help me with this problem. I am getting a runtime error (other) with this problem. Probably using too much space! But i am a beginner ..:( so coding the simplest way with least optimisation.. http://www.codechef.com/viewsolution/217730 can i get any ideas how and where i can optimise my code ...any useful links would be appreciated.. thnks in advance..happy coding..

hi can anyone help me with this problem. I am getting a runtime error (other) with this problem. Probably using too much space! But i am a beginner ..:( so coding the simplest way with least optimisation.. http://www.codechef.com/viewsolution/217730 can i get any ideas how and where i can optimise my code ...any useful links would be appreciated.. thnks in advance..happy coding..

Hi all

I am getting run time error..

so I used max possible input in my local to test...

i.e 99 rows each row contains number 99  only..

basically a triangle with all  the values as 99.

but, I am receiving below error -

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space

 

plz suggest sumthing..

this problem has frustated me to the limit of insanity .did everything correct tried different different algorithms but nuthing worked

@admin

i am getting a runtime error(other).. now what is that for?

i mean i am only using a small array 0f size 200 of integer type..

You declare an array of size 200 and the first thing you do is access elements up to index 250..

Anyone had any success with this problem in PHP? I can't optimize my code any further than this, and it still gives me a Timelimit Exceeded.

is it an application of longest path algorithm

sir...............i tried the sample inputs and also inputs of may own.......and i got the desired output.........but on

codechek.....i am getting wrong answer ....its really frustrating........................plz tell me the bug in my program...........................plz......plz......................

sorry spelling mistake..............*codechef

plz...check the code ->http://www.codechef.com/viewsolution/244226

how do u do this problem?

i am not able to get algo?

@Admin:

I first solved the problem in 0.73 secs and then improved it to .70, but it still shows 0.73 s against my name :(

@Admin

I have 8 successful perl submission for this problem but all TLE :(

As I do not see any submission in perl, I would like to know if this problem can be solved in the given time in Perl or is does it require any extra time for perl.

@Admin

15 Successful Submissions .. still Time Limit Exeeded.

I strongly suggest that you should perhaps consider increasing the time for Perl submissions for this problem.

A small python script to generate the input for this problem (Note: Modified the script provided by Pushparajan V in Enormous Input Test problem)

 

#! /usr/local/bin/python
import os
import random

f = open("sample.txt","w")
testcase=random.randint(999,1001)
f.write(str(testcase) + "n")
while (testcase):
rownum=random.randint(1,99)
f.write(str(rownum) + "n")
for i in range(1,rownum+1):
for j in range(0,i):
f.write(str(random.randint(0,99)) + " ")
f.write("n")
testcase=testcase-1
f.close()

My code works fine with the test cases given here on my compiler. But i am getting "wrong answer" here. Can anyone point to me the flaws??

 

#include<stdio.h>

int main(){

int final[1000],arr[2][100];

char str[300];

int i,j,k,a,b,c,max_so_far=-1,coll,index=0;

scanf("%d",&a);

for(i=1;i<=a;i++)

{

scanf("%d",&b);

for(j=1;j<=b;j++)

{

gets(str);

if(str[0]=='')

{

j--;

continue;

}

coll=1;

c=0;

k=0;

while(1)

{

if(str[k]==' '||str[k]=='')

{

if(j==1)

arr[index][1]=c;

else if(coll==1)

arr[index][1]=arr[(index+1)%2][1]+c;

else if((arr[(index+1)%2][coll-1])>arr[(index+1)%2][coll])

arr[index][coll]=arr[(index+1)%2][coll-1]+c;

else

arr[index][coll]=arr[(index+1)%2][coll]+c;

c=0;

if(max_so_far<arr[index][coll])

max_so_far=arr[index][coll];

if(str[k]=='')

break;

coll++;

}

else

c=10*c+(str[k]-'0');

k++;

}

index=(index+1)%2;

}

final[i]=max_so_far;

}

for(i=1;i<=a;i++)

printf("%dn",final[i]);

return 0;

}

i got my flaws in the previous code.sorry for the inconvenience.

I rectified the flaws i caught but still am getting "wrong answer". Please help me out.

 

 

#include<stdio.h>

int main(){

int final[1000],arr[2][100];

char str[300];

int i,j,k,a,b,c,max_so_far=-1,coll,index=0;

scanf("%d",&a);

for(i=1;i<=a;i++)

{

scanf("%d",&b);

for(k=0;k<2;k++)

for(c=0;c<100;c++)

arr[k][c]=0;

for(j=1;j<=b;j++)

{

gets(str);

if(str[0]=='')

{

j--;

continue;

}

coll=1;

c=0;

k=0;

while(1)

{

if(str[k]==' '||str[k]=='')

{

if(j==1)

arr[index][1]=c;

else if(coll==1)

arr[index][1]=arr[(index+1)%2][1]+c;

else if((arr[(index+1)%2][coll-1])>arr[(index+1)%2][coll])

arr[index][coll]=arr[(index+1)%2][coll-1]+c;

else

arr[index][coll]=arr[(index+1)%2][coll]+c;

c=0;

if(max_so_far<arr[index][coll])

max_so_far=arr[index][coll];

if(str[k]=='')

break;

coll++;

}

else

c=10*c+(str[k]-'0');

k++;

}

index=(index+1)%2;

}

final[i]=max_so_far;

max_so_far=-1;

}

for(i=1;i<=a;i++)

printf("%dn",final[i]);

return 0;

}

@ admin

please give me a test case for which the above posted code is not working..

Please, somebody, tell me, it's deikstra algorithm is here ?

Somebody please tell me why am I getting a runtime error:

http://www.codechef.com/viewsolution/269260

Can somebody please tell what is wrong with my code!!!,that it produces runtime error.It easily works in my pc for the worst case. :(

http://www.codechef.com/viewsolution/269260

abcd : I am not sure if this is the (only) reason causing it , but sometimes Integer.parseInt() returns a NumberFormatException if there are any trailing spaces after the integer and at least the sample test case does. I'd recommend trimming the read line using trim() ... try passing in.readLine().trim() to Integer.parseInt and see if that works.

@Antapreet Singh

Thanks again,the runtime error is now removed :) ,But now I am facing a wrong answer :(

Please check if my algo is wrong:

(coz u gave a good example in tidying posters)

I start from the bottommost row and move upwards or up-leftwards depending on the element at these positions which is greater.

max_sum(x,y)=max_sum(x,y)+max{element(x-1,y),element(x-1,y-1)}

and then check for the max sum (after checknig sum for each element in the bottom most row.Bottommostrow only because every path has to terminate there.)

 

A simple example of why a greedy approach has no chance of being correct:

1
6
1
1 1
1 99 1
2 1 1 2
1 2 1 2 1
1 1 1 1 1 1

Try the following test case : (Expected output is 7 )

1
4
1
1 3
2 1 1
1 2 1 1

Dear admin, please re-run the #1 solution. After successfully reaching #2 place i was able to re-test the #1 solution on my own PC and it was far away from reaching 0.00 sec with 0MB ...

sum1 give me the code....nt able to solve this....without iteration

plz sum1 post his/her code here..

tested my code on 1000 random cases on my machine

the code is working fine on my system

byt throwing runtime error(NZEC ) here.......

any suggestions??

but*

Hi admin

 

I am using java as programming language and trying to solve the problem using recursion but i m getting time limit exceeded.

Can you please look into the solution and inform me where i am wrong

Please mail me at shashikant.awasthi@gmail.com

@Admin: I'm a bit confused about the second input... it says: "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;" so for the second input the path should be 1 2 4 3 and thus the answer would be 10, but it shows the answer is 9.how the path is 1 1 4 3 ? please explain.

thanks

The number directly below the 2 in the second row is 1, and the number below and one place to the right is 2. So you can't possibly move from 2 to 4 like in your solution.

contents of trinagle for example

 

1

2 3

3 5 7

9 3 1 2

 

how it is supposed to enter 1 than enter 2 than enter 3 than enter like that ?

 

I am confused with the first condition

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;

 

for example

if the input is

1

5

1

1 2

1 2 3

1 2 3 4

1 2 3 4 5

 

so what should be the total?

Is it  1 + 1 + 1 + 1 + 1 = 5

or

1 + 2 + 3 + 4 + 5 = 15

There are lots of valid paths, including both the ones you mentioned, as well as something like 1+2+2+2+3, and so on. The path with maximum sum is 1+2+3+4+5=15.

a simple bottom up DP problem...

let

d[101][101] be the input data

 

a simple bottom up dp should be like this :

 

d[i][j] depends on d[i-1][j-1]  and d[i-1][j-1]

 

so for(i=0;i<=n;i++)

d[0][i]=d[i][0]=0

Okay

now

for(i=1;i<=n;i++)

for(j=1;j<=i;j++)

d[i][j]=max(d[i-1][j-1],d[i-1][j])

here last row d[n][1....n] contains the result

so find the maximux for the last of row.

really easy one!

Just a simple dynamic algorithm would do well!

This problem is interesting.

Don't use recursive, you will got time limit exceeded. Use looping method.  :)

can someone help me in solving this? My solution is coded like this:

 

1. tc=input()
2. while tc>0:
3. rows=input()+1
4. data=[[0 for j in xrange(rows-1)]for k in xrange(rows-1)]
5. data=[[input() for k in xrange(j+1)]for j in xrange(rows-1)]
6. for j in range(rows-1):
7. for k in range(j):
8. data[j][k]+=max(data[j-1][k-1], data[j-1][k])
9. print max(data[rows-2])
10. tc-=1

The number of rows can also be equal to 100 contrary to what the description says. My program crashed because of this first.

You can use my testcases to test your program locally if you like: http://ul.to/u8mwex

No, the number of rows cannot be equal to 100. Your code was crashing because an array of size 98 only stores enough room for 98 rows (0, 1, .., 97).

I am getting ":( internal error occured in  the system". What does this error imply?

I got time limit exceeded whit a dynamic algorithm, and it got accepted on the train site of the caribbean ACM-ICPC on 1000ms so.???? ;(

I am getting the WA with this code.Anyone plz help.

 

#include<iostream>

#include<stdlib.h>

using namespace std;

 

long long array[101][101]={0},ans,ans1,a,b;

long long recurse(long long ans1,long long i,long long j,long long n);

 

int main()

{

long long i,j,n,sum,tests;

cin >> tests;

while (tests--)

{

cin >> n;

for ( i = 0 ; i < n; i++)

{

for ( j = 0 ; j <= i ; j++ )

{

cin >> array[i][j];

}

}

ans=array[0][0];

ans1=0;

long long sum = recurse(ans1,0,0,n);

cout << sum << endl;

}

}

 

long long recurse(long long ans1,long long i,long long j,long long n)

{

if ( i == n-1 )

return ans;

else{

ans += max(recurse( array[i+1][j] , i+1,j,n ),recurse( array[i+1][j+1] , i+1,j+1,n));

}

}

http://www.codechef.com/viewsolution/366040

 

my program is exceeding time limits, can anyone please suggest something.

There could be up to 2^100 possible paths, so trying them all will never work in time. The aim of this problem is finding a way to guarantee you've found the best sum without trying every path individually.

#include<stdio.h>
int main()
{
int n, i, j,k,sum1,sum2, lines, *array[100];
scanf("%d", &n);
for(i = 1; i<=n; i++){
scanf("%d", &lines);
for(j = 0; j < lines; j++){
array[j] = (int*)malloc((j+1)*sizeof(int));
for(k = 0; k < j+1; k++){
scanf("%d", &array[j][k]);
}
}
for(j = lines-2; j >= 0; j--){
for(k = 0; k <= j+1; k++){
if((sum1 = (array[j][k]+ array[j+1][k])) > (sum2=(array[j][k]+array[j+1][k+1])))
array[j][k] =  sum1;
else
array[j][k] = sum2;
}
}
printf("%d", array[0][0]);
}
return 0;
}

 

Can any one please help why is this showing a wrong answer and that too for which test case

Your program gives the wrong output for the sample input. Read the FAQ if you aren't sure how to test your code.

Hi there Admin, are there any plans to let us coders know which testcase produced a wrong answer kind of like in TC?

SB

I don't have any clue what to do in this one... I've spent hours thinking about what the correct method is, and have got nowhere... help me!

plz help with my code, i cant find any error, is it the input output method? plz chk..

 

#include<stdio.h>

 

#define max 105

int main()

{

int a[max][max]={-1};

int f[max][max]={-1};

int i,j,t,n,ans=-1;

//int m, l[max-1][max-1]={-1};

 

scanf("%d",&t);

 

while(t--)

{

scanf("%d",&n);

for(i=1;i<=n;i++)

for(j=1;j<=i;j++)

scanf("%d",&a[i][j]);

 

/*

for(i=1;i<=n;i++)

for(j=1;j<=i;j++)

printf("%d",a[i][j]);

*/

 

f[1][1]=a[1][1];

 

for(i=2;i<=n;i++)

for(j=1;j<=i;j++)

{

if(f[i-1][j]>f[i-1][j-1])

{

f[i][j]=f[i-1][j]+a[i][j];

//l[i-1][j]=j;

}

else

{

f[i][j]=f[i-1][j-1]+a[i][j];

// l[i-1][j]=j-1;

}

}

 

for(j=1;j<=n;j++)

{

if(f[n][j]>ans)

ans=f[n][j];

//m=j;

}

 

/* for(i=1;i<=n;i++)

{

for(j=1;j<=i;j++)

printf("%d  ",f[i][j]);

printf("n");

}

for(int i=0;i<n;i++)

{

printf("%d ",l[i][j]);

}

printf("%d",m);

*/

printf("%d",ans);

}

 

return 0;

}

my program is not taking too much of memory n the output am getting on my system is also correct but am getting runtime error dont know y?????..can sum1 plz help me wid my code http://www.codechef.com/viewsolution/392161

can anybody help me to get rid of runtime error in this code plzzzz    help me

#include<stdio.h>
#include<stdlib.h>
//int line;
int max(int *a,int i,int k)
{
int j,l;

if(a[0]==1)
return a[1];
else
if(k<a[0])
{
j=(j=max(a,i+k,k+1))>(l=max(a,i+k+1,k+1)) ?j:l;
return j+a[i];
}

else
return 0;
} 

int main ()
{

int a[4950],*b,i,t,j=0;
scanf("%d",&t);
b=(int *)malloc(sizeof(int)*t);
while(t>0)
{
t--;
scanf("%d",&a[0]);
a[0]=a[0]*(a[0]+1)/2;
for(i=1;i<=a[0];i++)
scanf("%d",&a[i]);
b[j]=max(a,1,1);
//printf("n sum=%d",max(a,1,1)) ;
j++;
}
for(i=0;i<j;i++)
printf("%dn",b[i]);
return 0;
}

@admin i wrote the code using recursion it works perfect on my pc

here it says time limit exceeds

i dont care if it exceeds :))

and plz suggest ways to fix time problem( i use 'C')

p.s it was a goooood problem

 

 

You've tested it on an input with 99 rows, right?

class triangle1
{   
public static void main(String args[])throws java.lang.Exception
{
byte a,i,j,k,l;
String s;
int tr[][]=new int[100][100];
int max;
java.io.BufferedReader br =new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
s=br.readLine();
a=Byte.parseByte(s);       
for(i=1;i<=a;i++)
{
s=br.readLine();           
j=Byte.parseByte(s);                   
s=br.readLine();   
tr[1][1]=Integer.parseInt(s);                   
for(k=2;k<=j;k++)
{
String I[]=br.readLine().split(" ");
for(l=1;l<=k;l++)
{
tr[k][l]=Integer.parseInt(I[l-1]);                           
}
}
for(k=j;k>1;k--)
{
for(l=1;l<j;l++)
{
if(tr[k][l]>=tr[k][l+1])    max=tr[k][l];
else max=tr[k][l+1];
tr[k-1][l]=max+tr[k-1][l];                   
}
}
System.out.println(tr[1][1]);                   
}       
}   
}

 

can u plz tell me admin why am i having runtime error when its mery is only 177.3

Java guys, be aware!!

The test input has a trailing(or leading) space in lines.

String.trim() your line before you split!! Else, you will get a runtime error.

Used a memoized java code......Input using Sanner...but still saying TLE...any suggestions admins?/???

A lot of TLE for my solutions in Perl. It is totally equivalent in terms of complexity to others C codes that have passed. Please, consider a reasonable TL for Perl.

My solution worked with the examples but here it says 'wrong answer'. I've used recursion with memoization.

any correct submission using a recursive approach in java?

@admin while using recursion i am getting time limit exeed why?? #include int a[102][102]; int rec(int i,int j,int row) { int temp,temp1,max=0; if(i==row-1) { return a[i][j]; } if(i>=j) { temp=rec(i+1,j,row); temp1=rec(i+1,j+1,row); if(temp+a[i][j]<=temp1+a[i][j]) { max+=temp1+a[i][j]; } else { max+=temp+a[i][j]; } return max; } } int main() { int n,row; scanf("%d",&n); while(n--) { int i,j; scanf("%d",&row); for(i=0;i

Ridiculous. I have the most optimal solution which takes O(height) to try out all paths and then give you an answer. Yet it still exceeds time limit? Useless.

recursive algo with memoization will do the trick. Find memoization technique here: http://en.wikipedia.org/wiki/Memoization

Is it unable to do anything while reading the input???

#include int main() { //freopen("sumintri.in","r",stdin); //freopen("sumintri.out","w",stdout); int t; scanf("%d",&t); while(t--) { int n,i,j,a[110][110],max=0; scanf("%d",&n); for(i=0;i0) { if(a[i-1][j]>a[i-1][j-1]) a[i][j]+=a[i-1][j]; else a[i][j]+=a[i-1][j-1]; if(i==(n-1)) {if(a[i][j]>max) max=a[i][j];} } } } printf("n"); /*for(i=0;i

@ADMIN please check my solution, I know u r getting many of these requests but my problem is that I am getting different errors : "wrong ans", "time limit exceeded","runtime error"- on the same code submission. What is more amusing is that it is giving correct answer in all the test case such the one posted by triplem and fo3mix. Please chk it here : http://www.codechef.com/viewsolution/585678

@Admin With reference to my last post- I have used a recursive algorithm in c++ with memoization, similar to the tutorial of this problem...Please help !!

@trojan_horse: http://www.codechef.com/viewsolution/585678 change the base case condition of solve(i,j) instead of "if(i > univ_n)" it should be "if( i >= univ_n)" :) :)

Can anyone help in reducing time?? Heres my solution: http://www.codechef.com/viewsolution/595754

@gagangupt16: You will need to think of some other way of solving this problem

@gagan: Try DP. That must do the trick :)

@admin this working fine but why result is Wrong Answer, i have Gone through FAQ also..n import java.io.BufferedReader; public class Main { public static void main(String arg[])throws Exception { int a[][],d[][],i,j,max,readnum,t[],o; String strLine, strNum[]; BufferedReader br = new BufferedReader(new java.io.InputStreamReader (System.in)); int n=Integer.parseInt(br.readLine()); t=new int[n];o=0; while(n-->0) { int line = Integer.parseInt(br.readLine()); readnum=line; a = new int[line][line]; for(i=0;id[i-1][j-1]?d[i-1][j]:d[i-1][j-1])+ a[i][j-1]; } line=readnum-1; max=d[line][1]; for(i=2;i

getting a runtime error ? here is the solution .. http://www.codechef.com/viewsolution/630101

plzzzz sm1 help me out. this above code is working on my computer. but wen i submitted it..it showws runtime error....plz sm1 ...help... #include int rec(int n) { if(n==0) { return 0; } else return (n + rec(n-1)); } void sumoftriangle(int a) { int arr[1000]; int c; int d[10]; int k; int i=0; int p=0; int q=1; int r=2; int x; int y; int z; int f; int b; int v; int n=a; int l,j; int e; c=a+1; e=rec(c); for(k=0;kd[j]) { int temp=d[l]; d[l]=d[j]; d[j]=temp; } } } printf("nn%dn",d[n-1]); } int main() { int m; int g; int a; int e; scanf("%d",&m); for(g=0;g

#include int rec(int n) { if(n==0) { return 0; } else return (n + rec(n-1)); } void sumoftriangle(int a) { int arr[1000]; int c; int d[10]; int k; int i=0; int p=0; int q=1; int r=2; int x; int y; int z; int f; int b; int v; int n=a; int l,j; int e; c=a+1; e=rec(c); for(k=0;kd[j]) { int temp=d[l]; d[l]=d[j]; d[j]=temp; } } } printf("nn%dn",d[n-1]); } void main() { int m; int g; int a; int e; clrscr(); scanf("%d",&m); for(g=0;g

plzzzz sm1 help me out. this above code is working on my computer. but wen i submitted it..it showws runtime error....plz sm1 ...help... http://www.codechef.com/viewsolution/668164

@Admin: please look into this solution(http://www.codechef.com/viewsolution/675828) it has compiled successfully on my pc, but i am getting runtime error. I have tried nearly every approach that i could think of.

@Admin I am getting runtime error.My code works fine on my system. here is the ID..681980 Can you please help

#include int main() { int n; int arr[100][100]; scanf("%d",&n); while(n>0) { int rows; scanf("%d",&rows); int i,j; for(i=1;i<=rows;i++) { for(j=1;j<=i;j++) { scanf("%d",&arr[i][j]); } } for(i=1;i<(rows);i++) { for(j=1;j<=i;j++) { if(arr[i][j]+arr[i+1][j]>arr[i][j]+arr[i+1][j+1]) { arr[i][j]=arr[i][j]+arr[i+1][j]; } else arr[i][j]=arr[i][j]+arr[i+1][j+1]; } } int z,y,s,temp; y=arr[1][1]; for(z=1;z=y) { temp=arr[z][s]; arr[z][s]=y; y=temp; } else continue; } } printf("%d",y); n--; } return 0; } wats wrong in this code...help me out ...ny body :( ;(

can any body tell me why i`m gett`n rumtime error http://www.codechef.com/viewsolution/701335

Hi. Just got here. So we can't take more than 1 number from the same row to calculate the sum (for one path), right?

#include void main() { int n[99],rows,sum=0,i,j; cout<<"number of rows such between 0 to 100" <>rows; cout<<"enter the numbers that form the triangle"<>n[i]; cout<

i dint get the problem..please explain

so in case of a 2 digit numbers like for a triangle with testcase 1 and number of lines 3 1 99 3 3 66 5 the path should be 1->99->66 or 1->9->6 ??