Rupsa and Game puzzle

general
,
1

Can someone please help me understand the problem with my solution for Rupsa and Game problem
Solution : https://www.codechef.com/viewsolution/14669350

2

If you are a beginner, skip this problem. Its NOT a beginner problem, its a easy-medium problem (more on medium side) and needs you to know some tricks to solve. Try solving other problems in beginner section for now.

EDIT-So i went through your code.

  1. Dont use scanner. Google and look for fast I/O in JAVA. Scanner takes A LOT of time for your Input and can lead to TLE.

  2. Look at constraints. The answer can easily cross the range of 10^18 (limit of long) and you dont have any suitable data type to store the answer. This gives you WA in earlier test cases, because overflow leads to wrong answer. You need to continuously do modulo at each step to ensure that answer is awlays in range of your data type. Also, dont use int here as calculations go upto 10^18, use long this time and perform module at every recursion. (Change this to- sum = findSum(arr[index], end,index+1, arr,len,sum+start* arr[index]) + findSum(start, arr[index], index+1, arr,len,sum+end * arr[index] )%1000000007;
    With this, you should be able to pass first sub task in my opinion, and fail and get TLE, or runtime error in other 2 larger sub task.

  3. You complexity looks like O(2^N) which can take hours or days to complete. A simple recursion is not the solution (hence why this problem is more on medium side).

  4. Give a read to overflow, and tricks like fast exponentiation. Also read its editorial so you get what mathematics is used to arrive at the result. Then, re attempt the problem later, (atleast 3 days later so you forget the “memorised” stuff and think on your own).

3

Can you please take a look at my solution. i tried solving it recursively and am getting expected answer when running locally.Appreciate your help

4

Okay, i will have a look.