Internet Problem Solving Contest

IPSC 2007

Solution to Problem P – Paradox With Averages

After we remove a number from a set of numbers, the average of the set will increase if and only if the removed number was smaller than the original average.

Mathematically, if S was the sum of the original set, N the count of its elements, and x the element we removed, we get the inequality:

S/N < (S-x)/(N-1)

Solving for x we get x ≤ S/N, which is exactly what we claimed.

Similarly, the average will increase after adding a new element if and only if the added element exceeds the original average.

Thus all we need to do is to compute both averages and then count the numbers that fall between them. This can be done using a linear search and some simple integer arithmetics.