Recover the K Largest Positions by Comparisons
Autumn Tournament (2020)
Submission name: biggest.cpp
Problem summary
A hidden permutation is available only through compare(x,y), which returns the index holding the larger value. Return the positions of its K largest values, in descending-value order. The first N−1 comparisons are free in the score; further comparisons affect the score.
Source clarification. This is an oracle/grader task with score dependent on comparison count, not an ordinary stdin problem. The local demonstration is explicitly a simulator. No100%-score claim is made for the tournament strategy.
Input
Original interface: vector<int> biggest(int N,int K), with grader compare(x,y). Local demonstration reads N K and the hidden permutation for its simulated grader.
Output
K indices, from the position holding N down to the position holding N−K+1.
Constraints
Original tests have N=100000 and1≤K≤N; more than3000000 compare calls gives zero points. The illustrative communication uses N=4.
Worked example
Original statement sample.
Input
4 2 4 1 3 2
Output
1 3
Solution analysis
- Build a knockout tournament. Its leaves are the permutation positions, and every internal node stores the winner of comparing its two child winners. Padding leaves are marked absent and require no comparisons. The initial tournament uses exactly N−1 real comparisons and reveals the largest position.
- Output the root winner, remove that leaf, and recompute only the ancestors of the removed leaf. The new root is the largest remaining position. Repeat K times. The grader still hides all values: the algorithm uses only compare and never reads the simulated permutation directly.
- For hidden values[4,1,3,2], the initial winner is position1. Removing that leaf allows position3 to become the next winner, so the returned vector is[1,3]. A balanced tree limits every repair to⌈log2N⌉ comparisons; even K=N stays below the3million hard cap for N=100000.
Why it works
Every tournament node stores the maximum among its active leaves. The invariant holds after the bottom-up build and after recomputing the path of a removed leaf. Thus each root winner is the next maximum among remaining positions, and the returned indices have precisely the required descending order.
Watch out. compare returns a winning index, not a Boolean. Original submissions must contain biggest and include biggest.h, with no main. The LOCAL simulator reads the hidden array only to implement the grader oracle; that array must never be accessed by the submitted solution.
Commented C++17 solution
Compile the runnable local demonstration with g++ -std=c++17 -DLOCAL. For the original grader, omit -DLOCAL and provide its biggest.h; the function then uses the real compare oracle. This strategy guarantees correctness within the hard limit, not an optimal relative score.
#include<iostream>
#include<vector>
#ifndef LOCAL
#include"biggest.h"
#else
int compare(int x,int y);
#endif
using namespace std;
vector<int>biggest(int n,int k){
int leaves=1;
while(leaves<n){
leaves*=2;
}
vector<int>winner(2*leaves,0);
for(int i=0;i<n;i++){
winner[leaves+i]=i+1;
}
auto choose=[](int a,int b){
if(a==0){
return b;
}
if(b==0){
return a;
}
return compare(a,b);
};
for(int node=leaves-1;node>0;node--){
winner[node]=choose(winner[node*2],winner[node*2+1]);
}
vector<int>result;
for(int taken=0;taken<k;taken++){
int position=winner[1];
result.push_back(position);
if(taken+1==k){
break;
}
int node=leaves+position-1;
winner[node]=0;
// Only this leaf-to-root path has changed.
for(node/=2;node>0;node/=2){
winner[node]=choose(winner[node*2],winner[node*2+1]);
}
}
return result;
}
#ifdef LOCAL
vector<int>hidden;
int compare(int x,int y){
return hidden[x]>hidden[y]?x:y;
}
int main(){
int n,k;
cin>>n>>k;
hidden.resize(n+1);
for(int i=1;i<=n;i++){
cin>>hidden[i];
}
vector<int>answer=biggest(n,k);
for(int i=0;i<k;i++){
if(i>0){
cout<<' ';
}
cout<<answer[i];
}
cout<<'\n';
}
#endif