PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: righter
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
Sets, binary search
PROBLEM:
N introverts will attempt to sit in N positions, in order from 1 to N. Each person will behave as follows:
- Choose a seat that’s as far away from every seated person as possible.
- If there are multiple seats satisfying the above, choose a seat that maximizes the distance for the next person.
- If there are still multiple seats, take any of them.
You are given a permutation P. Is it possible that the introverts sat in this configuration?
EXPLANATION:
One way to look at this task is in terms of intervals.
We initially have the interval [1, N].
Each time a person sits, they will break one interval into two (or less, if they sit at an end).
In particular, the set of empty positions can be maintained as a disjoint set of intervals.
Given the behavior of the introverts, if a person chooses to sit in the interval [L, R], he will sit exactly at its midpoint if its length is odd; and at one of the two midpoints if the length is even (for example if the interval is [5, 10] either 7 or 8 can be chosen).
This is because the midpoint maximizes the distance to the closest person.
The only exceptions to this rule are the first two people: 1 will always sit at one end (i.e. either at 1 or N), and 2 will always sit at the other end.
Let’s take care of these two separately so that no further casework is required.
Now, suppose we have a set of intervals (representing the empty positions) with us after the first i-1 people have been seated, and we’re trying to seat person i.
Following the rules, the i-th person will first try to choose an interval whose midpoint is as far away as possible from its closest end.
In general this will correspond to the longest interval:
- For an interval of length 2k, either midpoint is at a distance of k from the closer border.
- For an interval of length 2k+1, the singular midpoint is at a distance of k+1 from both borders.
If there are multiple intervals that attain this maximum distance, we need to decide how to break ties.
However, nicely enough, we don’t actually need to care about this!
That is, if there are several intervals that attain the maximum distance from midpoint to border, they will all be valid choices, no matter what.
To see why:
- If there’s only one interval that attains maximum distance, clearly it’s the only choice and so no tiebreaking rule is needed.
- If there are multiple such intervals, because they’re disjoint it doesn’t matter which one is chosen: the maximum distance for the next person won’t reduce.
So, all we need to do is simulate the interval-breaking process quickly enough; while checking if each move made is valid.
One way of doing this is to store the intervals in a sorted set (std::set in C++ for example).
The intervals can be sorted by their length.
When processing person i,
- First, find which interval they’re breaking.
To do this quickly, you can for example maintain the set of occupied positions; and then find the nearest occupied position to the left and right of whichever position contains person i.
This can be done using a set and binary search (set.lower_boundin C++) - Once the interval [L, R] is known, two checks must be performed:
- Check if i is sitting at a midpoint of this interval.
- Check if this interval has the maximum distance to its borders among all existing intervals - this can be done by comparing its value to the value of the longest existing interval.
- If both checks pass, there are no issues with person i, so seat them and break the interval [L, R] into two parts appropriately.
If all N people can be seated this way, we’re done; otherwise we’ll encounter a problem midway and stop.
Every check and insert/delete operation is on a set, and so takes \mathcal{O}(\log N) time; leading to an overall complexity of \mathcal{O}(N\log N).
TIME COMPLEXITY:
\mathcal{O}(N\log N) per testcase.
CODE:
Author's code (C++)
// Setter's code
#include <bits/stdc++.h>
#define int long long int
#define f first
#define s second
#define INF LONG_LONG_MAX
#ifndef ONLINE_JUDGE
auto x = freopen("input30.txt", "r", stdin);
auto y = freopen("output.txt", "w", stdout);
#endif
using namespace std;
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1, n;
cin >> t;
for (int tc = 0; tc < t; tc++){
cin >> n;
int arr[n], ind[n + 1];
for (int i = 0; i < n; i++){
cin >> arr[i];
ind[arr[i]] = i;
}
if (n <= 2){
cout << "YES" << endl;
continue;
}
if (not ((arr[0] == 1 and arr[n - 1] == 2) or (arr[0] == 2 and arr[n - 1] == 1))){
cout << "NO" << endl;
continue;
}
bool poss = true;
map<int,set<pair<int,int>>> segments;
segments[(n - 2) - (1)].insert({1, n - 2});
for (int i = 3; i <= n; i++){
auto &p = *segments.rbegin();
set<pair<int,int>> &s1 = p.s;
bool ans = false;
pair<int,int> seg;
if (not ans) {
auto it = s1.upper_bound({ind[i], INF});
if (it != s1.begin()) {
it--;
if (ind[i] <= it->s){
if (ind[i] == (it->f + it->s) / 2 or ind[i] == (it->f + it->s + 1) / 2){
ans = true;
seg = *it;
}
}
}
}
if (not ans) {
if (p.f % 2 == 1 and segments.find(p.f - 1) != segments.end()) {
set<pair<int, int>> &s2 = segments[p.f - 1];
auto it = s2.upper_bound({ind[i], INF});
if (it != s2.begin()) {
it--;
if (ind[i] <= it->s) {
if (ind[i] == (it->f + it->s) / 2 or ind[i] == (it->f + it->s + 1) / 2) {
ans = true;
seg = *it;
}
}
}
}
}
if (not ans){
poss = false;
break;
}
segments[seg.s - seg.f].erase(seg);
if (segments[seg.s - seg.f].empty()){
segments.erase(seg.s - seg.f);
}
pair<int,int> seg1 = {seg.f, ind[i] - 1}, seg2 = {ind[i] + 1, seg.s};
if (seg1.s - seg1.f >= 0){
segments[seg1.s - seg1.f].insert(seg1);
}
if (seg2.s - seg2.f >= 0){
segments[seg2.s - seg2.f].insert(seg2);
}
}
if (poss){
cout << "YES" << endl;
}
else {
cout << "NO" << endl;
}
}
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t;
cin >> t;
while(t--) {
int n;
cin >> n;
vector<int> p(n), pos(n);
for(auto &x: p) cin >> x;
if(n == 1) {
cout << "YES\n";
continue;
}
for(int i = 0; i < n; i++) pos[p[i] - 1] = i;
if(!(p[0] == 1 && p[n - 1] == 2) && !(p[0] == 2 && p[n - 1] == 1)) {
cout << "NO\n";
continue;
}
set<int> s;
map<int, int> have;
s.insert(pos[0]);
s.insert(pos[1]);
have[n] = 1;
for(int i = 2; i < n; i++) {
auto itl = s.lower_bound(pos[i]);
itl = prev(itl);
auto itr = s.upper_bound(pos[i]);
int dl = pos[i] - *itl;
int dr = *itr - pos[i];
if(abs(dl - dr) > 1) {
cout << "NO\n";
goto end;
}
auto htr = have.rbegin();
auto htl = next(htr);
if(htr->fr - htl->fr > 1 || have.size() == 1 || (htr->fr) % 2 == 1) {
if(htr->fr != dl + dr + 1) {
cout << "NO\n";
goto end;
}
}
else {
if(htr->fr != dl + dr + 1 && htl->fr != dl + dr + 1) {
cout << "NO\n";
goto end;
}
}
if(have[dl + dr + 1] == 1) have.erase(dl + dr + 1);
else have[dl + dr + 1]--;
have[dl + 1]++;
have[dr + 1]++;
s.insert(pos[i]);
}
cout << "YES\n";
end:;
}
return 0;
}