# ZERARR - Editorial

Author: erdosnumber
Tester: tabr
Editorialist: iceknight1093

2754

# PREREQUISITES:

Observation, basic algebra

# PROBLEM:

You have an array A.
In one move, you can subtract 1 from A_i and A_{i+1}; indices modulo N.

Is it possible to make every element of A become 0?

# EXPLANATION:

All indices mentioned below are cyclic modulo N and zero-based.
So, for example talking about A_{i-1} when i = 0 refers to A_{N-1} instead.

Let’s deal with the cases of even N and odd N separately.

Even N

First, note that every move subtracts 1 each from an odd index and an even index.
So, surely the sum of values at even and odd indices should be equal; for the array to end up with zeros.
If this check fails, the answer is No, so let’s assume it holds from now on.

Suppose we perform B_i moves on index i.
That is, we subtract 1 from the pair (A_i, A_{i+1}), B_i times.
In particular, the final value of A_i will be A_i - B_i - B_{i-1}.

Assuming that every element of A becomes 0 in the end, this gives us a system of equations in A_i and B_I.
Rearranging them a bit, it can be seen that

A_1 - B_1 - B_0 = 0 \implies B_1 = A_1 - B_0 \\ A_2 - B_2 - B_1 = 0 \implies B_2 = A_2 - B_1 = A_2 - A_1 + B_0 \\ A_3 - B_3 - B_2 = 0 \implies B_3 = A_3 - A_2 + A_1 - B_0 \\ \vdots \\ B_i = (-1)^iB_0 + \sum\limits_{j=1}^i (-1)^{i-j} A_j

Notice that fixing B_0 then fixes every other B_i, so we only really need to check if a value of B_0 exists such that every B_i becomes valid.
That is, we need to ensure that every B_i \geq 0, since it’s the number of moves we make.

Putting that into the equations we have, we obtain the constraints

B_0 \leq \sum_{j=1}^i (-1)^{j+1} A_j, \ \ \ \ \ \ \ \ \ \text{for odd } i \\ B_0 \geq \sum_{j=1}^i (-1)^{j+1} A_j, \ \ \ \ \ \ \ \ \ \ \text{for even } i

This gives us lower and upper bounds on the possible values of B_0.

Let the lower and upper bounds obtained this way be L and R.
Then, a valid solution exists if and only if:

• L \leq R
• R \geq 0

Which allows us to choose a non-negative value of B_0 in the range [L, R], hence satisfying all the equations and inequalities.

Finding L and R can be done in \mathcal{O}(N), since we’re really just looking at alternating prefix sums of A.

Odd N

Define B_i as in the even case.

The system of equations we set up is also exactly the same.
In particular, notice that this time, we have

B_{N-1} = B_0 - A_1 + A_2 - A_3 + \ldots + A_{N-1}

We also have A_0 - B_0 - B_{N-1} = 0, giving us B_{N-1} = A_0 - B_0.

Notice that this uniquely determines B_0, in particular

2\cdot B_0 = A_0 + A_1 - A_2 + A_3 - \ldots - A_{N-1}

B_0 has to be a non-negative integer, meaning the RHS has to be even and non-negative; if it isn’t, the answer is immediately No.
Otherwise, compute B_0, after which all the other B_i are uniquely determined as well.

So, compute all the other B_i and check if they’re all \geq 0.

# TIME COMPLEXITY

\mathcal{O}(N) per testcase.

# CODE:

Author's code (C++)

#include<bits/stdc++.h>
#define int long long
using namespace std;

void solve()
{
int n; cin>>n;

vector<int> a(n);
for(int i=0;i<n;i++) cin>>a[i];

if(n&1)
{
vector<int> b(n); //b[i] denotes the number of times the move is performed on (i,(i+1)%n)
int sum=0;
for(int i=0;i<n;i++)
{
if(i&1) sum-=a[i];
else sum+=a[i];
}
if(sum<0) cout<<"NO\n";
else if(sum%2==1) cout<<"NO\n";
else
{
b[n-1]=sum/2;
//b[i]+b[i+1]=a[i+1]
for(int i=n-2;i>=0;i--) b[i]=a[i+1]-b[i+1];

for(int i=0;i<n;i++)
{
if(b[i]<0)
{
cout<<"NO\n";
return;
}
}

cout<<"YES\n";
}
}
else
{
int sumodd=0,sumeven=0;
for(int i=0;i<n;i++)
{
if(i & 1) sumodd+=a[i];
else sumeven+=a[i];
}

if(sumodd!=sumeven)
{
cout<<"NO\n";
return;
}

int minn=a,maxx=a-a;
int sum=a-a;
for(int i=2;i<n;i++)
{
if(i%2==0)
{
sum+=a[i];
minn=min(minn,sum);
}
else
{
sum-=a[i];
maxx=max(maxx,sum);
}
}

if(minn>=maxx) cout<<"YES\n";
else cout<<"NO\n";
}
}

signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);

int t; cin>>t;
while(t--)
{
solve();
}
}

Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

struct input_checker {
string buffer;
int pos;

const string all = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const string number = "0123456789";
const string upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string lower = "abcdefghijklmnopqrstuvwxyz";

input_checker() {
pos = 0;
while (true) {
int c = cin.get();
if (c == -1) {
break;
}
buffer.push_back((char) c);
}
}

assert(pos < (int) buffer.size());
string res;
while (pos < (int) buffer.size() && buffer[pos] != ' ' && buffer[pos] != '\n') {
res += buffer[pos];
pos++;
}
return res;
}

string readString(int min_len, int max_len, const string& pattern = "") {
assert(min_len <= max_len);
assert(min_len <= (int) res.size());
assert((int) res.size() <= max_len);
for (int i = 0; i < (int) res.size(); i++) {
assert(pattern.empty() || pattern.find(res[i]) != string::npos);
}
return res;
}

int readInt(int min_val, int max_val) {
assert(min_val <= max_val);
assert(min_val <= res);
assert(res <= max_val);
return res;
}

long long readLong(long long min_val, long long max_val) {
assert(min_val <= max_val);
assert(min_val <= res);
assert(res <= max_val);
return res;
}

vector<int> readInts(int size, int min_val, int max_val) {
assert(min_val <= max_val);
vector<int> res(size);
for (int i = 0; i < size; i++) {
if (i != size - 1) {
}
}
return res;
}

vector<long long> readLongs(int size, long long min_val, long long max_val) {
assert(min_val <= max_val);
vector<long long> res(size);
for (int i = 0; i < size; i++) {
if (i != size - 1) {
}
}
return res;
}

assert((int) buffer.size() > pos);
assert(buffer[pos] == ' ');
pos++;
}

assert((int) buffer.size() > pos);
assert(buffer[pos] == '\n');
pos++;
}

assert((int) buffer.size() == pos);
}
};

int main() {
input_checker in;
int sn = 0;
while (tt--) {
sn += n;
auto a = in.readLongs(n, 0, (int) 1e9);
string ans = "Yes";
vector<long long> b(n);
for (int i = 0; i < n - 1; i++) {
b[i + 1] = a[i] - b[i];
}
long long t = 0;
if (n % 2 == 0) {
if (b[n - 1] != a[n - 1]) {
ans = "No";
}
for (int i = 0; i < n; i += 2) {
t = min(t, b[i]);
}
t = -t;
} else {
if (abs(b[n - 1]) % 2 != a[n - 1] % 2 || b[n - 1] > a[n - 1]) {
ans = "No";
} else {
t = (a[n - 1] - b[n - 1]) / 2;
}
}
for (int i = 0; i < n; i++) {
if (i % 2 == 0) {
b[i] += t;
} else {
b[i] -= t;
}
}
if (*min_element(b.begin(), b.end()) < 0) {
ans = "No";
}
cout << ans << '\n';
}
assert(sn <= (int) 1e6);
return 0;
}

Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
if n%2 == 1:
tot = a
for i in range(1, n):
if i%2 == 1: tot += a[i]
else: tot -= a[i]
if tot < 0 or tot%2 == 1: print('No')
else:
b0, cur = tot//2, 0
ans = 'Yes'
for i in range(1, n):
cur = a[i] - cur
if cur - b0 < 0: ans = 'No'
b0 *= -1
print(ans)
else:
if sum(a[::2]) != sum(a[1::2]):
print('No')
continue
lo, hi = -10**18, 10**18
cur = 0
for i in range(1, n):
if i%2 == 1:
cur += a[i]
hi = min(hi, cur)
else:
cur -= a[i]
lo = max(lo, cur)
if lo <= hi and hi >= 0: print('Yes')
else: print('No')

1 Like

Where can we find the video editorial of this?

1 Like

when considering the system of equations, why do we disregard the case of B0 ?
B0 = A0 - Bn-1 is the equation and it shows that B0 is dependent on Bn-1, so these Bis are cyclically dependent. So fixing any specific Bi (let say we start from B1) and then computing and verifying all other Bi would also work, right?

In short, what I am asking is that for the even case, one can do the same approach as mentioned in editorial starting with B1 and finding a valid value of B1 (or any Bi in general) ?

What you said works for the odd case; for the even case there isn’t in fact a cyclic dependency.

For the even case, if you write out the equations involving B_{N-1}, you’ll notice that B_0 cancels out from both sides.
In fact, simplify it a bit and you’ll be left with

A_0 + A_2 + A_4 + \ldots = A_1 + A_3 + A_5 + \ldots

which is something you already know (sum of even indices = sum of odd indices) from observing the process.

The even case has this extra bit of freedom, so the answer isn’t necessarily unique there - you’ll see the editorial finds a range of values for B_0, choosing any of them will work.

1 Like

I got it
Thanks @iceknight1093