ABOVEAVG Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Utkarsh Gupta
Tester: Jakub Safin, Satyam
Editorialist: Pratiyush Mishra

DIFFICULTY:

1278

PREREQUISITES:

None

PROBLEM:

There are N students in a class. Recently, an exam on Advanced Algorithms was conducted with maximum score M and minimum score 0. The average score of the class was found out to be exactly X.

Given that a student having score strictly greater than the average receives an A grade, find the maximum number of students that can receive an A grade.

EXPLANATION:

Let us look at the two cases for this problem:

  • X=M: Here it implies that every single student has scored M marks and since no student can score more than M marks. Thus in this case no student would receive A grade.
  • X < M: Let us take a variable sum as the sum of marks of all students. Then
sum = N \times X

Now to maximise students who score more than average marks we assign (X+1) marks to as many students as possible, which would be our answer.

answer = \lfloor \frac{sum}{X+1} \rfloor

TIME COMPLEXITY:

O(1), for each test case.

SOLUTION:

Editorialist’s Solution
Setter’s Solution
Tester1’s Solution
Tester2’s Solution

In the problem, it was not mentioned that the scores of the student must be integer. Also, the sample test cases passed the solutions which assumed the solutions to include non-integer scores.

3 Likes

So true man! Was stuck for good time in this…

I don’t get it. Why would answer be the floor of n*x/(x+1) ? I understand we are trying to maximise but I can’t make the connection between that and the mathematical expression. Can someone please elaborate?

5 Likes

Average = Sum of score/ N.
So sum of score = NX
Number the persons from 1 to N. Start assigning them (X+1) scores from 1 to N. What’s the maximum number of person you can assign X+1 exactly floor(N
X/(X+1)). After that you’ll be left with N*X mod (X+1) score which is less than X+1 which it doesn’t to whom you give

1 Like

I Know the approach I used in below code is not optimized but still I want to know why the last teste case is failling ?

#include <iostream>
using namespace std;

int main() {

    int T ; cin>>T; 
    while(T--)
    {
        double n ,m ,x; cin>>n>>m>>x;
        
        if(m==x)
        {
            cout<<0<<endl;
            continue;
        }
        
        for(int i=1 ; i<=n ; i++)
        {
            if(((x+1)*(n-i))/n<=x)
            {
                cout<<n-i<<endl;
                break;
            }
        }
    }

	return 0;
}