Half-sum
Contest: Codeforces Round 869 (Div. 1)
Difficulty rating: 3400
Tags: brute force, divide and conquer, greedy

You're given a multiset of non-negative integers $$$\{a_1, a_2, \dots, a_n\}$$$.

In one step you take two elements $$$x$$$ and $$$y$$$ of the multiset, remove them and insert their mean value $$$\frac{x + y}{2}$$$ back into the multiset.

You repeat the step described above until you are left with only two numbers $$$A$$$ and $$$B$$$. What is the maximum possible value of their absolute difference $$$|A-B|$$$?

Since the answer is not an integer number, output it modulo $$$10^9+7$$$.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). Description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 10^6$$$) — the size of the multiset.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — the elements of the multiset.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output format:
For each test case, output a single integer, the answer to the problem modulo $$$10^9+7$$$.

Formally, let $$$M = 10^9+7$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output an integer $$$x$$$ such that $$$0 \le x < M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.

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

Note:
In the first case, you can't do any operations, so the answer is $$$|7-3|=4$$$.

In the second case, one of the optimal sequence of operations:

1. Substitute $$$1$$$ and $$$2$$$ with $$$1.5$$$;
2. Substitute $$$10$$$ and $$$11$$$ with $$$10.5$$$;
3. The difference between $$$1.5$$$ and $$$10.5$$$ is $$$9$$$.

In the third case, the exact answer is $$$\frac{3}{2}$$$, and $$$500\,000\,005 \cdot 2 \equiv 3 \pmod{10^9+7}$$$.

Example input:
5
2
7 3
4
1 2 10 11
3
1 2 3
6
64 32 64 16 64 0
4
1 1 1 1

Example output:
4
9
500000005
59
0

Editorial:
Similar to the Huffman encoding, the process described in the statement can be represented as constructing a tree, in which on every step we take two trees with weights $$$a$$$ and $$$b$$$, and connect them with a shared root into a single tree with weight $$$\frac{a+b}{2}$$$.
In the end of the process, we have two trees with weights $$$A$$$ and $$$B$$$, and we want to maximize $$$|A-B|$$$. In these trees, let $$$h_i$$$ be the height of the leaf corresponding to $$$a_i$$$. Then $$$a_i$$$ contributes to the final answer with the coefficient either $$$2^{-h_i}$$$, or $$$-2^{-h_i}$$$, depending on which tree it is in.
If we fix any set $$$\{h_1, \dots, h_n\}$$$ and would need to distribute $$$a_1, \dots, a_n$$$ between the heights, assuming $$$A < B$$$, it would always be better to send smaller numbers to the $$$A$$$-tree and bigger numbers to the $$$B$$$-tree, so that the positive impact belongs to bigger numbers and the negative impact belongs to the smaller numbers. That being said, if $$$a_1 \leq a_2 \leq \dots \leq a_n$$$, it is always optimal to choose a number $$$1 \leq k < n$$$ and send $$$a_1, a_2, \dots, a_k$$$ to the $$$A$$$-tree, while sending $$$a_{k+1}, a_{k+2}, \dots, a_n$$$ to the $$$B$$$-tree. Now we need to understand, how to pick an optimal $$$k$$$ and how to construct optimal trees with a fixed $$$k$$$.
Assume that $$$a_1, a_2, \dots, a_k$$$ will all go to the $$$A$$$-tree, for which we want to minimize the weight. What is the optimal distribution of $$$h_1, h_2, \dots, h_k$$$? Turns out, there always exists an optimal configuration, in which the constructed tree is very skewed, in a way that each vertex has at most $$$1$$$ child that is not a leaf.
Indeed, consider a vertex $$$v$$$ which has two children $$$L$$$ and $$$R$$$, both of which have children of its own. Let $$$x$$$ be a leaf with the smallest weight in the whole sub-tree of $$$v$$$ (without loss of generality, assume that it's a descendant of $$$L$$$). If we swap $$$x$$$ with $$$R$$$, we will effectively swap coefficients with which $$$x$$$ and $$$R$$$ contribute to the weight of $$$A$$$ overall.
In other words, if the initial contribution was $$$2^{-h_x} \cdot x + 2^{-h_R} \cdot R$$$, it will become $$$2^{-h_x} \cdot R + 2^{-h_R} \cdot x$$$. Note that $$$x \leq R$$$ and $$$h_x > h_R$$$. As a consequence, the later sum is not worse than the former and it's always optimal to swap $$$x$$$ and $$$R$$$ due to the rearrangement inequality.
Similar argument works for the tree $$$B$$$, except for we want to maximize sum in it, rather than minimize it.
With this in mind, if the split is $$$a_1, a_2, \dots, a_k$$$ and $$$a_{k+1}, a_{k+2}, \dots, a_n$$$, then the heights are $$$1, 2, 3, \dots, k-2, k-1, k-1$$$ for the first block, and similar (but reversed) for the second block. This allows us to find a specific value of $$$|A-B|$$$ for each specific $$$k$$$ in $$$O(n)$$$.
How to improve from that? We suggest two possible approaches here.
Divide and conquer approach. Assume that the optimal $$$k$$$ belongs to the interval $$$[l, r]$$$. In this case, all numbers outside the interval will have the same coefficients regardless of specific $$$k$$$, as long as $$$k$$$ itself is from the interval. This means that we can solve the problem with divide and conquer approach:
1. Let $$$m = \lfloor \frac{r-l}{2}\rfloor$$$;
2. Find best $$$k$$$ recursively on $$$[l, m]$$$ and $$$[m, r]$$$;
3. Compare them on the whole $$$[l; r]$$$, and return the best of them.
Which makes overall $$$O(n \log n)$$$ complexity.
Alternative approach. Let's compare the distribution of coefficients for $$$|A|=k$$$ and $$$|A|=k-1$$$:
As you see, almost all coefficients stay the same, except for coefficients near $$$a_{k-1}$$$, $$$a_k$$$ and $$$a_{k+1}$$$:
Therefore, let $$$f(k)$$$ be the optimal answer for $$$|A|=k$$$, and let $$$\alpha=k-1$$$, $$$\beta=n-k$$$ we may say that
$$$$$$ f(k) - f(k-1) = (a_{k+1}-a_k)2^{-\beta} - (a_k - a_{k-1}) 2^{-\alpha}. $$$$$$
Or, multiplying it with $$$2^n$$$ we get
$$$$$$ 2^n[f(k) - f(k-1)] = (a_{k+1}-a_k)2^{k} - (a_k - a_{k-1}) 2^{n-k+1}. $$$$$$
We can sum it up to get the difference between $$$f(k)$$$ and $$$f(j)$$$ for arbitrary $$$j < k$$$:
$$$$$$ 2^n [f(k) - f(j)] = (d_k 2^k + \dots + d_{j+1} 2^{j+1}) - (d_{k-1}2^{n-(k-1)} + \dots + d_j 2^{n-j}), $$$$$$
where $$$d_i = a_{i+1} - a_i$$$. Then, assuming $$$d_k > 0$$$, we can bound it as
$$$$$$ 2^n [f(k) - f(j)] \geq 2^k - 2^{n-j}\max d_i = 2^k - 2^{n-j+\log \max d_i}. $$$$$$
The later means that $$$f(k) > f(j)$$$ when $$$k + j > n + \log \max d_i$$$, which is the case when $$$k > \frac{n}{2} + \log \max d_i$$$ and $$$j \geq \frac{n}{2}$$$. By the same argument, we may show that $$$f(k) > f(j)$$$ when $$$k < \frac{n}{2} - \log \max d_i$$$ and $$$k < j < \frac{n}{2}$$$. In other words, it means that one of the following holds for the value $$$k$$$, on which the maximum value of $$$f(k)$$$ is achieved:
• $$$k$$$ is the first position in the array, at which $$$d_k = a_{k+1} - a_k > 0$$$,
• $$$k$$$ is the last position in the array, at which $$$d_k = a_{k+1} - a_k > 0$$$,
• $$$k$$$ belongs to the segment $$$[\frac{n}{2} - \log \max d_i, \frac{n}{2} + \log \max d_i] \subset [\frac{n}{2}-30, \frac{n}{2}+30]$$$.
Therefore, there are at most $$$64$$$ positions of interest in the array which can be checked manually. Moreover, optimal value in the segment $$$[\frac{n}{2}-30, \frac{n}{2}+30]$$$ can be found by checking every possible position while ignoring all the elements outside of the segment (due to the result from the divide and conquer approach). This allows, assuming $$$a_1 \leq a_2 \leq \dots \leq a_n$$$, to resolve the problem in $$$O(n)$$$.