Collecting Game (Codeforces 1904B)
Tags: Greedy, two pointers

You are given an array $$$a$$$ of $$$n$$$ positive integers and a score. If your score is greater than or equal to $$$a_i$$$, then you can increase your score by $$$a_i$$$ and remove $$$a_i$$$ from the array. For each index $$$i$$$, output the maximum number of additional array elements that you can remove if you remove $$$a_i$$$ and then set your score to $$$a_i$$$. Note that the removal of $$$a_i$$$ should not be counted in the answer.

Input: Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 5000$$$) — the number of test cases. The 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 length of the array.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the elements of the array.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output: For each test case, output $$$n$$$ integers, the $$$i$$$-th of which denotes the maximum number of additional array elements that you can remove if you remove $$$a_i$$$ from the array and then set your score to $$$a_i$$$.

Note: In the first test case, the answers are as follows:If we start with $$$i=4$$$, our initial score is $$$a_4=4$$$ and $$$a=[20,5,1,2]$$$. We can remove $$$3$$$ additional elements in the following order:   Since $$$4 \ge 1$$$, we can remove $$$1$$$ and our score becomes $$$5$$$. After this, $$$a=[20,5,2]$$$.  Since $$$5 \ge 5$$$, we can remove $$$5$$$ and our score becomes $$$10$$$. After this, $$$a=[20,2]$$$.  Since $$$10 \ge 2$$$, we can remove $$$2$$$ and our score becomes $$$12$$$. After this, $$$a=[20]$$$. If we start with $$$i=1$$$ we can remove all remaining elements in the array, so the answer is $$$4$$$.If we start with $$$i=2$$$, we can remove $$$3$$$ additional elements in the following order: $$$1$$$, $$$4$$$, $$$2$$$.If we start with $$$i=3$$$, we can remove no additional elements.If we start with $$$i=5$$$, we can remove $$$1$$$ additional element: $$$1$$$.

Sample Inputs:
4
5
20 5 1 4 2
3
1434 7 1442
1
1
5
999999999 999999999 999999999 1000000000 1000000000

Sample Outputs:
4 3 0 3 1 
1 0 2 
0 
4 4 4 4 4

Solution (Python):
from itertools import accumulate
n = int(input())

def argsort(seq):
    return sorted(range(len(seq)), key=seq.__getitem__)
for i in range(n):
    _ = input()
    numbers = list(map(int, input().split(' ')))
    numbers_argsort = argsort(numbers)[::-1]
    numbers = sorted(numbers, reverse=True)
    cumsum = list(accumulate(numbers[::-1]))[::-1]
    res = [0] * len(numbers)
    res[numbers_argsort[0]] = len(numbers) - 1
    for j in range(1, len(numbers)):
        if cumsum[j] < numbers[j - 1]:
            res[numbers_argsort[j]] = len(numbers) - j - 1
        else:
            res[numbers_argsort[j]] = res[numbers_argsort[j - 1]]
    print(' '.join(list(map(str, res))))

Solution (Python):
def main():
    t = int(input())
    for i in range(t):
        n = int(input())
        a = list(map(int, input().split()))
        testcase(n, a)

def testcase(n, a):
    res = [0 for i in range(n)]
    sorted_a = sorted(enumerate(a), key=lambda x: x[1])
    value = 0
    count = 0
    last_found = 0
    counts = []
    values = []
    for (idx, val) in sorted_a:
        if val > value:
            counts.extend([count - 1 for i in range(count - last_found)])
            last_found = count
        value += val
        count += 1
    counts.extend([n - 1 for i in range(n - last_found)])
    for (i, count) in enumerate(counts):
        res[sorted_a[i][0]] = count
    print(' '.join(map(str, res)))
main()

Solution (Python):
import sys
from math import *
input = sys.stdin.readline

def inp():
    return int(input())

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

def insr():
    s = input()
    return list(s[:len(s) - 1])

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

def solve(test):
    dp = {}
    prefix = []
    acc = 0
    sorted_list = sorted(test)
    for i in sorted_list:
        if len(prefix) == 0:
            prefix.append(i)
        else:
            prefix.append(prefix[-1] + i)
    for i in range(len(sorted_list) - 1, -1, -1):
        if i == len(sorted_list) - 1:
            dp[sorted_list[i]] = len(sorted_list) - 1
        else:
            pre = prefix[i]
            val = sorted_list[i]
            nxt = sorted_list[i + 1]
            if pre >= nxt:
                dp[val] = dp[nxt]
            else:
                dp[val] = i
    ret = []
    for i in test:
        ret.append(dp[i])
    return ' '.join(map(str, ret))
if __name__ == '__main__':
    tests = []
    num_tests = inp()
    for i in range(num_tests):
        n = inp()
        tests.append(inlt())
        continue
    for test in tests:
        print(solve(test))