PROBLEM LINK:
Practice
Div-2 Contest
Div-1 Contest
Author: Ildar Gainullin
Tester: Nikolay Budin
Editorialist: Alei Reyes
DIFFICULTY:
Medium
PREREQUISITES:
Binary search, range query data structures.
PROBLEM:
There are n sweets on a circular table. When you eat sweet i, the level of your happiness is changing by a_i.
You start by eating candy 1. While there is at least one uneaten sweet, you can eat any sweet that is adjacent to at least one of the previously eaten sweets.
Maximize the minimum smallest value of your happiness during this process.
Quick Explanation
BInary search the minimum happiness, to check if is possible to achieve a minimum level of happiness, find for each i the maximum suffix of candies that we can eat if we are obligated to eat the first i candies.
Explanation
The first candy is always eaten, so let’s remove it from the circle, and at the end just add a_1.
After removing a point from a circle it becomes a line! now in each step we have to decide to eat (remove) either the leftmost or the rightmost element in the line.
Let’s binary search the minimum happiness H that we should have at any moment of the process. The problem is reduced to determine if is possible to perform the process and at any moment have a happiness of at least H.
For each prefix of length i, let s_i be the maximum length of the suffix that is possible to eat if we are asked to take (eat) from the left at most i candies (and always keeping a happiness greater or equal than H).
Let L_i denote the sum of happiness of the first i candies, and R_i the sum of happiness of the last i candies.
We can use the value of s_{i-1} to calculate s_i:
- If a_i is positive, then s_i \geq s_{i-1}, our happiness increases, and maybe we can take more candies from the right. So we have to find the maximum j \geq s_{i-1} such that L_i + R_j \geq H. Such j can be found in logarithmic time with a segment tree.
- If a_i is negative, s_i \leq s_{i-1} because to keep our happiness level we have to remove a negative sum by decreasing the length of the suffix, it can be calculated similarly with binary search and a range query data structure.
SOLUTIONS:
Setter's Solution
Tester's Solution
void solve() {
int n;
cin >> n;
vector<int> arr;
for (int i = 0; i < n; ++i) {
int num;
cin >> num;
arr.push_back(num);
}
vector<ll> pref = {0}, suff = {0};
for (int i = 0; i < n - 1; ++i) {
pref.push_back(pref.back() + arr[1 + i]);
suff.push_back(suff.back() + arr[n - 1 - i]);
}
int bpv = 1;
while (bpv < szof(suff)) {
bpv *= 2;
}
vector<ll> segtree(bpv * 2);
for (int i = 0; i < szof(suff); ++i) {
segtree[bpv + i] = suff[i];
}
for (int i = bpv - 1; i; --i) {
segtree[i] = min(segtree[i * 2], segtree[i * 2 + 1]);
}
function<int(int, int, int, int, ll)> segtree_find = [&](int v, int vl, int vr, int pos, ll val) {
if (vr <= pos || segtree[v] >= val) {
return vr;
}
if (vr - vl == 1) {
return vl;
}
int vm = (vl + vr) / 2;
int tmp = segtree_find(v * 2, vl, vm, pos, val);
if (tmp < vm) {
return tmp;
}
return segtree_find(v * 2 + 1, vm, vr, pos, val);
};
auto find_next = [&](int row, int pos, ll val) {
val -= pref[row];
return segtree_find(1, 0, bpv, pos, val);
};
vector<vector<ll>> sparse = {suff};
int bp = 1;
while (1 << bp <= szof(suff)) {
++bp;
}
for (int i = 1; i < bp; ++i) {
sparse.push_back({});
for (int j = 0; j + (1 << i) <= szof(suff); ++j) {
sparse.back().push_back(max(sparse[i - 1][j], sparse[i - 1][j + (1 << (i - 1))]));
}
}
vector<int> maxp(szof(suff) + 1);
for (int i = 2; i < szof(maxp); ++i) {
maxp[i] = maxp[i / 2] + 1;
}
auto get_max_suff = [&](int l, int r) {
int p = maxp[r - l];
return max(sparse[p][l], sparse[p][r - (1 << p)]);
};
ll l = -2e5 * 1e9 * 2, r = 1;
while (r - l > 1) {
ll mid = (l + r) / 2;
bool ok = false;
int pos = 0;
for (int i = 0; i < n; ++i) {
int npos = find_next(i, pos, mid);
if (pos == npos) {
int l2 = -1, r2 = pos;
while (r2 - l2 > 1) {
int mid2 = (l2 + r2) / 2;
if (get_max_suff(mid2, pos + 1) + pref[i] < mid) {
r2 = mid2;
} else {
l2 = mid2;
}
}
npos = r2;
// while (npos > 0 && pref[i] + suff[npos - 1] < mid) {
// --npos;
// }
}
pos = npos;
if (pos == 0) {
break;
}
if (pos > n - 1 - i) {
ok = true;
break;
}
}
if (!ok) {
r = mid;
} else {
l = mid;
}
}
cout << l + arr[0] << "\n";
}