PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Jeevan Jyot Singh
Tester: Harris Leung
Editorialist: Kanhaiya Mohan
DIFFICULTY:
Cakewalk
PREREQUISITES:
PROBLEM:
Ved needs to earn atleast W rupees in N days.However, on a given day i (1 \leq i \leq N), he can only earn A_i rupees by working on that day.
Help maximise the number of days on which Ved can take a holiday, still earning the required amount.
EXPLANATION:
Observation
Ved should work on the days when payment is more. Similarly, Ved can take holidays when pay is less for that day.
Solution
To maximise the payment, Ved should work on the days which pay the most. Since he needs W rupees only, he can take holidays for the rest of the days.
We sort the days based on payment in descending order. Keep a count of the money earned till day i in the sorted array. Once the amount reaches W, Ved can take holidays for all the days thereafter.
TIME COMPLEXITY:
Sorting an array takes O(Nlog(N)) time. After sorting, we traverse the array in O(N). Thus, the time complexity is O(Nlog(N)) per test case.
SOLUTION:
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const ll mod=998244353;
int t;
int n,m;
ll a[300001];
ll s=0;
int main(){
ios::sync_with_stdio(false);cin.tie(0);
int t;cin >> t;
while(t--){
cin >> n >> m;
for(int i=1; i<=n ;i++){
cin >> a[i];
m-=a[i];
}
sort(a+1,a+n+1);
for(int i=1; i<=n ;i++){
if(a[i]+m>0){
cout << i-1 << '\n';
break;
}
m+=a[i];
}
}
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin>>t;
while(t--){
int n, w;
cin>>n>>w;
vector<int> a(n);
for(int i = 0; i<n; i++){
cin>>a[i];
}
sort(a.rbegin(), a.rend()); //sorting a vector in descending order
int curr_sum = 0;
int curr_day = 0;
for(; curr_day<n; curr_day++){
curr_sum += a[curr_day];
if(curr_sum>=w){
break;
}
}
int rem_days = (n-1) - curr_day; //array is 0-indexed
cout<<rem_days<<endl;
}
return 0;
}