ARRROT - Editorial

mod(remainder should be always positive). You can check on any ide -8mod5 . It is giving -3 but actual answer should be 2

Anyone, please tell me why am I getting TLE for this code.

https://www.codechef.com/viewsolution/45664226

Use pow instead of ** for exponentiation in the loop and this question can be done without exponentiation also.

using namespace std;
const unsigned int M = 1000000007;

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);

  l n ; cin >>n; 
  
    l sum=0;
    for ( l i  = 0 ; i  < n ; i++ ){
      l var;  cin >> var ;


      if ( var<0){
          sum+=(var%M+M)%M;

      }
      else{
          sum+=var%M;
      }


        sum= sum%M;  
    }

    l q; cin >> q;

    for ( l j=0 ; j <q; j++){

          sum+=sum;
        sum = sum%M;
        cout << sum<<endl;

 
    }

return 0 ;
}

just take care of modulo while taking input

try not using exponentiation.
Check a modified solution here.

1 Like

We want to output the answer in modulo field of MOD 10^9+7. So any number outside that range shall correspond to one value in range [0, 10^9+6].

For some x, we want to find y such that x = y + c*MOD and y \in [0, 10^9+6]. It can be see that for each x, there’s a unique y and c. You’d need to read on modular arithmetic, here and here

My idea for bonus problem is that since range [L, R] would be something like suffix of a rotation of A + Rotations of array A repeated X times for some X \geq 0 + prefix of a rotation A. There can also be a case where [L, R] correspond to a subarray of a rotation of A.

The sum of middle part is fixed. We need to determine the rotation of A which covers position L and R. This is the tricky part. Something like divide and conquer is possible here. It’d take time proportional to the number of times the array size is doubled.

Since array length doubles after each operation, and we want to keep L and R in long long range, there cannot be more than 64 queries of first type. Let’s call that Q_1

Hence, the solution would be working in something like O(Q_1) for each query of second type.

Keep thinking for the exact approach :wink:

True

bro in case x=0 means no rotation then why multiply by 2 ans will wrong

Hello friend!! actually logically ans for negative sum doesnt make any sense at all.You have to blindly follow the logic for negative no. Hope that helps!!!

bro question tells us to find mod 10^9 + 7 hence for negative values we have to use that logic only. dont think about the ans if it is making any logic or not . u have to just use mod concept for negative no . That’s it!!! XD

Can anyone tell why it is showing TLE, when I directly perform modulo 10^9 +7)?
Also, please help me by telling what is the most efficient way of doing it.