PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: tabr
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Prefix sums
PROBLEM:
An anti-palindrome is an array where none of the opposite pairs of elements are equal.
An array is called beautiful if every cyclic shift of it is an anti-palindrome.
You’re given an array containing the elements 1, 2, 3 only.
Answer Q queries on it: given L and R, can the subarray A[L\ldots R] be rearranged to form a beautiful array?
EXPLANATION:
First, note that an odd-length array can by definition never be an anti-palindrome - the middle element will always equal its opposite (which is itself).
This also means an odd-length array can never be beautiful.
So, we only need to reason about even-length arrays.
Now, suppose A is a beautiful array of even length 2M.
Let’s see what that means about A_1 in particular.
- First, A_1 \neq A_{2M} since A is itself an anti-palindrome.
- Rotating to the right once, we find A_1 \neq A_{2M-2} must hold.
Note that this is because the array is now [A_{2M}, A_1, \ldots, A_{2M-2}, A_{2M-1}] - Rotating right once again, A_1 \neq A_{2M-4} must hold.
\vdots - For the final right rotation, A_1 \neq A_2 must hold.
So, we must have A_1 unequal to all of A_2, A_4, A_6, \ldots, A_{2N} - in other words, all the elements at even positions initially.
Further, it’s not hard to see that A_1 isn’t special like this: the same logic applies to A_3, A_5, A_7, \ldots
Hence, every element at an even position must be different from every element at an odd position.
This condition is both necessary and sufficient for an array to be beautiful.
Next, note that we’re dealing with 1 \leq A_i \leq 3.
Suppose 1 appears only at some of the odd positions (and hence doesn’t appear at even positions at all).
Then,
- If 2 appears in the odd positions, every even position should be 3 since neither 1 nor 2 can appear there.
- Similarly, if 3 appears in odd positions, every even position should be 2 instead.
- If both 2 and 3 appear in even positions, every odd position should be 1.
More generally, we see that either all the odd positions must be the same, or all the even positions must be the same.
In other words, at least one of 1, 2, or 3 should have a frequency of exactly M - i.e, half the array’s size (which if you recall is 2M).
Further, if one of them does appear M times, it’s easy to find a valid rearrangement - put the one that occurs M times at positions 1, 3, 5, 7, \ldots, 2M-1, and the others in the even positions.
Now, let’s answer queries.
If the range [L, R] has odd length the answer is immediately No, of course.
Otherwise, let x_1, x_2, x_3 denote the frequencies of 1, 2, 3 in this range.
If any of x_1, x_2, x_3 equal \frac{R-L+1}{2}, i.e half the length of the range, the answer is Yes; otherwise it’s No.
Finding x_1, x_2, x_3 is a simple exercise in prefix sums - keep three separate ones for the frequencies of 1, 2, 3.
TIME COMPLEXITY:
\mathcal{O}(N + Q) per testcase.
CODE:
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
void solve(istringstream cin) {
int n, q;
cin >> n >> q;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
a[i]--;
}
vector pref(3, vector<int>(n + 1));
for (int i = 0; i < 3; i++) {
for (int j = 0; j < n; j++) {
pref[i][j + 1] = pref[i][j] + (a[j] == i);
}
}
while (q--) {
int l, r;
cin >> l >> r;
l--;
r--;
if ((r - l + 1) % 2 == 1) {
cout << "No" << '\n';
continue;
}
int cnt0 = pref[0][r + 1] - pref[0][l];
int cnt1 = pref[1][r + 1] - pref[1][l];
int cnt2 = pref[2][r + 1] - pref[2][l];
if (max({cnt0, cnt1, cnt2}) == (r - l + 1) / 2) {
cout << "Yes" << '\n';
} else {
cout << "No" << '\n';
}
}
}
////////////////////////////////////////
// #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;
int sq = 0;
while (tt--) {
int n = in.readInt(1, 2e5);
in.readSpace();
int q = in.readInt(1, 2e5);
in.readEoln();
sn += n;
sq += q;
auto a = in.readInts(n, 1, 3);
in.readEoln();
vector<int> l(q), r(q);
for (int i = 0; i < q; i++) {
l[i] = in.readInt(1, n);
in.readSpace();
r[i] = in.readInt(l[i], n);
in.readEoln();
}
ostringstream sout;
sout << n << ' ' << q << '\n';
for (int i = 0; i < n; i++) {
sout << a[i] << " \n"[i == n - 1];
}
for (int i = 0; i < q; i++) {
sout << l[i] << ' ' << r[i] << '\n';
}
solve(istringstream(sout.str()));
}
cerr << sn << endl;
cerr << sq << endl;
assert(sn <= 2e5);
assert(sq <= 2e5);
in.readEof();
return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
n, q = map(int, input().split())
a = list(map(int, input().split()))
pref = [ [0, 0, 0, 0] for _ in range(n+1)]
for i in range(1, n+1):
pref[i] = pref[i-1][:]
pref[i][a[i-1]] += 1
for i in range(q):
l, r = map(int, input().split())
if l%2 == r%2:
# odd length
print('No')
continue
k = r-l+1
ans = 'No'
for x in [1, 2, 3]:
if pref[r][x] - pref[l-1][x] == k//2: ans = 'Yes'
print(ans)
