PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: raysh07
Editorialist: iceknight1093
DIFFICULTY:
Medium
PREREQUISITES:
Segment trees, binary search
PROBLEM:
Given an odd-length array A, Alice and Bob will do the following:
- Start with empty array B.
- Take turns, Alice going first.
- On the i-th turn, the player must insert A_i to either the front or back of B.
The score of the final array B is \min(B_1, B_N).
Alice wants to maximize the score, Bob wants to minimize it.
Define f(A) to be the final score when both players try to achieve their goals.
Compute f(A).
There are now Q point updates, compute f(A) after each one.
EXPLANATION:
Computing f(A) for a fixed array had a simple greedy algorithm that ran in \mathcal{O}(N) time.
However, it’s a bit unclear how to optimize this to support point updates.
Instead, we’ll look at a different algorithm to compute the answer.
Let’s try to check if the answer is \ge X.
This happens if and only if Alice can ensure that both endpoints of B are \ge X in the end.
First, for this to happen, certainly A_N \ge X must hold.
Next, let’s look at A_{N-1}. There are two possibilities
- A_{N-1} \ge X.
Here, because N is odd, Alice can ensure that the answer is \ge X.
The reason is that Bob will be the one to place A_{N-1}, and when he does so, it will be at one end of B.
Alice can then simply place A_N at the other end of B, and now both ends are \ge X, as desired. - A_{N-1} \lt X.
Here, let’s analyze the situation after N-2 elements have been placed (so just before Bob needs to place A_{N-1}).
There are two possibilities:- Both ends are currently \ge X.
Here, Alice can ensure that both ends remain \ge X in the end: whichever side Bob places A_{N-1} at, she can place A_N at the same side and win. - (At least) one end is \lt X.
Here, Bob can place A_{N-1} at the other end, so when Alice needs to place A_N, both ends are \lt X and she can fix at most one of them.
- Both ends are currently \ge X.
So, Alice always “wins” the first case, while in the second, it can be observed that she wins if and only if she’s able to win after the prefix of length N-2.
(Note that this gives us a simple check in linear time, which combined with binary search on X gives a solution in \mathcal{O}(N\log N) to the easy version.)
Let’s analyze the last result a bit more globally.
Consider a boolean array B, where B_i = 1 if A_i \ge X, and B_i = 0 otherwise.
Looking at B in reverse:
- B must end with [1], otherwise Alice loses.
- If B ends with [1, 1], Alice wins, otherwise the suffix is [0, 1] and we need to look at the previous elements.
- Applying the same logic to the prefix at N-2, we see that Alice loses if [0, 0, 1] is a suffix of B, wins if [1, 1, 0, 1] is a suffix of B, and otherwise the suffix is [0, 1, 0, 1] and we need to look at previous elements again.
Extending the above logic, observe that if a suffix of B is alternating between 0 and 1, we cannot decide whether Alice wins or not, and must look further.
So, what we’re really interested in is the smallest suffix that’s not alternating - or equivalently, the largest index i such that B_i = B_{i+1}.
Once this index is known, we decide whether Alice wins or not by just looking at the value of B_i - if B_i = 0 then Alice loses, otherwise she wins.
The important observation now is that, since B must be alternating after the index i we care about, we don’t even need to look for a pair of adjacent equal elements in B - we can instead just find the last element that’s “out of place”.
That is, we can find the last occurrence of 1 at an even index, and the last occurrence of 0 at an odd index, and check which comes later!
This just means we’re looking for:
- Among all even indices, the last element that’s \ge X
- Among all odd indices, the last element that’s \lt X
These can be found quickly - in \mathcal{O}(\log N) time actually - using segment trees. Store separate segment trees corresponding to even/odd indices to make things easier to work with.
Assuming we have segment trees corresponding to the even/odd indices, it’s now possible for us to find the answer as follows:
- For a fixed X, we can check if Alice “wins” X by querying the segment trees in logarithmic time.
- Binary searching on X then gives us a check in \mathcal{O}(\log^2 N) time.
It’s possible to improve this to \mathcal{O}(\log N) time, though not necessary to get AC.
Each point update to the array now only corresponds to a simple segment tree update, so we’re done!
Bonus: This problem guaranteed that N is odd. What if it wasn’t?
TIME COMPLEXITY:
\mathcal{O}(N + Q\log^2 N) or \mathcal{O}(N + Q\log N) per testcase.
CODE:
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
struct Itersegtree{
int n, def, t;
vector <int> seg;
inline int combine(int x, int y){
if (t == 0){
return min(x, y);
} else {
return max(x, y);
}
}
inline void modify(int p, int v){
p--;
for (seg[p += n] = v; p > 1; p >>= 1)
seg[p >> 1] = combine(seg[p], seg[p ^ 1]);
}
inline int query(int l, int r){
l--;
int res = def;
for (l += n, r += n; l < r; l >>= 1, r >>= 1){
if (l & 1) res = combine(res, seg[l++]);
if (r & 1) res = combine(res, seg[--r]);
}
return res;
}
Itersegtree (int _n, int _def){
n = _n;
def = _def;
seg.resize(2 * n + 1);
for (auto &x : seg){
x = def;
}
}
Itersegtree (int _n, int _def, vector <int> a, int _t){
n = _n;
t = _t;
def = _def;
seg.resize(2 * n + 1);
for (auto &x : seg){
x = def;
}
for (int i = 1; i <= n; i++){
if (a.size() == n) modify(i, a[i - 1]);
else modify(i, a[i]);
}
}
};
void Solve()
{
int n, q; cin >> n >> q;
vector <int> a(n);
for (auto &x : a) cin >> x;
auto b = a;
auto c = a;
for (int i = 0; i < n; i++){
if (i % 2 == 0){
c[i] = -INF;
} else {
b[i] = INF;
}
}
Itersegtree segmn(n, INF, b, 0);
Itersegtree segmx(n, -INF, c, 1);
auto solve = [&](){
int lo = 1, hi = n;
while (lo != hi){
int mid = (lo + hi) / 2;
int v1 = segmn.query(mid, n);
int v2 = segmx.query(mid, n);
if (v1 >= v2){
hi = mid;
} else {
lo = mid + 1;
}
}
int v1 = segmn.query(lo, n);
int v2 = segmx.query(lo, n);
if (lo % 2 == 0){
cout << v2 << " ";
} else {
cout << v1 << " ";
}
};
solve();
while (q--){
int p, x; cin >> p >> x;
p--;
a[p] = x;
if (p % 2 == 0){
segmn.modify(p + 1, x);
} else {
segmx.modify(p + 1, x);
}
solve();
}
cout << "\n";
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
Editorialist's code (C++)
// #include <bits/allocator.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());
/**
* Point-update Segment Tree
* Source: kactl
* Description: Iterative point-update segment tree, ranges are half-open i.e [L, R).
* f is any associative function.
* Time: O(logn) update/query
*/
template<class T, T unit = T()>
struct SegTree {
T f(T a, T b) { return max(a, b); }
vector<T> s; int n;
SegTree(int _n = 0, T def = unit) : s(2*_n, def), n(_n) {}
void update(int pos, T val) {
for (s[pos += n] = val; pos /= 2;)
s[pos] = f(s[pos * 2], s[pos * 2 + 1]);
}
T query(int b, int e) {
T ra = unit, rb = unit;
for (b += n, e += n; b < e; b /= 2, e /= 2) {
if (b % 2) ra = f(ra, s[b++]);
if (e % 2) rb = f(s[--e], rb);
}
return f(ra, rb);
}
};
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int t; cin >> t;
while (t--) {
int n, q; cin >> n >> q;
vector a(n, 0);
for (int &x : a) cin >> x;
vector<set<int>> pose(n+1), poso(n+1);
for (int i = 1; i <= n; ++i) {
pose[i].insert(-1);
poso[i].insert(-1);
}
SegTree<int, -1> evens(n+1), odds(n+1);
auto del = [&] (int i) {
if (i%2 == 0) {
pose[a[i]].erase(i);
evens.update(a[i], *rbegin(pose[a[i]]));
}
else {
poso[a[i]].erase(i);
odds.update(a[i], *rbegin(poso[a[i]]));
}
};
auto ins = [&] (int i) {
if (i%2 == 0) {
pose[a[i]].insert(i);
evens.update(a[i], *rbegin(pose[a[i]]));
}
else {
poso[a[i]].insert(i);
odds.update(a[i], *rbegin(poso[a[i]]));
}
};
for (int i = 0; i < n; ++i) {
ins(i);
}
auto brute = [&] () {
if (n == 1) return a[0];
int oth = a[0];
for (int i = 1; i < n; ++i) {
if (i%2 == 0) oth = max(oth, a[i-1]);
else oth = min(oth, a[i-1]);
}
return min(oth, a[n-1]);
};
auto solve = [&] () {
if (n%2 == 0 or n == 1) {
cout << brute() << ' ';
return;
}
int lo = 1, hi = a[n-1] + 1;
while (lo+1 < hi) {
int mid = (lo + hi)/2;
// >= mid possible?
// compare last element >= mid at odd index and last element < mid at even index
int x = evens.query(0, mid), y = odds.query(mid, n+1);
if (x == -1 and y == -1) lo = mid;
else if (x == -1) lo = mid;
else if (y == -1) hi = mid;
else {
if (y > x) lo = mid;
else hi = mid;
}
}
cout << lo << ' ';
};
solve();
while (q--) {
int i, x; cin >> i >> x;
--i;
del(i);
a[i] = x;
ins(i);
solve();
}
cout << '\n';
}
}