Time Limit exceed

general
,
1

i am getting time limit exceed in my program and i am not getting whats the problem the question is Please Like me

    itr = int(raw_input())
arr = []
for i in xrange(0,itr):
	inp = raw_input()
	a , b , c , d = [int(d) for d in inp.split()]
	for j in xrange(1 , b):
		c= c + (c*d)
	if c>=a:
		e = "ALIVE AND KICKING"
	else:
		e = "DEAD AND ROTTING"
	arr.append(e)
for i in xrange(0 ,itr):
	print arr[i]
1 Like
2

@dpmittal: you are getting TLE because you are iterating b times to calculate final c for every input. you are taking T*D computations to complete one test file and this will lead to TLE because T,D are very large and the time limit is 1sec in which you can compute 10^7 to 10^8 computations. you can optimize that to a very large extent by using basic maths.

  • if you observe it carefully D2=(S)+Ā©(S). if you take S common then you get S(1+C) for D2
  • similarly D3=(D2)+Ā©(D2) again taking D2 common you get D2(1+C) but D2=S(1+C) from above point. So finally D3=S(1+C)^2 similarly D4=S(1+C)^3 and so onā€¦
  • so you just need to check whether S(1+C)^D-1 is greater than or equal to L then print ALIVE else DEAD.
  • you need not save it in an array because you can print it directly again traversing array is waste of time.

I hope you understand. If this is helpful to you upvote and accept my answer. happy coding :slight_smile:

1 Like
3

The condition to be checked is:s((1+c)^d-1)>=l; this is the same condition you have used but to check this condition ,there is no need to find value of s((1+c)^d-1),which is the wrong you have commited.long long int can store up to 10^18 only but the left hand side value will be much more than that resulting in overflow which is the reason for your wrong answer ot tle. A simple implementation like this would suffice:

Psuedo Code:

{

c++;

long long int count=1;

while(s<l)

{

s=s*c;

count++;

}

if(d>=count)

print(ā€œALIVE AND KICKINGā€)

else

print(ā€œDEAD AND ROTTINGā€)

}

4

You need not print all the answers at a time. Means you need not store the answers in an array(in this case you are using arr[]). You can print them after checking for each case.

5

it is still resulting in TLE

6

sorry for the above explanation, this logic is working in C but getting TLE in python. do one thing in your above mentioned code do not iterate from(1,b) stop iteration when ever you exceed ā€˜aā€™ in your program and break the ā€˜forā€™ loop because you need not iterate further if you got minimum number of likes. this will work you can view at my code which is coded on the basis of your logic CodeChef: Practical coding for everyone thank you :slight_smile: donā€™t forget to accept my answer :stuck_out_tongue:

7

thanx @pudge pls like rate my question if find it common

8

the formula s((1+c)^d-1) can be thought of as derived from the compund interest formula:A=P((1+r/100)^n) where P is s,r/100 is c and n= d-1.