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