Gather Two Colors with Minimum Adjacent Swaps
Autumn Tournament (2023)
Submission name: coloring.cpp
Problem summary
For each independent query(x,y), color all occurrences of x or y. First minimize the sum of pairwise distances between colored positions; among arrangements attaining that minimum, find the fewest adjacent swaps needed.
Input
N Q; N values; Q pairs x y.
Output
One minimum swap count per query.
Constraints
2≤N≤1000000;1≤Q≤1000000;1≤values,x,y≤N; x≠y and both occur.
Worked example
Original statement sample.
Input
5 4 1 2 3 1 4 1 2 1 3 1 4 2 4
Output
1 1 2 2
Solution analysis
- The pairwise-distance objective is smallest exactly when the colored elements occupy consecutive cells: every gap increases distances across that gap. Adjacent swaps preserve the order among identical colored tokens, so match the i-th colored position p[i] to target start+i.
- The swap count becomes Σ|p[i]−i−start|, minimized at a median of the sorted adjusted positions p[i]−i. Since p[i+1]≥p[i]+1, these adjusted positions are nondecreasing; therefore the middle colored element supplies a median.
- Store each value’s sorted positions and prefix sums. A query combines two already sorted lists without merging: binary-search a partition that takes r=(k+1)/2 elements in total and leaves every selected element≤every unselected element. This gives the r-th position and the sum of the first r positions in O(log N). The remaining sum follows from the two total sums. For positions[1,2,4], moving4 to3 costs1; positions[1,4,5] need2 swaps.
Why it works
Any optimal pairwise-distance arrangement has no uncolored gaps. Order-preserving matching minimizes adjacent swaps to a chosen consecutive target block. The standard absolute-deviation median rule minimizes its start. The two-list partition returns precisely the lower median and the required position sums, so the arithmetic formula evaluates that minimum without constructing the merged list.
Watch out. Do not minimize just the original pairwise sum without packing the colored elements. Queries do not modify the array. Use long long for sums and swap counts. The median’s rank is in the union of both occurrence lists, not either list separately.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<limits>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,q;
cin>>n>>q;
vector<vector<int>>positions(n+1);
for(int i=1;i<=n;i++){
int value;
cin>>value;
positions[value].push_back(i);
}
vector<vector<long long>>prefix(n+1);
for(int value=1;value<=n;value++){
if(positions[value].empty()){
continue;
}
prefix[value].resize(positions[value].size()+1,0);
for(int i=0;i<static_cast<int>(positions[value].size());i++){
prefix[value][i+1]=prefix[value][i]+positions[value][i];
}
}
while(q--){
int x,y;
cin>>x>>y;
if(positions[x].size()>positions[y].size()){
swap(x,y);
}
const auto&a=positions[x];
const auto&b=positions[y];
int count=static_cast<int>(a.size()+b.size());
int rank=(count+1)/2;
int low=max(0,rank-static_cast<int>(b.size()));
int high=min(rank,static_cast<int>(a.size()));
int takeA=low;
while(low<=high){
int i=(low+high)/2;
int j=rank-i;
int leftA=i==0?0:a[i-1];
int leftB=j==0?0:b[j-1];
int rightA=i==static_cast<int>(a.size())?n+1:a[i];
int rightB=j==static_cast<int>(b.size())?n+1:b[j];
if(leftA>rightB){
high=i-1;
}
else if(leftB>rightA){
low=i+1;
}
else{
takeA=i;
break;
}
}
int takeB=rank-takeA;
long long median=max(takeA==0?0:a[takeA-1],takeB==0?0:b[takeB-1]);
long long leftSum=prefix[x][takeA]+prefix[y][takeB]-median;
long long totalSum=prefix[x].back()+prefix[y].back();
long long rightSum=totalSum-leftSum-median;
long long left=rank-1;
long long right=count-rank;
// Remove distances already present inside a consecutive block.
long long answer=median*left-leftSum-left*(left+1)/2;
answer+=rightSum-median*right-right*(right+1)/2;
cout<<answer<<'\n';
}
}