Distinct Score Ranking with Little Memory
National Olympiad — National round (2024 season)
Submission name: rank.cpp
Problem summary
Find the k-th largest distinct score. If fewer than k distinct scores exist, return the lowest score. Equal scores share a rank.
Input
n k followed by n scores.
Output
The requested distinct-rank score.
Constraints
0<n<1000000; 1≤k≤1000; positive scores<100000000. Original memory limit: 2 MB.
Worked example
Input and output for the worked example discussed below.
Input
10 3 4 1 4 1 9 8 9 8 8 8
Output
4
Solution analysis
- Only the k highest distinct scores affect the answer, so storing every contestant is unnecessary. Keep an ordered set of at most k scores.
- Insert each score, ignoring duplicates automatically. Whenever size exceeds k, erase the minimum; it cannot belong to the highest k distinct scores.
- The sample’s descending distinct scores are 9,8,4,1. For k=3 the set retains {4,8,9}, whose minimum 4 is the answer. With fewer than k distinct scores, its minimum is the last available rank.
Why it works
Inductively the set holds exactly the highest min(k,D) distinct values seen. Insertion and removal of the minimum preserve this invariant. Its final minimum has the required meaning in both cases.
Watch out. Rank distinct scores, not contestants. A full score-frequency table wastes the tight memory allowance.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<set>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
int k;
cin>>n>>k;
set<int>best;
for(int i=0;i<n;i++){
int score;
cin>>score;
best.insert(score);
// Retain only scores that can affect the highest k distinct ranks.
if(int(best.size())>k){
best.erase(best.begin());
}
}
cout<<*best.begin()<<'\n';
}