ARRROT - Editorial


Contest Division 1
Contest Division 2
Contest Division 3

Setter: Sambhav Jain
Tester & Editorialist: Taranpreet Singh






Given an array A of length N, handle Q queries of form, replace A with A + f(A, x) where f(A, x) is the cyclic shift of A x times (if x is positive, then right shift x times, else left shift |x| times.

After each query, print the sum of A.


  • Order of elements do not matter. We can assume A = A+A.
  • Since we only care about sum, each query multiplies the sum of values by 2.


The important thing to notice is that the order of elements do not matter at all. For all it matters, we can simply assume the operation as A = A + A, appending elements.

Even more, since each element is appended, the sum of updated array becomes twice the sum of original array.

Hence, we can simply take sum of all elements of A and answer queries based on the fact that each query doubles the sum of array A.

Example: considering array A = [1,4], following depicts the array after 3 queries.

sum([1,4,1,4]) = 10
sum([1,4,1,4,1,4,1,4]) = 20
sum([1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4]) = 40

We can state that the sum of array A after q queries is 2^q * T where T denotes the sum of initial array A.

Hence, we can take sum and then print answer after doubling the sum before each query.

Pitfalls: Since the initial sum can be greater than MOD, do remember to take remainder of T when divided by MOD. T can be negative too.


Given array A of length N, handle operations as follows.

  • Replace A with A+f(A, x)
  • Find sum of subarray [L, R]

Can you think of any approach apart from brute force?


The time complexity is O(N+Q) per test case


Setter's Solution
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
using namespace std;

#ifdef LOCAL
    #define eprintf(...) fprintf(stderr, __VA_ARGS__);fflush(stderr);
    #define eprintf(...) 42

using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
    return (ull)rng() % B;

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second

clock_t startTime;
double getCurrentTime() {
    return (double)(clock() - startTime) / CLOCKS_PER_SEC;

ll MOD = (ll)1e9 + 7;

int main()
    startTime = clock();
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);

    int n;
    scanf("%d", &n);
    assert(n <= 100000);
    ll sum = 0;
    while(n--) {
	    ll x;
	    scanf("%lld", &x);
	    sum += x;
    sum %= MOD;
    if (sum < 0) sum += MOD;
    scanf("%d", &n);
    assert(n <= 100000);
    while(n--) {
	    sum += sum;
	    if (sum >= MOD) sum -= MOD;
	    printf("%lld\n", sum);

    return 0;
Tester's Solution
import java.util.*;
class ARRROT{
    void pre() throws Exception{}
    void solve(int TC) throws Exception{
        int N = ni();
        long sum = 0, MOD = (long)1e9+7;
        for(int i = 0; i< N; i++)sum += ni();
        sum %= MOD;
        if(sum < 0)sum += MOD;
        int Q = ni();
        for(int q = 0; q< Q; q++){
            int x = ni();
            sum += sum;
            if(sum >= MOD)sum -= MOD;
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    static boolean multipleTC = false;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        in = new FastReader();
        out = new PrintWriter(System.out);
        //Solution Credits: Taranpreet Singh
        int T = (multipleTC)?ni():1;
        pre();for(int t = 1; t<= T; t++)solve(t);
    public static void main(String[] args) throws Exception{
        new ARRROT().run();
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object o){out.print(o);}
    void pn(Object o){out.println(o);}
    void pni(Object o){out.println(o);out.flush();}
    String n()throws Exception{return;}
    String nln()throws Exception{return in.nextLine();}
    int ni()throws Exception{return Integer.parseInt(;}
    long nl()throws Exception{return Long.parseLong(;}
    double nd()throws Exception{return Double.parseDouble(;}

    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(;

        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));

        String next() throws Exception{
            while (st == null || !st.hasMoreElements()){
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    throw new Exception(e.toString());
            return st.nextToken();

        String nextLine() throws Exception{
            String str = "";
                str = br.readLine();
            }catch (IOException e){
                throw new Exception(e.toString());
            return str;

Feel free to share your approach. Suggestions are welcomed as always. :slight_smile:


I think almost 90% of the people who submitted a solution to this problem got WA in first attempt because of negative numbers. Even me :frowning: .



I have still not understood why negative sum makes difference in answer…


Can you tell me…why we are changing negative answers to positive


It makes a difference because the “%” operator does not do what you think it does i.e the MOD operation. Refer this stackoverflow question for more details.


Including me.


can someone tell how to solve bonus problem?without brute force??

in the setter’s solution we find the sum then we take the mod till here it’s fine but why we have to check if it’s less than 0 and if it is why we add mod?

1 Like

Why ?


Consider the test case

-1  -6 
1 1

The Setters solution outputs the answers as


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.


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)


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
    // 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,


can you give some hint about the bonus problem ?

i also cant understand please explain @taran_1407 :pray: :pray:

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.


so can we say like this mod value have to lie between 0 to mod-1 ?


1 Like