Ranked Song Ballots
National Olympiad — National round
Submission name: comp.cpp
Problem summary
Each of N ballots lists up to three song codes in preference order; empty ballots are ignored. Count current first preferences. A song with strictly more than half of nonempty ballots wins. Otherwise eliminate all songs tied for the smallest positive first-preference count, deleting them everywhere and promoting later preferences. Repeat. If all current first-preference counts are equal, report those tied songs for a runoff. For a winner, report the number of ballots that originally ranked it first.
Input
N followed by N ballot lines. Codes have the form S followed by the song number; codes may be adjacent without spaces.
Output
Winner code and its original first-choice count, or runoff codes in increasing numeric order.
Constraints
1 ≤ N ≤ 100000; at most 52 songs. Each ballot contains at most three codes.
Worked example
An independently prepared example for this explanation.
Input
3 S2S1 S2 S1
Output
S2 2
Solution analysis
- Parse song numbers rather than whitespace-separated tokens; preserve original first-choice counts.
- Maintain a set of eliminated songs. In every round find the first noneliminated song on each ballot and count its votes.
- Test strict majority, then an all-equal tie, then simultaneously eliminate the positive-count minimum. Songs with zero current first preferences are not eliminated merely for having zero votes.
Why it works
Deleting an eliminated song from all positions is equivalent to skipping it while scanning ballots. The resulting counts are exactly the next round specified by the rules. At least one new song is eliminated in every nonterminal round.
Watch out. Winner support is the original first-choice count, not the final transferred vote count. Do not split adjacent codes incorrectly.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Deleting an eliminated song from all positions is equivalent to skipping it while scanning
// ballots. The resulting counts are exactly the next round specified by the rules.
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<set>
#include<map>
#include<cmath>
#include<climits>
#include<cctype>
#include<iterator>
using namespace std;
int main(){
int n;
cin>>n;
string line;
getline(cin,line);
vector<vector<int>>ballots(n);
map<int,int>original;
for(auto&b:ballots){
getline(cin,line);
for(size_t i=0;i<line.size();i++){
if(line[i]=='S'){
int x=0;
i++;
while(i<line.size()&&isdigit((unsigned char)line[i])){
x=10*x+line[i++]-'0';
}
i--;
b.push_back(x);
}
}
if(!b.empty()){
original[b[0]]++;
}
}
set<int>removed;
while(true){
map<int,int>count;
int total=0;
for(auto&b:ballots){
for(int x:b){
if(!removed.count(x)){
count[x]++;
total++;
break;
}
}
}
if(count.empty()){
cout<<'\n';
break;
}
int mn=INT_MAX,mx=0,winner=0;
for(auto[x,c]:count){
mn=min(mn,c);
if(c>mx){
mx=c;
winner=x;
}
}
if(2*mx>total){
cout<<'S'<<winner<<' '<<original[winner]<<'\n';
break;
}
if(mn==mx){
for(auto[x,c]:count){
cout<<'S'<<x<<' ';
}
cout<<'\n';
break;
}
for(auto[x,c]:count){
if(c==mn){
removed.insert(x);
}
}
}
}