CLARISSA - Editorial

PROBLEM LINK:

Practice
Contest

Author: mesksr
Editorialist: mesksr

DIFFICULTY:

EASY

PREREQUISITES:

Math, Fast Modular Exponentiation

PROBLEM:

Given a list of the integers, we have to tell the number of ways of selecting integers such that thier arithmetic mean is maximum.

EXPLANATION:

We can get maximum arithmetic mean, only when one or more occurances of maximum element of list is selected. (like in second example we selected {90}, {90} and {90,90})
So, we need to count the number of times (say c) the maximum element of list occurs.
Now, the answer will be 2^c - 1.
2^c means : for each of c elements, we are either selecting it or not. (for second example c = 2, 2^c denotes {}, {90}, {90}, {90,90})
-1 : for removing the case when we did not select any of the c elements. (removing this -> {})

To calculate 2^c, we can get TLE if c is very large. So, we will use Fast Modulo Multiplication. Read more about it here

AUTHOR’S SOLUTION:

Author’s solution can be found here.