Why ?
3 Likes
Consider the test case
2
-1 -6
2
1 1
The Setters solution outputs the answers as
999999993
999999979
Why would you deliberately make the sum positive? There was nowhere mentioned in the problem that you have to output only the positive number.
What I understand is \ a \% \ b \ = \ a \ - \large (\frac{a}{b}) *\ b
If we put the sum as \ a and the mod as \ b and the value of to be less than mod then the \large \frac{a}{b} term becomes zero and we are left the number itself.
It would be great if someone could clarify it. I also read the answer on stack overflow, I didn’t find it useful.
5 Likes
if a system is N-modular
then it can have integers in the domain
D = {0, 1, 2, ..., N-1}
let say we have a integer value X
if an integer X is in D
we interpret it as X only
else if a integer X is greater than N-1
then we interpret it as X % N
otherwise if integer X is less than 0
then we interpret it as min(X + p*N)
such that X+p*N is in domain D
where p is positive integer
i.e. we keep on adding N's to X till we reach in the
domain {0,1,..,N-1}
for e.g. 12hr clock system ,
where we have 15:00 interpreted as 3:00
& 20:00 interpreted as 8:00
In the problem it’s 10^9+7 modular system
(but not explicitly specified or not focused upon)
hence
domain D = { 0, 1, 2, ..., (10^9+7)-1 }
Therefore, in setter’s soln
we are making -ve sum*(bcoz of it’s invalidity in domain D)* as +ve
hence Intially
sum %= MOD;
if (sum < 0) sum += MOD;
alternatively we can do this by adding (10^9+7) repeatedly(i.e. p times) to sum (to enter into the valid domain D)
if( sum < 0){
while(sum < 0){
sum += MOD;
}
}else if( sum>=MOD) {
sum = sum % MOD
}else{
// already in domain
}
this concept is mentioned in some book or online site, the source(from where i read this) i don’t remember currenty.
Correct me if something’s wrong,
17 Likes
can you give some hint about the bonus problem ?
because see -1%3 = -1 but answer should be +ve so -1%3 = (-1 + 3 ) %3 = 2 (this is in c++ )
while in python -1 % 3 = 2
Array Rotation[ARRROT] , April Lunchtime 2021 , Why WA for many users? - general - CodeChef Discuss
why the number should have to be possitive ??
because in CP ,as far as I know , if we have print -ve value % mod then we have to print +ve answer only … I know setter has to write in question u have to remember this , by default we have to print +ve value only.
2 Likes
so can we say like this mod value have to lie between 0 to mod-1 ?
obviously
1 Like
True
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.
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
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 
True
bro in case x=0 means no rotation then why multiply by 2 ans will wrong