Minimizing Difference
Contest: Codeforces Round 592 (Div. 2)
Difficulty rating: 2000
Tags: binary search, constructive algorithms, greedy, sortings, ternary search, two pointers

You are given a sequence $$$a_1, a_2, \dots, a_n$$$ consisting of $$$n$$$ integers.

You may perform the following operation on this sequence: choose any element and either increase or decrease it by one.

Calculate the minimum possible difference between the maximum element and the minimum element in the sequence, if you can perform the aforementioned operation no more than $$$k$$$ times.

Input format:
The first line contains two integers $$$n$$$ and $$$k$$$ $$$(2 \le n \le 10^{5}, 1 \le k \le 10^{14})$$$ — the number of elements in the sequence and the maximum number of times you can perform the operation, respectively.

The second line contains a sequence of integers $$$a_1, a_2, \dots, a_n$$$ $$$(1 \le a_i \le 10^{9})$$$.

Output format:
Print the minimum possible difference between the maximum element and the minimum element in the sequence, if you can perform the aforementioned operation no more than $$$k$$$ times.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example you can increase the first element twice and decrease the third element twice, so the sequence becomes $$$[3, 3, 5, 5]$$$, and the difference between maximum and minimum is $$$2$$$. You still can perform one operation after that, but it's useless since you can't make the answer less than $$$2$$$.

In the second example all elements are already equal, so you may get $$$0$$$ as the answer even without applying any operations.

Example input:
4 5
3 1 7 5

Example output:
2

Example input:
3 10
100 100 100

Example output:
0

Editorial:
Suppose that the maximum value in the resulting array should be $$$R$$$, and the minimum value should be $$$L$$$. Let's estimate the required number of operations to make an array with such properties. All elements that are less than $$$L$$$ should be increased to $$$L$$$, and all elements that are greater than $$$R$$$ should be decreased to $$$R$$$ — and we don't have to do any operation with remaining elements.
Now we claim that either $$$L$$$ or $$$R$$$ should belong to the initial array. Why so? Suppose we constructed an answer such that $$$L \notin A$$$ and $$$R \notin A$$$. If the number of elements we increased to $$$L$$$ is not less than the number of elements we decreased to $$$R$$$, then we could construct the answer with minimum equal to $$$L - 1$$$ and maximum equal to $$$R - 1$$$, and it would not require more operations. And if the number of elements we increased to $$$L$$$ is less than the number of elements we decreased to $$$R$$$, then we construct the answer for $$$L + 1$$$ as minimum and $$$R + 1$$$ as maximum. So we can shift the range $$$[L, R]$$$ so that one of its endpoints belongs to the initial array.
Now we can solve the problem as follows: iterate on the maximum in the resulting array and find the largest minimum we can obtain with binary search, and then do it vice versa: iterate on the minimum in the resulting array and find the largest maximum we can obtain with binary search. To check how many operations we need, for example, to make all values not less than $$$L$$$, we can find the number of elements that we have to change with another binary search (let the number of such elements be $$$m$$$), and find their sum with prefix sums (let their sum be $$$S$$$). Then the required number of operations is exactly $$$Lm - S$$$. The same approach can be used to find the number of operations to make all elements not greater than $$$R$$$.
This is the way the problem was supposed to solve, but, unfortunately, we failed to find a much easier greedy solution.