Restore Reflection Orbits
National Olympiad — National round (2019 season)
Submission name: sim.cpp
Problem summary
Grid marks originally occupied complete reflection orbits across both midlines. Some were erased, with each original orbit still represented. Count all restored marks.
Input
M N K, then K surviving 1-based cells.
Output
The restored mark count.
Constraints
2 ≤ M,N ≤ 100000; 1 ≤ K ≤ 100000.
Worked example
Input and output for the worked example discussed below.
Input
5 6 6 2 5 4 2 1 3 3 1 5 6 5 1
Output
14
Solution analysis
- Reflecting (r,c) gives (M+1−r,c),(r,N+1−c), and their combination. All these cells belong to one orbit.
- An orbit’s canonical key is (min(r,M+1−r),min(c,N+1−c)). Store keys in a set to deduplicate observations of the same orbit.
- Normally the orbit size is four, but a central row or column has only one reflected choice in its dimension. The sample’s sizes 4,4,2,4 total 14.
Why it works
Reflection closure partitions cells into disjoint canonical orbits, and the stated recovery guarantee identifies exactly which orbits existed.
Complexity: O(K log K) time and O(K) space.
Watch out. Deduplicate orbits rather than just input cells. Odd dimensions can produce two-cell or one-cell orbits.
Commented C++17 solution
An independently written complete program with standard headers.
// Reflection closure partitions cells into disjoint canonical orbits, and the stated recovery guarantee
// identifies exactly which orbits existed.
#include<algorithm>
#include<iostream>
#include<set>
#include<utility>
using namespace std;
int main(){
int rows,columns,count;
cin>>rows>>columns>>count;
set<pair<int,int>>orbits;
while(count--){
int row,column;
cin>>row>>column;
orbits.insert({min(row,rows+1-row),min(column,columns+1-column)});
}
long long answer=0;
for(auto[row,column]:orbits){
int a=row==rows+1-row?1:2;
int b=column==columns+1-column?1:2;
answer+=a*b;
}
cout<<answer<<'\n';
}