CodeChef - Please like me

Question

In a far away dystopian world, the measure of the quality of a person’s life is the numbers of likes he gets for an article about their life. For a person to stay alive, he has to acquire at least L number of likes before D days pass.

People in this world employ various techniques to increase the number of likes. One of the famous ones is to dis-like and re-like their own article once per day. On doing so you can assume that the number of likes for the post increase by a constant factor C.

So if one starts with S likes on Day-1, he would have D2 = S + C * S likes on Day-2, D3 = D2 + D2 * C on Day-3 etc. You are to answer if the person would survive at the end of Day-D or not.

Input

First line contains a single positive integer T denoting the number of test cases. The following T lines represent a test case each. Each test case contains 4 space-separated integers L, D, S and C.

Output

For each test case, print a single line containing "ALIVE AND KICKING" if the person would live, otherwise print, "DEAD AND ROTTING".

Constraints

1 <= T <= 1000

1 <= L <= 1000000000

1 <= D <= 1000000000

1 <= S <= 1000000000

1 <= C <= 1000000000

Sample cases:

Input

2

5 1 5 1

10 2 2 2

Output

ALIVE AND KICKING

DEAD AND ROTTING

#include <stdio.h>
int main()
{
 int t;
 scanf("%d",&t);
 while(t--)
 {
 long long int l,d,s,c;
 scanf("%lld%lld%lld%lld",&l,&d,&s,&c);
 long long int i;
 long long int x=s;
 for(i=2;i<=d;i++)
 x*=(1+c);
 if(x>=l)
 printf("ALIVE AND KICKING\n");
 else
 printf("DEAD AND ROTTING\n");
 }
 return 0;
}

How do I improve efficiency so that the time limit does not get exceeded?

• agtoever: Use the power operator: pow, from math.h. 5*5*5*5=pow(5,4). So (d-1) times (1+c) multiplied is: pow( (1+c),(d-1) ). I think you can work it out from here.
• Atul Shanbhag: i made my own power function (refer to exponentiation by squares) but that gave me wrong answer
• agtoever: Check this answer for a reference implementation of an integer power function. Much faster than pow too.

Answer 1

I think the key thing you are missing isn't a better pow function. The problem is that you are iterating d times without checking whether you have surpassed l. Notice that for the lowest c of 1, you are multiplying by 2 every loop. The maximum l is 1000000000 which is less than 2^30. Therefore the max number of loops you will ever need is 30.

If you simply checked every loop:

if (x >= l)
 break;

then you limit your loop to 30 iterations instead of 1000000000 iterations.

Answer 2

The problem with using a power function was that it returns a floating value. My variables are of type int. I changed them to double and used the pow function from math.h library and it worked.

I was also successful by using my own power function using the exponentiation by squares algorithm.

Here is my power function (using the exponentiation by squaring algorithm):

int power(int x, int n)
{
 if(n==0)
 return 1;
 else if(n==1)
 return x;
 else if(n%2==0)
 return power(x*x,n/2);
 else if(n%2!=0)
 return x*power(x*x,(n-1)/2);
}

• agtoever: Great that you solved it. For completeness, could you add you implementation of the integer pow function in your answer?
• Ext3h: @AtulShanbhag Since your function only operates on integers, so that's not a problem. Negative exponents don't really make sense for integer return values, since x can't take values in the range ]0,1[, so for any negative exponent the result would be in this range as well. You might want to consider error handling, should someone provide a negative exponent or just change the parameter type to unsigned int.
• Atul Shanbhag: In that case, I would simply change my function and variable x from int type to double type. Then I would add an extra if statement that if(n<0) return power(1/x,-n);
• agtoever: Use bitwise operators to speed it up even more: n&1 to test uneven (logical AND); n<<1 for *2 (bitshift left) and n>>1 to /2 (bitshift right).
• JS1: You need to handle overflow, otherwise your function could end up returning anything, including 0 or a negative number.