Exam Preparation
National Olympiad — National round
Submission name: exams.cpp
Problem summary
Exam i currently yields bᵢ points and has maximum aᵢ. Each day increases every unfinished exam score by one, so after d days its score is min(aᵢ,bᵢ+d). Find the fewest days needed for total score at least M.
Input
N M; N maximum scores; N current scores.
Output
The minimum number of days.
Constraints
2 ≤ N ≤ 1,000,000; N ≤ M < 2⁶⁴; 1 ≤ aᵢ ≤ 2⁴⁴; 0 ≤ bᵢ ≤ aᵢ; M ≤ Σaᵢ. Half the tests have N≤1000, M≤1,000,000, aᵢ≤1000.
Worked example
An independently prepared example for this explanation.
Input
2 12 10 8 3 1
Output
4
Solution analysis
- Binary-search days from 0 to the largest individual deficit aᵢ−bᵢ.
- Evaluate the resulting total with a wide unsigned accumulator, stopping once M is reached.
Why it works
Each individual score and hence their sum are nondecreasing with days. The upper bound reaches every exam maximum and is feasible, so standard first-true binary search returns the minimum.
Watch out. M may exceed signed 64-bit range. Zero days is a valid answer.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Each individual score and hence their sum are nondecreasing with days. The upper bound
// reaches every exam maximum and is feasible, so standard first-true binary search returns the
// minimum.
#include<iostream>
#include<vector>
#include<algorithm>
#include<tuple>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
unsigned long long m;
cin>>n>>m;
vector<unsigned long long>a(n),b(n);
for(auto&x:a){
cin>>x;
}
unsigned long long hi=0;
for(int i=0;i<n;i++){
cin>>b[i];
hi=max(hi,a[i]-b[i]);
}
auto enough=[&](unsigned long long days){
unsigned __int128 sum=0;
for(int i=0;i<n;i++){
sum+=min(a[i],b[i]+days);
if(sum>=m){
return true;
}
}
return false;
};
unsigned long long lo=0;
while(lo<hi){
auto mid=lo+(hi-lo)/2;
if(enough(mid)){
hi=mid;
}
else{
lo=mid+1;
}
}
cout<<lo<<'\n';
}