STEPAVG - Editorial

PROBLEM LINKS

Practice
Contest

DIFFICULTY

CHALLENGE

EXPLANATION

There are several different approaches to this problem (and the top contestants always provide a broad range of them).

The simplest of them resulting in a reasonable score is greedy. We’ll try to make the set of numbers smaller and closer overall to K at the same time. To do this, take the smallest (X) and the largest (Y) number out of the remaining ones. If K is much smaller than their average (X+Y)/2, then it’s reasonable to use two largest numbers for the current operation (as there are. too many large numbers at the moment). If K is much larger than their average, then use two smallest numbers (as there are too many small numbers at the moment). Finally, if K is close to their average (the exact definition of “close” may differ), then use the smallest and the largest number – this way you replace two numbers which are far from K with one number which is close to K.

A better approach is doing the greedy in the reverse order – that is, we don’t change the given set of numbers (except removing some), but we change K. The idea is taking the smallest (X) and the largest (Y) numbers available again. If K is much smaller than (X+Y)/2, let’s say that the last operation is replacing the smallest number and what we get from the remaining numbers with their average. Then it’s clear that the number we should get from the remaining ones should be close to 2K-X. Similarly, if K is much larger than (X+Y)/2, then use the largest number in the last operation and try to get as close as possible to 2K-Y with the remaining numbers. Finally, if K is close to (X+Y)/2, then replace X and Y with (X+Y)/2. This kind of approach was successfully implemented by David Stolp (pieguy) for the top spot. I found the solutions of other top scorers less readable, so I’d like to ask them to share their ideas :slight_smile:

And the last but not the least, I want to apologize for the tie of the top scorers. Actually, their solutions get the smallest possible score – the differences of their results and K are less than 10^(-6). The reason they didn’t get the score of 0.000000 is simple – there exists a test case where K is less than all of Ai. In fact, making the constraint on N lower would have helped to distinguish them, but it was too late to change anything when I realized that.

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.