What is the mistake I have made in the question RGAME?

general
, , ,
1

Here is the problem:
https://www.codechef.com/problems/RGAME

I don’t know what error I have made. I am getting WA for all test cases. But I get the right answers for sample test cases. I have implemented according to the editorial given.

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<set>
#include<vector>
#include<utility>

#define MO 1000000007
using namespace std;

int main( ) {

    int t;
    cin>>t;

    long long int n, a[100004],suffix_sum[100004];
    long long int cost,prefix;

    while ( t-- ) {
        cost = 0;
        cin>>n;
        for ( int i = 0; i <= n; i++ ) {
            scanf("%lld", &a[i]);
        }

        suffix_sum[n] = a[n];

        for ( int i = (n-1); i >=1 ; i-- ) {
            suffix_sum[i] = ( (long long int)pow(2,(n-i)) * a[i] ) % MO ;
            suffix_sum[i] += suffix_sum[i+1];
        }


        for ( int i = 0; i <= n-1; i++ ) {
            if ( i == 0 ) {
                prefix = 1;
            }
            else {
                prefix = ( (long long int)pow(2,(i-1)) *  a[i] ) % MO;
            }
            cost += ( (prefix * suffix_sum[i+1]) % MO );
        }
        cout<<2*cost<<endl;
    }
    return 0;
}
1 Like
2

I am guessing that the built in pow() function for double/float exponentiation is causing some loss of precision. By definition, floats and doubles have limited precision. Try doing modular exponentiation by squaring. There are many implementations/tutorials online.

Here is my implementation, hopefully it will get you an AC :slight_smile:

// modpow(n, k) = n ^ k % MOD where MOD = 1e9+7
long long modpow(long long n, long long k) {
     long long r = 1;
     while (k > 0) {
        if (k % 2 == 1) 
            r = (r * n) % MOD;
        n = (n * n) % MOD;
        k /= 2;
     }
     return r;
}

if you have any questions, feel free to ask.

3

The time complexity of the function is O(log(n)) if you are wondering :smiley: It uses divide and conquer technique.

4

Hi, thanks for your suggestion. I tried replacing the pow function with the modpow function provided by you. But I still get WA. Any other ideas?