Pursuit (Codeforces 1544C)
Tags: Others, binary search

You and your friend Ilya are participating in an individual programming contest consisting of multiple stages. A contestant can get between $$$0$$$ and $$$100$$$ points, inclusive, for each stage, independently of other contestants.Points received by contestants in different stages are used for forming overall contest results. Suppose that $$$k$$$ stages of the contest are completed. For each contestant, $$$k - \lfloor \frac{k}{4} \rfloor$$$ stages with the highest scores are selected, and these scores are added up. This sum is the overall result of the contestant. (Here $$$\lfloor t \rfloor$$$ denotes rounding $$$t$$$ down.)For example, suppose $$$9$$$ stages are completed, and your scores are $$$50, 30, 50, 50, 100, 10, 30, 100, 50$$$. First, $$$7$$$ stages with the highest scores are chosen — for example, all stages except for the $$$2$$$-nd and the $$$6$$$-th can be chosen. Then your overall result is equal to $$$50 + 50 + 50 + 100 + 30 + 100 + 50 = 430$$$.As of now, $$$n$$$ stages are completed, and you know the points you and Ilya got for these stages. However, it is unknown how many more stages will be held. You wonder what the smallest number of additional stages is, after which your result might become greater than or equal to Ilya's result, at least in theory. Find this number!

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). Description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of completed stages.The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 100$$$) — your points for the completed stages.The third line contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$0 \le b_i \le 100$$$) — Ilya's points for the completed stages.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output: For each test case print a single integer — the smallest number of additional stages required for your result to be able to become greater than or equal to Ilya's result.If your result is already not less than Ilya's result, print $$$0$$$.

Note: In the first test case, you have scored $$$100$$$ points for the first stage, while Ilya has scored $$$0$$$. Thus, your overall result ($$$100$$$) is already not less than Ilya's result ($$$0$$$).In the second test case, you have scored $$$0$$$ points for the first stage, while Ilya has scored $$$100$$$. A single stage with an opposite result is enough for both your and Ilya's overall scores to become equal to $$$100$$$.In the third test case, your overall result is $$$30 + 40 + 50 = 120$$$, while Ilya's result is $$$100 + 100 + 100 = 300$$$. After three additional stages your result might become equal to $$$420$$$, while Ilya's result might become equal to $$$400$$$.In the fourth test case, your overall result after four additional stages might become equal to $$$470$$$, while Ilya's result might become equal to $$$400$$$. Three stages are not enough.

Sample Inputs:
5
1
100
0
1
0
100
4
20 30 40 50
100 100 100 100
4
10 20 30 40
100 100 100 100
7
7 59 62 52 27 31 55
33 35 50 98 83 80 64

Sample Outputs:
0
1
3
4
2

Solution (Python):
t = int(input())

def solve(n, A, B):
    A.sort()
    B.sort()
    k = int(n / 4)
    j = k - 1
    sumA = sum(A[k:])
    sumB = sum(B[k:])
    i = 0
    while sumA < sumB:
        i += 1
        n += 1
        sumA += 100
        if n % 4 == 0:
            k = int(n / 4) - 1
            sumA -= A[k]
            continue
        if j >= 0:
            sumB += B[j]
        j -= 1
    print(i)
for _ in range(t):
    n = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    solve(n, A, B)

Solution (Python):
def check(suffixA, suffixB, m):
    k = n + m - (n + m) // 4
    vb = suffixB[0] if k >= n else suffixB[n - k]
    if k > m:
        va = m * 100
        k -= m
        assert k <= n
        if k != 0:
            va += suffixA[n - k]
    else:
        va = k * 100
    return va >= vb
T = int(input())
for _ in range(T):
    n = int(input())
    A = [int(e) for e in input().split(' ')]
    A.sort()
    B = [int(e) for e in input().split(' ')]
    B.sort()
    k = n - n // 4
    (sA, sB) = (sum(A[n - k:]), sum(B[n - k:]))
    suffixA = [0] * n
    suffixA[-1] = A[-1]
    for i in range(n - 2, -1, -1):
        suffixA[i] = suffixA[i + 1] + A[i]
    suffixB = [0] * n
    suffixB[-1] = B[-1]
    for i in range(n - 2, -1, -1):
        suffixB[i] = suffixB[i + 1] + B[i]
    if sA >= sB:
        print(0)
    else:
        (l, h) = (0, 10 ** 7)
        while l < h:
            m = (l + h) // 2
            if check(suffixA, suffixB, m):
                h = m
            else:
                l = m + 1
        print(l if check(suffixA, suffixB, l) else h)

Solution (Python):
import os
import sys
import time
from io import BytesIO, IOBase
from heapq import *

def main():
    t = i_input()
    for tt in range(t):
        n = i_input()
        a = li_input()
        b = li_input()
        sa = sum(a)
        sb = sum(b)
        a.sort()
        b.sort()
        (pa, pb) = (0, 0)
        l = n
        for i in range(l // 4):
            sa -= a[pa]
            sb -= b[pb]
            pa += 1
            pb += 1
        if sa >= sb:
            print(0)
            continue
        pb -= 1
        while True:
            l += 1
            sa += 100
            if not l % 4:
                sa -= a[pa]
                pa += 1
            elif pb >= 0:
                sb += b[pb]
                pb -= 1
            if sa >= sb:
                break
        print(l - n)
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = 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(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))

def input():
    return sys.stdin.readline().rstrip('\r\n')

def i_input():
    return int(input())

def l_input():
    return input().split()

def li_input():
    return list(map(int, l_input()))

def il_input():
    return list(map(int, l_input()))
if __name__ == '__main__':
    TT = time.time()
    main()