HOLIDAYS - Editorial

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:

Greedy

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;
}

why does this code is giving the wrong answer

#include <bits/stdc++.h>
using namespace std;

void find(int arr[],int n,int w)
{
int sum=0;
int temp;
for(int i=1;i<=n;i++)
{

    if(sum>w)
    {cout<<n-temp<<endl;
    break;    }
    
    else{ sum+=arr[i-1];
          
        
        
        temp=i; }
        
        //      temp  =1   temp =2  temp = 3 temp = 4 
         if(i==n)
        cout<<"0"<<endl;
    }
    
}

int main() {
// your code goes here
int t;
cin>>t;

while(t--)
{
    int n,w;
    cin>>n>>w;
    int arr[n];
    for(int i=0;i<n;i++)
    {
        
        cin>>arr[i];
        
    }
    sort(arr,arr+n,greater<int>());
    find(arr,n,w);
    
}


return 0;

}

@notsoloud

We need atleast W rupees. This means you should break the loop once the sum is greater than or equal to W.