PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author & Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Binary search
PROBLEM:
There is a line segment of length M.
N operations are performed on it - in the i-th operation, point A_i is marked.
After each operation, find the length of the longest segment without any marked points.
EXPLANATION:
This problem was intended to be somewhat of an introduction to C++ STL (or whatever your language’s library is) for newer participants; though it is still possible to solve without libraries, if you’d like to do so.
The core idea behind solving the problem is that the empty segments can be directly maintained, because each time we mark a new point, one empty segment breaks into two smaller ones; for a net addition of one segment.
After each such break, notice that the (multi)set of lengths of the empty segments doesn’t change much either - in particular, one length disappears and two lengths appear.
So, solving the problem requires us to be able to support the following quickly:
- Find which empty segment needs to be split into two
- Find out which length disappears, and which ones appear
- Find out the maximum among the remaining lengths
In particular, we need a data structure that supports quick insertion/deletion/getting the maximum, which is what a set does.
This leads to several different ways to implement the problem, some simpler than others.
Below are a couple of them.
Approach 1
The problem can be solved “directly”, by breaking the segments as mentioned earlier.
To do this, let’s maintain a set S of existing posts (initially contains 0 and M), and another set L of the lengths of empty segments (initially contains only M).
Then, for each i from 1 to N:
- First, we need to find which empty segment contains A_i.
To do this, we use binary search.
Let x be the largest element of S that’s \lt A_i, and y be the smallest element of S that’s \gt A_i. Both x and y can be found by binary searching on S (for example, via thelower_boundandupper_boundfunctions in C++) - Now, we know A_i lies in the segment [x, y], and placing a pole there will break it into segments [x, A_i] and [A_i, y].
- So, we can delete the length (y-x) from L, and insert the lengths (A_i - x) and (y - A_i) instead.
- Finally, the maximum element of L is the current answer.
Each of these operations can be done in \mathcal{O}(\log N) using a sorted set (std::set in C++, TreeSet in Java).
Note that L can contain duplicate elements because lengths may occur more than once; so you should use a datastructure that allows for duplicates such as std::multiset.
Approach 2 (slightly longer but simpler and faster)
Another way to implement this is to look at the process in reverse.
Instead of adding in posts, let’s start with all of them already there, and remove posts instead.
Notice that going this way, the maximum empty length can only increase: in particular, when we remove a pole, the newly created larger segment is the only potential new maximum.
This allows for a simpler implementation, as follows:
- Let S be a set containing all the remaining poles.
Initially, it contains all the A_i, along with 0 and M.
Also keep a variable \text{ans}, denoting the answer. Initialize it to the maximum adjacent difference between elements of S. - Then, for each i from N to 1, do the following:
- Locate A_i in S using a binary search. Also find the nearest remaining poles to its left and right; say x and y.
When A_i is removed, the new empty segment created has length y-x. - Set \text{ans} = \max(\text{ans}, y-x), and delete A_i from S.
- Locate A_i in S using a binary search. Also find the nearest remaining poles to its left and right; say x and y.
This way, we easily find all the answers in reverse.
This implementation is much simpler to reason about, and has a lower chance of implementation errors creeping in because you need one less data structure. It also runs a bit faster than the first approach.
The tradeoff is that it’s a bit longer to code than approach 1.
Some languages, such as Python, unfortunately don’t have a builtin data structure that supports the required operations, so you’ll have to code one yourself - for example the SortedList found here.
TIME COMPLEXITY
\mathcal{O}(N\log N) per testcase.
CODE:
Author's code (C++, approach 1)
// #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());
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int t; cin >> t;
while (t--) {
int n, m; cin >> n >> m;
set<int> posts = {0, m};
multiset<int> lengths = {m};
for (int i = 0; i < n; ++i) {
int x; cin >> x;
auto it = posts.lower_bound(x);
int L = *prev(it), R = *it;
lengths.erase(lengths.find(R-L));
lengths.insert(x-L);
lengths.insert(R-x);
posts.insert(x);
cout << *lengths.rbegin() << ' ';
}
cout << '\n';
}
}
Author's code (C++, approach 2)
// #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());
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int t; cin >> t;
while (t--) {
int n, m; cin >> n >> m;
vector<int> a(n), ans(n);
for (int &x : a) cin >> x;
set<int> s(begin(a), end(a));
s.insert(0); s.insert(m);
int mxdif = 0;
for (auto it = begin(s); it != end(s); ++it) {
if (next(it) == end(s)) break;
mxdif = max(mxdif, *next(it) - *it);
}
for (int i = n-1; i >= 0; --i) {
ans[i] = mxdif;
auto it = s.find(a[i]);
int L = *prev(it), R = *next(it);
mxdif = max(mxdif, R-L);
s.erase(a[i]);
}
for (int x : ans) cout << x << ' ';
cout << '\n';
}
}