CHEFEXAM Editorial

Problem Link:
Contest
Practice

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.

Explanation:

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])

break

Else

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