SAVL - Editorial

editorial
, ,
1

PROBLEM LINK:

Deepavali Code Battle

Author: Saksham Aggarwal
Tester: Amisha Garg
Editorialist: Amisha Garg

DIFFICULTY:

EASY

PREREQUISITES:

Greedy

PROBLEM:

Given the distances of laddus from Lakshika’s house, maximize the number of laddus that she can take to her house without being eaten by the cat.

QUICK EXPLANATION:

Start from the nearest laddu from the home and keep on moving the nearest laddu towards the home, also incrementing the position of the cat each time after a laddu is moved by one place.

EXPLANATION:

Let d be the number of laddus we will save from the cat. Then it is more efficient to save d laddus such that they are the closest ones to Lakshika’s house.
So firstly, we will pick up the laddu that is closest to Lakshika’s house.
Hence, to find which laddu is closest to Lakshika’s house, let’s first sort the array of distances of laddus from Lakshika’s house in ascending order.

Now let’s start iterating over the array from the last laddu, and also each time whenever Lakshika moves a laddu by one unit, the cat also moves towards the house by one unit and eats up all the laddu’s present at its new position.
Continue doing this until any laddu hasn’t been hidden in the house or isn’t eaten.

TIME COMPLEXITY:

For sorting: O(k log k)
For traversing the array: O(k)
Overall time complexity would be O(k log k) per test case, where k is the number of laddus.

SOLUTIONS:

Setter's Solution 
#include<bits/stdc++.h>
using namespace std;

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,k;
        cin>>n>>k;
        int arr[k];
        for(int i=0;i<k;i++)
            cin>>arr[i];
        int cat=0;
        sort(arr, arr+k);
        int ans=0;
        for(int i=0;i<k;i++)
        {
            int curr=arr[k-i-1];
            if(curr>cat)
            {
                cat+=(n-curr);
                ans++;
            }
            else
                break;
        }
        cout<<ans<<"\n";
    }
}
Editorialist's Solution 
#include<bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin>>t;
    while(t--){
        int n,k;
        cin>>n>>k;
        int arr[k];
        for(int i=0; i<k; i++){
            cin>>arr[i];
        }
        sort( arr, arr+k);
        int cat = 0;
        int laddu = 0;
        int last = k-1;
        while( last>=0 && arr[last] > cat ){
            cat += n - arr[last--];
            ++laddu;
        }
        cout<<laddu<<"\n";
    }
    return 0;
}