Unable to detect the error in my code

general
,
1

Hello, I am new to CodeChef, and tried out a beginner exercise “Rupsa and the Game” (Problem code: RGAME; url: https://www.codechef.com/problems/RGAME). When I run my code manually, it generates the output as demanded by the problem statement. However, when I submit it on codechef, it is always evaluated wrong. I tried out running my code on ideone.com as well, and the desired output is generated.

Here is my code:

import java.util.*;
class Rupsa_and_the_game {
    public static void main(String args[]) {
        int T, N;
        long A[], total_score[];
        Rupsha_and_the_game rg = new Rupsha_and_the_game();
        Scanner sc = new Scanner(System.in);
        T = sc.nextInt();
        total_score = new long[T];
        for(int i = 0; i < T; i++) {
            N = sc.nextInt();
            A = new long[N + 1];
            for(int j = 0; j <= N; j++) A[j] = sc.nextLong();
            total_score[i] = rg.calc_total_score(A) ;
            System.out.print( total_score[i] + "\n");
        }
    }
    public long calc_total_score(long A[]) {
        long sum_sequence = 0, total_score = 0, mod = 1000000007;
        for(int i = 1; i < A.length; i++) {
            if(i == 1) sum_sequence += A[i - 1] * 2;
            else sum_sequence += A[i - 1] * (long)Math.pow(2, i - 1);
            total_score = (2 * total_score + A[i] * sum_sequence) % mod;
        }
        return total_score % mod;
    }
}

I am unable to understand what is going wrong. Any help will be highly appreciated.

2

Overflow can be the culprit. This problem dealt a lot with big numbers. Do you think that long will store a number like (long)Math.pow(2, i - 1); when N can be upto 10,0000 (if i recall correctly). It will overflow here, giving WA. Your code should work for smaller cases though. I think this should require fast exponentiation.

BTW, if you are new to coding, please leave this problem for later. Its NOT beginner problem. Its a easy-medium, with a little bit on medium side in my opinion. When you learn some more tricks, then re-attempt it.

3

Thank you very much. :slight_smile: