Creating a Half-or-More Majority
National Olympiad — National round (2021 season)
Submission name: major.cpp
Problem summary
Two arrays have equal length. You may swap a[i] with b[i] at selected positions. Find the minimum swaps making some value occur in at least half of the first array, or report impossibility.
Input
A question count, then for each question n and the two arrays.
Output
One minimum swap count per question, or −1.
Constraints
At most 10 questions; 1 < n < 200000; values are positive and <40000.
Worked example
Input and output for the worked example discussed below.
Input
3 6 3 2 1 4 9 10 5 5 3 5 3 1 4 1 2 3 4 5 6 7 8 5 1 1 1 1 1 2 2 2 2 2
Output
2 -1 0
Solution analysis
- The required frequency is ceil(n/2), since the problem says half or more rather than strictly more than half. Count how often each value already occurs in a.
- A position can add one occurrence of value v only when b[i]=v and a[i]≠v. Count those available gains separately. If existing[v]+gain[v] reaches the threshold, exactly max(0,threshold−existing[v]) swaps suffice for v.
- In the first sample the threshold is 3. Value 3 already occurs once and can be imported at positions 3 and 5. Two swaps therefore create frequency 3. Examine all values and keep the smallest feasible cost.
Why it works
For a fixed target value, each useful swap raises its first-array frequency by exactly one, and no swap raises it by more. Hence the stated deficit is a lower bound and is achieved whenever enough useful positions exist. Taking the minimum over all possible target values gives the global optimum.
Watch out. Do not demand a strict majority. Swapping equal values creates no gain. A value absent from a can still become the answer through b.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int questions;
cin>>questions;
while(questions--){
int n;
cin>>n;
vector<int>a(n);
vector<int>existing(40000,0);
vector<int>gain(40000,0);
for(int&value:a){
cin>>value;
existing[value]++;
}
for(int i=0;i<n;i++){
int value;
cin>>value;
if(value!=a[i]){
gain[value]++;
}
}
int needed=(n+1)/2;
int answer=n+1;
for(int value=1;value<40000;value++){
// Only imports at unequal positions can increase the target count.
if(existing[value]+gain[value]>=needed){
answer=min(answer,max(0,needed-existing[value]));
}
}
cout<<(answer==n+1?-1:answer)<<'\n';
}
}