Perfect Conversations
National Olympiad — National round (2010 season)
Submission name: pranka.cpp
Problem summary
Seats form an N×M grid; . is a student and # a broken seat. A student may converse with exactly one orthogonally adjacent student. For how many row prefixes 1..K can every student be paired, and which K are they? An empty prefix configuration is perfectly pairable.
Input
N M followed by N strings of M characters.
Output
If none qualify, print 0. Otherwise print the count and then the qualifying K in increasing order.
Constraints
1 ≤ N ≤ 1000; 1 ≤ M ≤ 20.
Worked example
An independently prepared example for this explanation.
Input
9 4 .... .##. .#.. ##.# #.## .... ...# .##. ....
Output
5 1 2 4 7 9
Solution analysis
- Color seats by (row+column) modulo 2. Every conversation joins opposite colors, so a perfect pairing is a perfect matching in this bipartite grid graph. Process seats row by row, inserting one student vertex at a time and adding its edges to the already inserted upper and left neighbors.
- Maintain a maximum matching after every insertion. A newly added unmatched vertex is the only possible endpoint introduced to an augmenting path; search from it through alternating unmatched and matched edges, regardless of which color it has. If a free opposite-color endpoint is reached, flip the path.
- After completing each row, compare twice the matching size with the number of inserted students. Equality means the prefix is perfect. For the official grid the qualifying final rows are 1,2,4,7,9. Iterative BFS avoids deep recursive augmenting paths.
Why it works
Before an insertion the matching is maximum, so no augmenting path exists. Any new augmenting path must involve the new vertex. Because that vertex is initially unmatched, such a path has it as an endpoint; searching from it is therefore sufficient. A single vertex insertion raises maximum matching size by at most one. Flipping one path, or finding none, restores maximal cardinality. A matching covers every student exactly when its size is half the student count.
Watch out. A new vertex can have either checkerboard color, so the augmenting search must support both. Broken seats do not connect students across gaps. Check prefixes only after the entire row is inserted.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<queue>
#include<string>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m;
cin>>n>>m;
vector<string>room(n);
for(string&row:room){
cin>>row;
}
int vertices=n*m;
vector<vector<int>>graph(vertices);
vector<int>match(vertices,-1),seen(vertices,0),parent(vertices,-1);
int stamp=0;
int students=0;
int pairs=0;
vector<int>perfect;
for(int r=0;r<n;r++){
for(int c=0;c<m;c++){
if(room[r][c]=='#'){
continue;
}
int root=r*m+c;
students++;
if(r>0&&room[r-1][c]=='.'){
int other=root-m;
graph[root].push_back(other);
graph[other].push_back(root);
}
if(c>0&&room[r][c-1]=='.'){
int other=root-1;
graph[root].push_back(other);
graph[other].push_back(root);
}
stamp++;
queue<int>pending;
pending.push(root);
seen[root]=stamp;
int endpoint=-1;
while(!pending.empty()&&endpoint==-1){
int v=pending.front();
pending.pop();
for(int u:graph[v]){
if(seen[u]==stamp){
continue;
}
seen[u]=stamp;
parent[u]=v;
if(match[u]==-1){
endpoint=u;
break;
}
int next=match[u];
if(seen[next]!=stamp){
seen[next]=stamp;
pending.push(next);
}
}
}
if(endpoint!=-1){
pairs++;
// Flip every alternating edge back to the new root.
while(endpoint!=-1){
int v=parent[endpoint];
int old=match[v];
match[v]=endpoint;
match[endpoint]=v;
endpoint=old;
}
}
}
if(2*pairs==students){
perfect.push_back(r+1);
}
}
cout<<perfect.size()<<'\n';
if(!perfect.empty()){
for(size_t i=0;i<perfect.size();i++){
if(i!=0){
cout<<' ';
}
cout<<perfect[i];
}
cout<<'\n';
}
}