Minimum Hacks to Win Outright
Autumn Tournament (2021)
Submission name: hacks.cpp
Problem summary
A scoreboard gives each contestant’s provisional points on N tasks. Ivaylo can hack a rival’s positive-scoring solution only on a task he himself solved. Each hack removes that rival’s task points and awards Ivaylo 100 points. His own solutions stay correct. Find the fewest hacks needed to finish strictly ahead of every rival, or−1 if impossible.
Input
N M K, where K is Ivaylo’s 1-based row, then M rows of N nonnegative task scores. A 0 means no accepted provisional solution.
Output
The minimum number of hacks, or−1.
Constraints
1 ≤ N ≤50; 1 ≤ M ≤10000; 1 ≤ K ≤ M; 0 ≤ scores ≤10000000.
Worked example
Original statement sample.
Input
5 3 3 500 500 0 0 500 300 0 0 0 0 480 500 0 0 490
Output
1
Solution analysis
- For each rival, collect the scores of hackable solutions and sort them decreasingly. Their prefix sums tell us the greatest score reduction attainable with any chosen number of hacks on that rival. Hacks against 0 entries are not available.
- Suppose exactly h hacks will be made. Ivaylo’s final score is fixed at ownScore+100 h. For every rival whose total is at least that score, remove at least rivalTotal−finalScore+1 points. Binary-search that rival’s prefix sums for the minimum required number of hacks. If a rival cannot be reduced enough, h is impossible.
- Add these mandatory hack counts. If their sum is at most h and h does not exceed the total number of available solutions, the remaining hacks can target any unused hackable solutions: they only help. This predicate is monotone, so binary-search h. In the sample, Ivaylo starts with 1470. Hacking the second contestant’s 300-point solution gives him 1570, already above the first contestant’s 1500; one hack is enough.
Why it works
For a fixed rival and hack count, taking its largest hackable scores maximizes the reduction, so its prefix search gives the least necessary count. Rivals have disjoint solutions, making the mandatory counts additive. Extra available hacks cannot harm any inequality. Increasing h raises Ivaylo’s target score and never increases a rival’s mandatory count, so binary search is valid.
Watch out. Winning must be strict: a tie is not enough. Only tasks solved by Ivaylo are hackable, and a rival must actually have positive points on that task. Distinguish points removed from a rival from the fixed 100-point reward.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: For a fixed rival and hack count, taking its largest hackable scores maximizes the
// reduction, so its prefix search gives the least necessary count. Rivals have disjoint solutions,
// making the mandatory counts additive.
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tasks;
int contestants;
int ownRow;
cin>>tasks>>contestants>>ownRow;
ownRow--;
vector<vector<int>>scores(contestants,vector<int>(tasks));
vector<long long>totals(contestants,0);
for(int i=0;i<contestants;i++){
for(int j=0;j<tasks;j++){
cin>>scores[i][j];
totals[i]+=scores[i][j];
}
}
vector<vector<long long>>reductions(contestants);
int available=0;
for(int i=0;i<contestants;i++){
if(i==ownRow){
continue;
}
vector<int>values;
for(int j=0;j<tasks;j++){
if(scores[ownRow][j]>0&&scores[i][j]>0){
values.push_back(scores[i][j]);
}
}
sort(values.rbegin(),values.rend());
reductions[i].push_back(0);
for(int value:values){
reductions[i].push_back(reductions[i].back()+value);
}
available+=static_cast<int>(values.size());
}
auto possible=[&](int hacks){
long long finalScore=totals[ownRow]+100LL*hacks;
int necessary=0;
for(int i=0;i<contestants;i++){
if(i==ownRow||totals[i]<finalScore){
continue;
}
long long needed=totals[i]-finalScore+1;
auto it=lower_bound(reductions[i].begin(),reductions[i].end(),needed);
if(it==reductions[i].end()){
return false;
}
necessary+=static_cast<int>(it-reductions[i].begin());
if(necessary>hacks){
return false;
}
}
return true;
};
if(!possible(available)){
cout<<-1<<'\n';
return 0;
}
int low=0;
int high=available;
while(low<high){
int middle=low+(high-low)/2;
if(possible(middle)){
high=middle;
}
else{
low=middle+1;
}
}
cout<<low<<'\n';
}