COEX01-Editorial

editorial
, , , ,
1

PROBLEM LINKS:
Practice
Contest

DIFFICULTY:
MEDIUM

PREREQUISITES:
Greedy
Knapsack

PROBLEM:
There are a total of ‘N’ letters and ‘S’ hours are given to burn them. Each love letter depending on the length and paper takes time ‘b’ minutes to burn. The aim is to find the minimum number of letters which can be burned in exactly ‘S’ hours. If the letters burn for less than “S” hours then aim is to find the total number of minutes for which the letters burns,which happens in case Chef runs out of letters. However, if the letters burns for more than “S” hours then find the minimum number of letters burned and the time in minutes for which the fire burns for after “S” hours.

EXPLANATION:
Step 1: Convert total burning time S in hours into minutes.
S=S*60
Step 2: To get the burning time S and minimum number of letters,we will pick the letter having longest burning time and if its burning time is less than or equal to the required burning time we consider this letter and decrement the burning time by this letter’s burning time to get the new burning time and count this letter in.
sort array ‘a’ containing burning times for letters in decreasing order
set burning­time=S

for(i=1 to n)
{
    if(burning­time >= a[i])
    {
        if(flag!=0)
        {
            cost=cost+a[i];
            cnt1++;
        }

        burning­time=(burning­time­a[i]);

        a[i]=­1; // to keep track of burned letters
    }
}

Step 3: If it is not possible to get exactly the burning time as S with the given number of letter, then we have to pick a letter from remaining letters such that we get burning cost as minimum, for this we have to pick a letter from the remaining whose burning cost is minimum of all the letters having burning cost greater than required and add it to the total cost and add one to number of letters, also calculate difference between actual burning time and required burning time.

if(burn­cost!=0)
{
    cnt1++;
    min=a[n­1];
    for(i=n­1;i>=0;i­­)
    {
        if((a[i]!= ­1) && (a[i]<=min) && (a[i]>=(sum­cost)))
        {
            min=a[i];
        }
     }
     diff=(min+cost)­(sum);
}

*There is a corner case in the problem, if the sum of cost of all the letters ‘n’ is less than the required burning time then simply print ‘n’ in the output.

Solution:
Author’s solution can be found here.