CHEFEXAM Editorial

Problem Link:

Author: Rajat De

Editorialist: Sidhant Bansal

Difficulty: Easy

Pre-requisites: Sorting

Quick Explanation:
Sort all the subjects in descending order according to C[i] and then greedily spend the hours on each of the subject turn by turn till the time the average does not come upto M.


For the average to be at least M, the total of all the marks should be at least M*N

If \sum A[i] \geq M*N then answer is 0.

Otherwise, calculate delta = (M*N) - \sum A[i]

Now, the original question reduces to studying least amount of hours so as to gain delta marks.

For calculating this, follow the below pseudocode -

Sort all subjects in descending order according to C[i]

Set answer = 0

For i = 1 to N

If B[i] - A[i] \geq delta

answer = answer + ceil(delta/C[i])



answer = answer + (B[i] - A[i])/C[i]

delta = delta - (B[i] - A[i])

Print answer

Complexity: Time complexity is O(N * logN) and memory complexity is O(N)

The alternate solution is binary search on answer along with min cost max flow, please refer to the author solution for more details.

Author Solution