Particles on a Grid
National Olympiad — National round (2010 season)
Submission name: particles.cpp
Problem summary
Particles move on an N-column, M-row grid. Every particle takes exactly S orthogonal unit steps in each unit of time. Given initial and target multiplicities, decide whether the target is attainable after exactly T units. Particles may share cells.
Input
N M, then T S, then the initial M×N matrix and target M×N matrix. Blank lines are optional whitespace.
Output
Y if attainable, otherwise N.
Constraints
1 ≤ N,M ≤ 100; 1 ≤ T ≤ 1000000; 1 ≤ S ≤ 100; initially at most 200 particles in total and at most 200 in a cell.
Worked example
An independently prepared example for this explanation.
Input
5 3 1 2 0 0 1 0 0 0 0 0 0 1 2 0 0 0 0 2 0 0 0 0 0 1 0 0 1 0 0 0 0 0
Output
Y
Solution analysis
- Expand multiplicities into one vertex per particle on each side of a bipartite graph. Total particle counts must match. A source-target pair is compatible when its Manhattan distance d is at most L=T·S and L−d is even.
- On a rectangular grid with at least two cells, take a shortest path of d steps and insert two-step backtracks to obtain every larger length with the same parity. On a single-cell grid no positive-length walk exists, so only an empty configuration is attainable under the positive T,S bounds.
- Find a matching covering all source particles using augmenting paths. Each match independently assigns one initial particle to a target position; no collisions restrict the walks. In the sample all four source particles can be paired with target particles at compatible distances and parity.
Why it works
Every unit step flips checkerboard parity and can reduce distance by at most one, proving the distance and parity conditions necessary. A shortest path plus repeated traversals of any incident edge in both directions proves sufficiency when the grid has an edge. Thus a valid evolution gives a perfect matching, and a perfect matching gives independent valid walks for every particle. Augmenting-path matching finds a maximum matching, completing the equivalence.
Watch out. Check particle conservation before matching. Exact length requires parity, not only a distance bound. Handle the 1×1 grid separately.
Commented C++17 solution
An independently written complete program with standard headers.
#include<cstdlib>
#include<functional>
#include<iostream>
#include<utility>
#include<vector>
// Algorithm: Expand multiplicities into one vertex per particle on each side of a bipartite
// graph.
using namespace std;
int main(){
int columns,rows;
long long time,speed;
cin>>columns>>rows>>time>>speed;
vector<pair<int,int>>source,target;
for(int layer=0;layer<2;layer++){
auto&particles=layer==0?source:target;
for(int r=0;r<rows;r++){
for(int c=0;c<columns;c++){
int count;
cin>>count;
for(int i=0;i<count&&particles.size()<=200;i++){
particles.push_back({r,c});
}
}
}
}
if(source.size()!=target.size()||source.size()>200){
cout<<"N\n";
return 0;
}
if(rows*columns==1){
cout<<(source.empty()?"Y\n":"N\n");
return 0;
}
int p=static_cast<int>(source.size());
vector<vector<int>>graph(p);
long long length=time*speed;
for(int i=0;i<p;i++){
for(int j=0;j<p;j++){
int distance=abs(source[i].first-target[j].first)+abs(source[i].second-target[j].second);
if(distance<=length&&(length-distance)%2==0){
graph[i].push_back(j);
}
}
}
vector<int>matched(p,-1),seen(p,0);
int stamp=0;
function<bool(int)>augment=[&](int v){
if(seen[v]==stamp){
return false;
}
seen[v]=stamp;
for(int u:graph[v]){
if(matched[u]==-1||augment(matched[u])){
matched[u]=v;
return true;
}
}
return false;
};
for(int i=0;i<p;i++){
stamp++;
if(!augment(i)){
cout<<"N\n";
return 0;
}
}
cout<<"Y\n";
}