Choose Nonoverlapping Festival Concerts
Autumn Tournament (2019)
Submission name: festival.cpp
Problem summary
Each performer offers two closed concert intervals. Choose exactly one interval per performer so that no two selected concerts overlap, or report impossibility. Sharing an endpoint counts as overlap.
Input
N followed by N rows ai bi ci di.
Output
No if impossible; otherwise Yes followed by N lines, each 1 or 2 for the chosen concert.
Constraints
1≤N≤100000; 0≤ai≤bi<ci≤di≤1000000000.
Worked example
Original statement sample.
Input
3 0 0 1 6 2 2 3 4 1 3 5 5
Output
Yes 1 2 2
Solution analysis
- Introduce one Boolean per performer. Its two literals mean choosing the first or second concert. If candidates p and q overlap, they cannot both be chosen: p implies not q, and q implies not p.
- Sort all 2N candidates by start time. For candidate i, all later candidates whose start≤end[i] overlap it. This is one contiguous range, found by upper_bound. Every conflict is considered once, but listing the pairs individually could be quadratic.
- Compress the range implications with a segment tree. A leaf represents its candidate’s negation. An internal auxiliary literal implies both children. Give every auxiliary literal a complementary partner: adding u→v always also adds not v→not u. A range edge from candidate i to a tree node represents both directions of all the corresponding forbidden-pair clauses.
- Run strongly connected components on the expanded graph. A variable is impossible precisely when both literals lie in the same SCC. Otherwise component order gives a satisfying assignment. Iterative DFS avoids overflowing the call stack on a long implication chain.
- In the sample, choose first,second,second. The selected intervals are[0,0],[3,4],[5,5], so no pair overlaps. Another valid assignment may also be accepted.
Why it works
The sorted range contains exactly the later conflicting candidates. Each downward compressed path and its contrapositive enforce a forbidden pair. Conversely, any valid original assignment extends to the auxiliary literals by making a downward node true exactly when all its descendant leaf literals are true. Thus compression preserves satisfiability, and the standard SCC criterion solves the resulting 2-SAT instance.
Complexity: O(N log N) time and space: O(N) literal and auxiliary vertices, O(N) tree edges, and O(N log N) range edges. SCC traversal is linear in the expanded graph.
Watch out. Closed endpoints require start≤end. Add contrapositives for auxiliary implications. Exclude the interval itself from its range. Recursive graph DFS may overflow for the full constraints.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: The sorted range contains exactly the later conflicting candidates. Each downward
// compressed path and its contrapositive enforce a forbidden pair.
#include<algorithm>
#include<iostream>
#include<utility>
#include<vector>
using namespace std;
struct Concert{
int start;
int finish;
int literal;
};
struct Implications{
vector<vector<int>>graph;
vector<vector<int>>reverse;
Implications(int variables):graph(2*variables),reverse(2*variables){
}
int newPair(){
int id=static_cast<int>(graph.size());
graph.resize(id+2);
reverse.resize(id+2);
return id;
}
void edge(int from,int to){
graph[from].push_back(to);
reverse[to].push_back(from);
}
void imply(int from,int to){
edge(from,to);
edge(to^1,from^1);
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
vector<Concert>concerts;
for(int i=0;i<n;++i){
int a;
int b;
int c;
int d;
cin>>a>>b>>c>>d;
concerts.push_back({a,b,2*i});
concerts.push_back({c,d,2*i+1});
}
sort(concerts.begin(),concerts.end(),[](const Concert&a,const Concert&b){
return a.start<b.start;
});
int total=2*n;
Implications implications(n);
vector<int>tree(4*total);
auto build=[&](auto&&self,int node,int left,int right)->void{
if(left==right){
tree[node]=concerts[left].literal^1;
return;
}
tree[node]=implications.newPair();
int middle=(left+right)/2;
self(self,node*2,left,middle);
self(self,node*2+1,middle+1,right);
implications.imply(tree[node],tree[node*2]);
implications.imply(tree[node],tree[node*2+1]);
};
build(build,1,0,total-1);
auto addRange=[&](auto&&self,int node,int left,int right,int first,int last,int literal)->void{
if(first>right||last<left){
return;
}
if(first<=left&&right<=last){
implications.imply(literal,tree[node]);
return;
}
int middle=(left+right)/2;
self(self,node*2,left,middle,first,last,literal);
self(self,node*2+1,middle+1,right,first,last,literal);
};
vector<int>starts(total);
for(int i=0;i<total;++i){
starts[i]=concerts[i].start;
}
for(int i=0;i<total;++i){
int last=
static_cast<int>(upper_bound(starts.begin(),starts.end(),concerts[i].finish)-starts.begin())-
1;
if(i+1<=last){
addRange(addRange,1,0,total-1,i+1,last,concerts[i].literal);
}
}
int vertices=static_cast<int>(implications.graph.size());
vector<bool>visited(vertices,false);
vector<int>order;
for(int root=0;root<vertices;++root){
if(visited[root]){
continue;
}
visited[root]=true;
vector<pair<int,int>>stack{{root,0}};
while(!stack.empty()){
int vertex=stack.back().first;
int&next=stack.back().second;
if(next==static_cast<int>(implications.graph[vertex].size())){
order.push_back(vertex);
stack.pop_back();
}
else{
int to=implications.graph[vertex][next++];
if(!visited[to]){
visited[to]=true;
stack.push_back({to,0});
}
}
}
}
vector<int>component(vertices,-1);
int count=0;
reverse(order.begin(),order.end());
for(int root:order){
if(component[root]!=-1){
continue;
}
vector<int>stack{root};
component[root]=count;
while(!stack.empty()){
int vertex=stack.back();
stack.pop_back();
for(int to:implications.reverse[vertex]){
if(component[to]==-1){
component[to]=count;
stack.push_back(to);
}
}
}
++count;
}
for(int i=0;i<n;++i){
if(component[2*i]==component[2*i+1]){
cout<<"No\n";
return 0;
}
}
cout<<"Yes\n";
for(int i=0;i<n;++i){
cout<<(component[2*i]>component[2*i+1]?1:2)<<'\n';
}
}