Halve or Subtract (Codeforces 1799F)
Tags: 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:   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$$$.  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: 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: For each test case, print the minimum cost of $$$a$$$ you can achieve by performing the operations.

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.

Sample Inputs:
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

Sample Outputs:
11
500000001
23
6
0
4999999995
6

Solution (Python):
import sys
input = sys.stdin.readline
from operator import itemgetter
t = int(input())
for tests in range(t):
    (n, b, k1, k2) = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort(reverse=True)
    B = [(a + 1) // 2 for a in A]
    C = [max(a - b, 0) for a in A]
    D = [max(0, (a + 1) // 2 - b) for a in A]
    SA = [0]
    SB = [0]
    SC = [0]
    SD = [0]
    for a in A:
        SA.append(SA[-1] + a)
    for a in B:
        SB.append(SB[-1] + a)
    for a in C:
        SC.append(SC[-1] + a)
    for a in D:
        SD.append(SD[-1] + a)
    ANS = 1 << 60
    for hs in range(min(k1, k2) + 1):
        r1 = k1 - hs
        r2 = k2 - hs
        for h1 in range(r1 + 1):
            r1x = r1 - h1
            if hs + h1 + r1x + r2 > n:
                continue
            score = SD[hs] + (SB[h1 + hs] - SB[hs]) + (SC[h1 + hs + r2] - SC[h1 + hs]) + (SB[h1 + hs + r1x + r2] - SB[h1 + hs + r2]) + (SA[-1] - SA[h1 + hs + r1x + r2])
            ANS = min(ANS, score)
    print(ANS)

Solution (Python):
import sys
import io
import os
BUFSIZE = 8192

class FastIO(io.IOBase):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.buffer = io.BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(io.IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
    """"""
    (sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop('end', '\n'))
    if kwargs.pop('flush', False):
        file.flush()
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def read_int_list():
    return list(map(int, input().split()))

def read_int_tuple():
    return map(int, input().split())

def read_int():
    return int(input())
read_str = input
MOD = 998244353
inf = 1 << 60

def solve():
    (n, b, k1, k2) = read_int_tuple()
    A = read_int_list()
    A.sort(reverse=True)
    ans = inf
    for p in range(max(0, k1 + k2 - n), min(k1, k2) + 1):
        res = 0
        for i in range(p):
            res += max(0, (A[i] + 1) // 2 - b)
        B = []
        for i in range(p, k1 + k2 - p):
            (hal, sub) = ((A[i] + 1) // 2, max(0, A[i] - b))
            B.append(sub - hal)
            res += hal
        for i in range(k1 + k2 - p, n):
            res += A[i]
        m = k2 - p
        cur = tr = sum(B[:m])
        for i in range(m, len(B)):
            cur += B[i] - B[i - m]
            if tr > cur:
                tr = cur
        ans = min(ans, res + tr)
    print(ans)
T = read_int()
for t in range(T):
    solve()

Solution (Python):
import sys
import io
import os
BUFSIZE = 8192

class FastIO(io.IOBase):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.buffer = io.BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(io.IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
    """"""
    (sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop('end', '\n'))
    if kwargs.pop('flush', False):
        file.flush()
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def read_int_list():
    return list(map(int, input().split()))

def read_int_tuple():
    return map(int, input().split())

def read_int():
    return int(input())
read_str = input
MOD = 998244353
inf = 1 << 60

def solve():
    (n, b, k1, k2) = read_int_tuple()
    A = read_int_list()
    A.sort(reverse=True)
    ans = sum(A)
    for p in range(max(0, k1 + k2 - n), min(k1, k2) + 1):
        res = 0
        for i in range(p):
            res += max(0, (A[i] + 1) // 2 - b)
        B = []
        for i in range(p, k1 + k2 - p):
            (hal, sub) = ((A[i] + 1) // 2, max(0, A[i] - b))
            B.append(sub - hal)
            res += hal
        for i in range(k1 + k2 - p, n):
            res += A[i]
        m = k2 - p
        cur = tr = sum(B[:m])
        for i in range(m, len(B)):
            cur += B[i] - B[i - m]
            if tr > cur:
                tr = cur
        ans = min(ans, res + tr)
    print(ans)
T = read_int()
for t in range(T):
    solve()