Yet Another Tournament (Codeforces 1783C)
Tags: Greedy, sortings

You are participating in Yet Another Tournament. There are $$$n + 1$$$ participants: you and $$$n$$$ other opponents, numbered from $$$1$$$ to $$$n$$$.Each two participants will play against each other exactly once. If the opponent $$$i$$$ plays against the opponent $$$j$$$, he wins if and only if $$$i > j$$$.When the opponent $$$i$$$ plays against you, everything becomes a little bit complicated. In order to get a win against opponent $$$i$$$, you need to prepare for the match for at least $$$a_i$$$ minutes — otherwise, you lose to that opponent.You have $$$m$$$ minutes in total to prepare for matches, but you can prepare for only one match at one moment. In other words, if you want to win against opponents $$$p_1, p_2, \dots, p_k$$$, you need to spend $$$a_{p_1} + a_{p_2} + \dots + a_{p_k}$$$ minutes for preparation — and if this number is greater than $$$m$$$, you cannot achieve a win against all of these opponents at the same time.The final place of each contestant is equal to the number of contestants with strictly more wins $$$+$$$ $$$1$$$. For example, if $$$3$$$ contestants have $$$5$$$ wins each, $$$1$$$ contestant has $$$3$$$ wins and $$$2$$$ contestants have $$$1$$$ win each, then the first $$$3$$$ participants will get the $$$1$$$-st place, the fourth one gets the $$$4$$$-th place and two last ones get the $$$5$$$-th place.Calculate the minimum possible place (lower is better) you can achieve if you can't prepare for the matches more than $$$m$$$ minutes in total.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 5 \cdot 10^5$$$; $$$0 \le m \le \sum\limits_{i=1}^{n}{a_i}$$$) — the number of your opponents and the total time you have for preparation.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 1000$$$), where $$$a_i$$$ is the time you need to prepare in order to win against the $$$i$$$-th opponent.It's guaranteed that the total sum of $$$n$$$ over all test cases doesn't exceed $$$5 \cdot 10^5$$$.

Output: For each test case, print the minimum possible place you can take if you can prepare for the matches no more than $$$m$$$ minutes in total.

Note: In the first test case, you can prepare to all opponents, so you'll win $$$4$$$ games and get the $$$1$$$-st place, since all your opponents win no more than $$$3$$$ games.In the second test case, you can prepare against the second opponent and win. As a result, you'll have $$$1$$$ win, opponent $$$1$$$ — $$$1$$$ win, opponent $$$2$$$ — $$$1$$$ win, opponent $$$3$$$ — $$$3$$$ wins. So, opponent $$$3$$$ will take the $$$1$$$-st place, and all other participants, including you, get the $$$2$$$-nd place.In the third test case, you have no time to prepare at all, so you'll lose all games. Since each opponent has at least $$$1$$$ win, you'll take the last place (place $$$6$$$).In the fourth test case, you have no time to prepare, but you can still win against the first opponent. As a result, opponent $$$1$$$ has no wins, you have $$$1$$$ win and all others have at least $$$2$$$ wins. So your place is $$$4$$$.

Sample Inputs:
5
4 401
100 100 200 1
3 2
1 2 3
5 0
1 1 1 1 1
4 0
0 1 1 1
4 4
1 2 2 1

Sample Outputs:
1
2
6
4
1

Solution (Python):
def solve(N, M, arr):
    arr_sorted = sorted(arr)
    _sum = 0
    for (idx, a) in enumerate(arr_sorted + [0]):
        _sum += a
        if _sum > M:
            break
    if idx == 0:
        return N + 1
    elif idx == N:
        return 1
    _sum = sum(arr_sorted[:idx])
    tmp = arr_sorted[idx - 1]
    if _sum - tmp + arr[idx] <= M:
        return N - idx
    else:
        return N - idx + 1
T = int(input())
for _ in range(T):
    (N, M) = list(map(int, input().split()))
    arr = list(map(int, input().split()))
    ans = solve(N, M, arr)
    print(ans)

Solution (Python):
ress = []

def solve(n, m, a):
    b = sorted(a)
    wins = 0
    for x in b:
        if x > m:
            break
        wins += 1
        m -= x
    res = n - wins + 1
    if 0 < wins < n:
        if m + b[wins - 1] - a[wins] >= 0:
            res -= 1
    return res
for _ in range(int(input())):
    (n, m) = map(int, input().split())
    a = list(map(int, input().split()))
    print(solve(n, m, a))

Solution (Python):
for _ in range(int(input())):
    (n, k) = list(map(int, input().split()))
    l = list(map(int, input().split()))
    l1 = sorted(l)
    sm = 0
    for x in range(n):
        sm += l1[x]
        if sm > k:
            if x != 0:
                sm -= l1[x] + l1[x - 1]
            sm += l[x]
            break
    if sm <= k:
        print(n - x)
    else:
        print(n - x + 1)