Help in Rupsa and Game

help
,
1

Hey,
I was trying on the problem “Rupsa and the Game”. I found a algorithm for the answer and i coded it. I tested it with the example they gave and the answers matched. But when i submitted my solution it said the answers did not match.

Here is the link to my solution: https://www.codechef.com/viewsolution/14974347

Please, can somebody help me out.

2

pow(2,k);

Issue lies here. Do you think this will accurately compute 2^10000 or such large powers? Overflow is causing WA. Try looking for fast exponentiation and you should get AC.

3

But he is getting WA even for N<=10 subtask… I think there is something else too…

4

The problem page isnt opening so I cant confirm, but although N<+10 there, array element could be upto 10^9 and this can be reason of overflow and WA. Not sure about “long int” s limit, but i think its not 64bit

5

Yup… just realised that A_i can be upto 10^9

6

I think your logic is correct but there are few correction you have to made:

  1. Remove unnecessary \n from code.
  2. I used modulo properly to avoid overflow till a level and It got AC for first subtask. See it here.
  3. Use fast power method while calculating power of 2. and take care of modulo there too.

I used little different approach though, So I had not to calculate pow of 2 again and again. You can follow my solution here.