Minimum Swaps for the National Flag
National Olympiad — National round (2010 season)
Submission name: flag.cpp
Problem summary
Rearrange a string of W, G and R into all whites, then greens, then reds using as few arbitrary position swaps as possible. Output the swaps, not the sorted string.
Input
One color string.
Output
Each swap on a separate line as two 1-based positions; there is no leading operation count.
Constraints
3 ≤ N ≤ 100; all three colors occur; input is not already sorted.
Worked example
One optimal operation sequence produced by this implementation; other minimal sequences are valid.
Input
GGWRWRGWG
Output
2 5 6 9 1 8 4 8
Solution analysis
- The color counts determine the target block boundaries uniquely. For each pair of different colors a,b, collect positions that should hold a but currently hold b. These directed misplacements form a balanced three-color graph.
- First match opposite errors: swap one position wanting a and holding b with one wanting b and holding a. One swap fixes two positions, so this is the most efficient possible operation.
- After every opposite pair is removed, remaining errors form directed three-cycles. Fix each cycle in two swaps. In the sample four swaps are sufficient; different minimal position lists are equally valid, so validate the resulting string and count rather than one particular witness.
Why it works
A direct opposite swap repairs two misplaced positions at once. Remaining errors cannot be repaired two at a time: their balanced three-color graph contains only equally oriented three-cycles. Each such triple requires at least two swaps, and the construction uses exactly two. Thus direct corrections plus two swaps per remaining cycle attain the lower bound.
Watch out. Do not output a count first. Sorting by adjacent swaps need not be optimal. Repeated colors must be treated as interchangeable. Output is a nonunique witness.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<string>
#include<utility>
#include<vector>
using namespace std;
int color(char value){
if(value=='W'){
return 0;
}
return value=='G'?1:2;
}
int main(){
string text;
cin>>text;
int count[3]={};
for(char value:text){
count[color(value)]++;
}
vector<int>wrong[3][3];
for(int position=0;position<int(text.size());position++){
int wanted=position<count[0]?0:position<count[0]+count[1]?1:2;
int actual=color(text[position]);
if(actual!=wanted){
wrong[wanted][actual].push_back(position);
}
}
vector<pair<int,int>>operations;
// Opposite misplacements can be fixed simultaneously.
for(int a=0;a<3;a++){
for(int b=a+1;b<3;b++){
while(!wrong[a][b].empty()&&!wrong[b][a].empty()){
operations.push_back({wrong[a][b].back(),wrong[b][a].back()});
wrong[a][b].pop_back();
wrong[b][a].pop_back();
}
}
}
for(int b:{1,2}){
int c=3-b;
while(!wrong[0][b].empty()){
int x=wrong[0][b].back();
int y=wrong[b][c].back();
int z=wrong[c][0].back();
wrong[0][b].pop_back();
wrong[b][c].pop_back();
wrong[c][0].pop_back();
operations.push_back({x,z});
operations.push_back({y,z});
}
}
for(auto[first,second]:operations){
cout<<first+1<<' '<<second+1<<'\n';
}
}