ARRROT - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

Setter: Sambhav Jain
Tester & Editorialist: Taranpreet Singh

DIFFICULTY

Simple

PREREQUISITES

None

PROBLEM

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.

QUICK EXPLANATION

  • 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.

EXPLANATION

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.

Bonus

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?

TIME COMPLEXITY

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

SOLUTIONS

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);
#else
    #define eprintf(...) 42
#endif

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.*;
import java.io.*;
class ARRROT{
    //SOLUTION BEGIN
    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;
            pn(sum);
        }
    }
    //SOLUTION END
    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);
        out.flush();
        out.close();
    }
    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 in.next();}
    String nln()throws Exception{return in.nextLine();}
    int ni()throws Exception{return Integer.parseInt(in.next());}
    long nl()throws Exception{return Long.parseLong(in.next());}
    double nd()throws Exception{return Double.parseDouble(in.next());}

    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }

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

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

        String nextLine() throws Exception{
            String str = "";
            try{   
                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:

4 Likes

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: .

21 Likes

True

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

3 Likes

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

1 Like

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.

2 Likes

Including me.

6 Likes

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 ?

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

14 Likes

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.

2 Likes

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

obviously

1 Like

True