PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: pols_agyi_pols
Tester: tabr
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Prefix sums, sorting
PROBLEM:
You’re given an array A, on which you can perform the following operation:
- Choose an index i (2 \leq i \leq N-2), and
- Set A_{i-1} := A_{i-1} + A_i + A_{i+1}
- Set A_{i} \hspace{3.2mm} := -A_{i+1}
- Set A_{i+1} := -A_i
- Set A_{i+2} := A_{i+2} + A_i + A_{i+1}
Is it possible to make A equal B after some sequence of moves?
EXPLANATION:
When dealing with operations on arrays that affect a small number of indices close to each other like this one, it’s often useful to look at its effects on either the prefix sums or the difference array of A.
In this case, we look at prefix sums.
Let P^{(A)} denote the prefix sum of A, so that
P^{(A)}_i = A_1 + A_2 + \ldots + A_i
Suppose we choose to operate on index i. How do the values of the prefix sum array change?
Answer
For j \lt i-1, P^{(A)}_j remains unchanged.
So, for convenience of indexing, we can assume i = 2, i.e, we’re changing only the first four elements of the array.
The array was initially [A_1, A_2, A_3, A_4, \ldots].
After the operation, it becomes [A_1+A_2+A_3, -A_3, -A_2, A_4+A_2+A_3].
Observe that:
- At index 1, the prefix sum was originally A_1, now it’s A_1+A_2+A_3.
- At index 2, the prefix sum was originally A_1+A_2, now it’s A_1+A_2+A_3-A_3 = A_1+A_2.
- Note that there’s no change here.
- At index 3, the prefix sum was originally A_1+A_2+A_3, now it’s A_1+A_2-A_2 = A_1.
- Note that the prefix sums at indices 1 and 3 have essentially swapped places after the operation.
- At index 4, the prefix sum was originally A_1+A_2+A_3+A_4, now it’s A_1+A_2+A_3+A_4.
- Note that there’s no change here as well.
- For indices \geq 5, the prefix sum doesn’t change; since P^{(A)}_4 was unchanged and elements at indices \geq 5 are also unchanged.
That is, the only thing that happened is that the first and third prefix sum swapped places!
Bringing this back to the original problem, performing the operation with index i essentially just swaps P^{(A)}_{i-1} and P^{(A)}_{i+1}.
In simpler words, our operation is simply to swap two alternate elements of P^{(A)}.
The only catch is that P^{(A)}_N (the last element) cannot be moved, since we can’t choose i = N-1.
It’s easy to see why via the lens of the operation itself too: this element represents the sum of the array, which doesn’t change after an operation.
Now that we’ve reduced our operation to swapping alternate prefix sums, let’s see if we can make the prefix sum array of A equal the prefix sum array of B — this will ensure that A and B are equal.
Since we can swap alternate elements of the prefix sum array of A, we can essentially:
- Freely rearrange the even-indexed elements of P^{(A)} among themselves.
- Freely rearrange the odd-indexed elements of P^{(A)} among themselves.
- Only the last element cannot be moved.
So, for P^{(A)} to become equal to P^{(B)},
- Their last elements should be equal (i.e, A and B should have the same sum).
- The even-indexed elements of P^{(A)} should form a rearrangement of the even-indexed elements of P^{(B)}.
- One way to check this is to sort both lists of even-indexed prefix sums and check if they’re equal.
- The odd-indexed elements of P^{(A)} should form a rearrangement of the odd-indexed elements of P^{(B)}.
- This can also be checked in the same way.
If all three conditions are satisfied, A can be made to equal B; otherwise it cannot.
TIME COMPLEXITY:
\mathcal{O}(N\log N) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll kitne_cases_hain;
kitne_cases_hain=1;
cin>>kitne_cases_hain;
while(kitne_cases_hain--){
ll n; cin >> n;
vector<ll> p1(n), p2(n);
vector<ll> p1o, p1e, p2o, p2e;
cin >> p1[0];
p1e.push_back(p1[0]);
for (ll i = 1; i < n; i++) {
cin >> p1[i];
p1[i] += p1[i-1];
if (i & 1) p1o.push_back(p1[i]);
else p1e.push_back(p1[i]);
}
cin >> p2[0];
p2e.push_back(p2[0]);
for (ll i = 1; i < n; i++) {
cin >> p2[i];
p2[i] += p2[i-1];
if (i & 1) p2o.push_back(p2[i]);
else p2e.push_back(p2[i]);
}
sort(p1o.begin(), p1o.end());
sort(p2o.begin(), p2o.end());
sort(p1e.begin(), p1e.end());
sort(p2e.begin(), p2e.end());
if (p1o == p2o and p1e == p2e and p1.back() == p2.back()) cout << "YES\n";
else cout << "NO\n";
}
return 0;
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif
#define IGNORE_CR
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;
}
#ifdef IGNORE_CR
if (c == '\r') {
continue;
}
#endif
buffer.push_back((char) c);
}
}
string readOne() {
assert(pos < (int) buffer.size());
string res;
while (pos < (int) buffer.size() && buffer[pos] != ' ' && buffer[pos] != '\n') {
assert(!isspace(buffer[pos]));
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(1, 2e5);
in.readEoln();
sn += n;
auto a = in.readLongs(n, -1e9, 1e9);
in.readEoln();
auto b = in.readLongs(n, -1e9, 1e9);
in.readEoln();
if (n <= 3) {
cout << (a == b ? "YES" : "NO") << '\n';
continue;
}
for (int i = 1; i < n; i++) {
a[i] += a[i - 1];
b[i] += b[i - 1];
}
vector<vector<long long>> x(2), y(2);
for (int i = 0; i < n; i++) {
x[i % 2].emplace_back(a[i]);
y[i % 2].emplace_back(b[i]);
}
for (int i = 0; i < 2; i++) {
sort(x[i].begin(), x[i].end());
sort(y[i].begin(), y[i].end());
}
if (x[0] == y[0] && x[1] == y[1] && a.back() == b.back()) {
cout << "YES" << '\n';
} else {
cout << "NO" << '\n';
}
}
assert(sn <= 2e5);
in.readEof();
return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
if sum(a) != sum(b):
print('No')
continue
prefa, prefb = [0], [0]
for x in a: prefa.append(prefa[-1] + x)
for x in b: prefb.append(prefb[-1] + x)
for st in range(2):
prefa[st::2] = sorted(prefa[st::2])
prefb[st::2] = sorted(prefb[st::2])
print('Yes' if prefa == prefb else 'No')