Count number of above-average people, a person is considered above-average if he/she obtains above-average marks in at least one of the exams.
EXPLANATION:
Create an array of size N, initialize it with all 0’s, arr[i] contains count of exams for which ith person obtained above-average marks.
Now iterate over each exam find the average, and then iterate over it again to find above-average people and increase their arr[i] by one.
The output will be the number of non-zero entries of arr.
Alternatively, you can use maps/dictionaries to maintain above-average people
The test-cases which you are using to determine the verdict i.e AC, WA, TLE. is not correct because there are two ways of calculating the average of N integers.
One is to simply use the formula for average: Average = \frac{\sum\limits_{i=0}^{n - 1} a[i]}{n}
Another way is use an algorithm given by Donald K Knuth known as Better Average Algorithm. using which I can calculate the average as follows:
static double better_average_algorithm(const int *const data, const unsigned int n) {
double avg = 0.0;
for(unsigned int i = 0; i < n; ++i) {
avg += (data[i] - avg) / (i + 1);
}
return avg;
}
When I use the second approach which is much efficient and chances of integer overflow is very less as compare to naive algorithm to calculate the average marks of the students in the i^{th} exam and then finding how many students will be selected for the club as described in the problem, the verdict was WA rather it should be AC.
On the other hand if I use naive algorithm to calculate the average the program receive a verdict AC.
Why is that? You should check your test cases or if there is a bug in my code when I used the second approach, then I would really appreciate it you tell me in which test case I got the WA.
Just telling : instead of checking whether x > \frac{\sum_{i = 1}^{n}a[i]}{n}, it is better to check nx > \sum_{i = 1}^{n}a[i]. No doubles, no overflow.
Ya I know, but my concern is about calculating the average in two different ways.
Moreover you are still doing the sum, well what if I change the constraints for total students giving the exam from 100 to 10^{18}.
Waste your time trying to learn about these kind of error-prone algorithms (instead of using a better approach) , and you won’t progress in CP.
And btw, what you wrote (the testcases are incorrect ) is definitely wrong, since the author’s solution is correct and it passes the tests.
