Halve or Subtract
Contest: Codeforces Round 854 by cybercats (Div. 1 + Div. 2)
Difficulty rating: 2700
Tags: binary search, brute force, dp, greedy, sortings

You have an array of positive integers $$$a_1, a_2, \ldots, a_n$$$, of length $$$n$$$. You are also given a positive integer $$$b$$$.

You are allowed to perform the following operations (possibly several) times in any order:

1. Choose some $$$1 \le i \le n$$$, and replace $$$a_i$$$ with $$$\lceil \frac{a_i}{2} \rceil$$$. Here, $$$\lceil x \rceil$$$ denotes the smallest integer not less than $$$x$$$.
2. Choose some $$$1 \le i \le n$$$, and replace $$$a_i$$$ with $$$\max(a_i - b, 0)$$$.

However, you must also follow these rules:

- You can perform at most $$$k_1$$$ operations of type 1 in total.
- You can perform at most $$$k_2$$$ operations of type 2 in total.
- For all $$$1 \le i \le n$$$, you can perform at most $$$1$$$ operation of type 1 on element $$$a_i$$$.
- For all $$$1 \le i \le n$$$, you can perform at most $$$1$$$ operation of type 2 on element $$$a_i$$$.

The cost of an array is the sum of its elements. Find the minimum cost of $$$a$$$ you can achieve by performing these operations.

Input format:
Input consists of multiple test cases. The first line contains a single integer $$$t$$$, the number of test cases ($$$1 \le t \le 5000$$$).

The first line of each test case contains $$$n$$$, $$$b$$$, $$$k_1$$$, and $$$k_2$$$ ($$$1 \le n \le 5000$$$, $$$1 \le b \le 10^9$$$, $$$0 \le k_1, k_2 \le n$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ describing the array $$$a$$$ ($$$1 \le a_i \le 10^9$$$).

It is guaranteed the sum of $$$n$$$ over all test cases does not exceed $$$5000$$$.

Output format:
For each test case, print the minimum cost of $$$a$$$ you can achieve by performing the operations.

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

Note:
In the first test case, you can do the following:

- Perform operation 2 on element $$$a_3$$$. It changes from $$$5$$$ to $$$3$$$.
- Perform operation 1 on element $$$a_1$$$. It changes from $$$9$$$ to $$$5$$$.

After these operations, the array is $$$a = [5, 3, 3]$$$ has a cost $$$5 + 3 + 3 = 11$$$. We can show that this is the minimum achievable cost.

In the second test case, note that we are not allowed to perform operation 1 more than once on $$$a_1$$$. So it is optimal to apply operation 1 once to each $$$a_1$$$ and $$$a_2$$$. Alternatively we could apply operation 1 only once to $$$a_1$$$, since it has no effect on $$$a_2$$$.

In the third test case, here is one way to achieve a cost of $$$23$$$:

- Apply operation 1 to $$$a_4$$$. It changes from $$$19$$$ to $$$10$$$.
- Apply operation 2 to $$$a_4$$$. It changes from $$$10$$$ to $$$7$$$.

After these operations, $$$a = [2, 8, 3, 7, 3]$$$. The cost of $$$a$$$ is $$$2 + 8 + 3 + 7 + 3 = 23$$$. We can show that this is the minimum achievable cost.

Example input:
7
3 2 1 1
9 3 5
2 1 2 0
1000000000 1
5 3 1 1
2 8 3 19 3
6 9 4 2
1 2 3 4 5 6
3 10 3 3
1 2 3
5 1 0 0
999999999 999999999 999999999 999999999 999999999
5 5 4 3
5 9 10 7 4

Example output:
11
500000001
23
6
0
4999999995
6

Editorial:
For convenience, let $$$half(x)$$$ denote $$$\lceil \frac{x}{2} \rceil$$$, and $$$sub(x)$$$ denote $$$\max(x - b, 0)$$$.
First, notice that if we apply both operations to some element, it will be optimal to apply halving first, then subtraction. We can prove this with 2 cases:
1. $$$a_i \le 2b$$$. In this case, $$$half(a_i) \le b$$$, and so $$$sub(half(a_i)) = 0$$$. Since applying either function to a nonnegative integer results in a nonnegative integer, $$$0 = sub(half(a_i)) \le half(sub(a_i))$$$.
2. Otherwise, $$$a_i > 2b$$$. Then $$$sub(half(a_i)) = a_i - \lfloor \frac{a_i}{2} \rfloor - b$$$, and $$$half(sub(a_i)) = a_i - b - \lfloor \frac{a_i - b}{2} \rfloor$$$. Since $$$\lfloor \frac{a_i - b}{2} \rfloor \le \lfloor \frac{a_i}{2} \rfloor$$$, $$$sub(half(a_i)) \le half(sub(a_i))$$$.
Next, suppose there are exactly $$$p$$$ elements to which we apply both operations. Then, it will be optimal to apply both operations to the $$$p$$$ greatest elements in the array. This should be somewhat intuitive, but here's a proof:
• Suppose there are some $$$a_i, a_j$$$ such that $$$a_i < a_j$$$. Suppose we apply both operations to $$$a_i$$$, and only one operation to $$$a_j$$$. Then applying both operations to $$$a_j$$$ and a single operation to $$$a_i$$$ instead won't increase the resulting sum. We can prove this with two cases:   We apply $$$half$$$ to $$$a_j$$$. Note that since it's optimal to apply $$$half$$$ first when applying both operations, this case is essentially: halve both elements, then choose one to apply $$$sub$$$ to. And it's better to subtract $$$b$$$ from the greater element, since $$$x - sub(x) \le y - sub(y)$$$ for $$$x \le y$$$.  We apply $$$sub$$$ to $$$a_j$$$. We can analyze this with (surprise!) a few cases:   $$$a_i, a_j \le 2b$$$. Then whichever element we apply both operations to will be $$$0$$$, and the result will depend only on the other element. $$$sub(x) \le sub(y)$$$ for $$$x \le y$$$, so it's better to apply both operations to the greater element.  $$$a_j > 2b$$$. If we apply both operations to the greater element, we subtract $$$\min(a_i, b) + \lfloor \frac{a_j}{2} \rfloor + b$$$ from the sum. But applying both operations to the lesser element subtracts $$$\lfloor \frac{a_i}{2} \rfloor + \min(half(a_i), b) + b \le \min(a_i, b) + \lfloor \frac{a_i}{2} \rfloor + b$$$ from the sum. So it's optimal to apply both operations to the greater element.  And this covers all cases where $$$a_i < a_j$$$.
• We apply $$$half$$$ to $$$a_j$$$. Note that since it's optimal to apply $$$half$$$ first when applying both operations, this case is essentially: halve both elements, then choose one to apply $$$sub$$$ to. And it's better to subtract $$$b$$$ from the greater element, since $$$x - sub(x) \le y - sub(y)$$$ for $$$x \le y$$$.
• We apply $$$sub$$$ to $$$a_j$$$. We can analyze this with (surprise!) a few cases:   $$$a_i, a_j \le 2b$$$. Then whichever element we apply both operations to will be $$$0$$$, and the result will depend only on the other element. $$$sub(x) \le sub(y)$$$ for $$$x \le y$$$, so it's better to apply both operations to the greater element.  $$$a_j > 2b$$$. If we apply both operations to the greater element, we subtract $$$\min(a_i, b) + \lfloor \frac{a_j}{2} \rfloor + b$$$ from the sum. But applying both operations to the lesser element subtracts $$$\lfloor \frac{a_i}{2} \rfloor + \min(half(a_i), b) + b \le \min(a_i, b) + \lfloor \frac{a_i}{2} \rfloor + b$$$ from the sum. So it's optimal to apply both operations to the greater element.  And this covers all cases where $$$a_i < a_j$$$.
• $$$a_i, a_j \le 2b$$$. Then whichever element we apply both operations to will be $$$0$$$, and the result will depend only on the other element. $$$sub(x) \le sub(y)$$$ for $$$x \le y$$$, so it's better to apply both operations to the greater element.
• $$$a_j > 2b$$$. If we apply both operations to the greater element, we subtract $$$\min(a_i, b) + \lfloor \frac{a_j}{2} \rfloor + b$$$ from the sum. But applying both operations to the lesser element subtracts $$$\lfloor \frac{a_i}{2} \rfloor + \min(half(a_i), b) + b \le \min(a_i, b) + \lfloor \frac{a_i}{2} \rfloor + b$$$ from the sum. So it's optimal to apply both operations to the greater element.
Let's fix $$$p$$$, the number of elements we apply both operations to. After taking them out, we will be left with the $$$n-x$$$ smallest elements in the array. Suppose we have $$$v_1$$$ operations of type 1 left, and $$$v_2$$$ operations of type 2 left. We'll assume $$$v_1 + v_2 \le n - x$$$ (otherwise we can apply both operations to more elements).
Notice that it's optimal to apply our $$$v_1 + v_2$$$ operations to the $$$v_1 + v_2$$$ greatest remaining elements: subtracting from a greater element can't decrease the amount we subtract, and halving a greater element can't decrease the amount we take away. So we're left with $$$v_1 + v_2$$$ elements, and we want to choose $$$v_1$$$ of them to apply the halving to.
Let's consider a few cases and try to analyze them. Let $$$a_i \le a_j$$$, and suppose we want to apply $$$half$$$ to one of them and $$$sub$$$ to the other.
• $$$a_i, a_j \le b$$$. Then it will be optimal to apply $$$sub$$$ to the greater element.
• $$$b \le a_i, a_j$$$. Then it will be optimal to apply $$$sub$$$ to the smaller element.
Using this information, we can form the final lemma we need for our solution:
• Let $$$a_i \le a_j \le a_k$$$. Suppose we apply $$$sub$$$ to $$$a_i$$$ and $$$a_k$$$, and $$$half$$$ to $$$a_j$$$. Then it will not increase the answer to apply $$$half$$$ to one of $$$a_i$$$ or $$$a_k$$$ instead.
There are 4 cases we should consider to prove this lemma:
• $$$a_k \le b$$$. Then we should apply $$$half$$$ to $$$a_i$$$ and $$$sub$$$ to the others.
• $$$b \le a_i$$$. Then we should apply $$$half$$$ to $$$a_k$$$ and $$$sub$$$ to the others.
• $$$a_i, a_j \le b \le a_k$$$. Then we should apply $$$half$$$ to $$$a_i$$$ and $$$sub$$$ to the others.
• $$$a_i \le b \le a_j, a_k$$$. Then we should apply $$$half$$$ to $$$a_k$$$ and $$$sub$$$ to the others.
You can verify that doing this produces the optimal answer. And using this lemma, we find that the optimal answer has all $$$sub$$$ operations applied to some of the middle elements, with all $$$half$$$ operations applied to the endpoints.
To summarize, the optimal answer will have a form like this (assuming $$$a$$$ is sorted in non-increasing order, $$$a_1 \ge a_2 \ge a_3 \ge \ldots \ge a_n$$$):
• First come some elements to which we apply both operations.
• Second come some elements to which we apply only $$$half$$$.
• Third come some elements to which we apply only $$$sub$$$.
• Fourth come some elements to which we apply only $$$half$$$.
• Finally come some elements to which we apply no operations.
Note that some of these segments may be empty.
It's easy to verify that it's optimal to use all given operations. So if we loop through all possible sizes for the first two segments, we can uniquely determine the sizes of the last three. Finally, using prefix sums to quickly find the sums of elements in a segment, we get an $$$O(n^2)$$$ solution.
There is an interesting fact: if we will fix the size of the first group $$$p$$$ and calculate the answer $$$f(p)$$$ for it, the function $$$f$$$ is convex. So the ternary or binary search can be used here to find the minimum in $$$O(n \log{n})$$$ time, but it was not necessary.