PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: erdosnumber
Tester: tabr
Editorialist: iceknight1093
DIFFICULTY:
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
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
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
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
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[0],maxx=a[0]-a[1];
int sum=a[0]-a[1];
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);
}
}
string readOne() {
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);
string res = readOne();
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);
int res = stoi(readOne());
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);
long long res = stoll(readOne());
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++) {
res[i] = readInt(min_val, max_val);
if (i != size - 1) {
readSpace();
}
}
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++) {
res[i] = readLong(min_val, max_val);
if (i != size - 1) {
readSpace();
}
}
return res;
}
void readSpace() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == ' ');
pos++;
}
void readEoln() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == '\n');
pos++;
}
void readEof() {
assert((int) buffer.size() == pos);
}
};
int main() {
input_checker in;
int tt = in.readInt(1, 1e5);
in.readEoln();
int sn = 0;
while (tt--) {
int n = in.readInt(2, 1e6);
in.readEoln();
sn += n;
auto a = in.readLongs(n, 0, (int) 1e9);
in.readEoln();
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);
in.readEof();
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[0]
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')