The problem is from today's Educational Codeforces Round 171. After spending nearly two hours trying to solve this problem, I wasn’t able to achieve the desired results. Here’s an outline of my approach:
The task is to determine the smallest $$$k$$$ for which we can make all cells black, with at most one additional midpoint insertion. For each consecutive elements in the sequence, I computed both the floor and ceil midpoints as follows:
Each midpoint divides the original gap $$$v[i+1] - v[i]$$$ into two new segments:
Left Gap: $$$ \text{mid} - v[i] $$$
Right Gap: $$$ v[i+1] - \text{mid} $$$
I inserted each midpoint separately, recalculated the largest and second-largest gaps among all segments, then restored the original sequence. By aiming to minimize the maximum of these gaps across all midpoint attempts, I sought to find the smallest feasible $$$k$$$ that allows painting all required cells black.
Here’s my submission link smash me. If someone is having trouble accessing the link, here is my implementation:
void solve () {
int n;
cin >> n;
vector<int> v(n);
for (int i = 0; i < n; i++) {
cin >> v[i];
}
if (n == 1) {
cout << 1 << endl;
return;
} else if (n == 2) {
cout << v[1] - v[0] << endl;
return;
}
multiset<int> res;
for (int i = 1; i < n; i++) {
res.insert(v[i] - v[i - 1]);
}
int mn = 0;
for (int i = 0; i < n - 1; i++) {
int x = v[i + 1] - v[i];
int mid = (v[i] + v[i + 1]) / 2;
res.erase(res.find(x));
res.insert(mid - v[i]);
res.insert(v[i + 1] - mid);
auto it = res.rbegin();
int gp = *it;
it++;
int sc = (it != res.rend()) ? *it : gp;
mn = max(mn, sc);
res.erase(res.find(mid - v[i]));
res.erase(res.find(v[i + 1] - mid));
res.insert(x);
}
for (int i = 0; i < n - 1; i++) {
int x = v[i + 1] - v[i];
int mid = (v[i] + v[i + 1] + 1) / 2;
res.erase(res.find(x));
res.insert(mid - v[i]);
res.insert(v[i + 1] - mid);
auto it = res.rbegin();
int gp = *it;
it++;
int sc = (it != res.rend()) ? *it : gp;
mn = max(mn, sc);
res.erase(res.find(mid - v[i]));
res.erase(res.find(v[i + 1] - mid));
res.insert(x);
}
cout << mn << endl;
}
I can't find any exceptional cases. Can someone help me? Thanks in advance for your assistance.
i too thought of this approach of just outputing the largest gap for even value of n and outputing the second largest gap for n odd i know it fails somewhere but can't figure out where
as for n even to reduce gap we might need 2 elements extra (not possible acc to prob) for n odd we can take the largest gap and minimize it and then print the second largest gap directly like 1 7 10 11 15 largest gap is 6 and then 4 so for reducing 6 gap we consider adding 2 which makes the gap of 11 15 as largest which is 4 but it fails somewhere