USELEC - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: notsoloud
Tester: mexomerf
Editorialist: iceknight1093

DIFFICULTY:

cakewalk

PREREQUISITES:

Sorting

PROBLEM:

In an election across N states, candidate A received A_i votes in the i-th state, while candidate B received B_i votes in the i-th state.

A candidate wins the state if they have strictly more votes than their competitor.
A candidate wins the election if they win strictly more than half the N states.

Chef has X votes, which he can distribute as he likes to any of the N states.
Can he make candidate A win the election?

EXPLANATION:

Chef wants to make candidate A win, so ideally he should make A win as many states as possible.
For the i-th state,

  • If A_i \gt B_i, this state is already won by candidate A, and Chef doesn’t need to do anything.
  • If A_i \leq B_i, Chef needs to provide B_i - A_i + 1 votes to candidate A to make him win it.

Since all the states are equivalent in terms of winning them, Chef can simply gives votes to the state that needs the least, then the second-least, and so on - there’s no better strategy.

That is, compute the value C_i = \max(B_i - A_i + 1, 0) to be the number of votes that Chef needs to give to state i.
Sort the array C so that C_1 \leq C_2 \leq C_3 \leq\ldots\leq C_N, and then give votes in order of C_1, C_2, \ldots

If at any point Chef needs to give more votes than he has, stop immediately, since satisfying any further C_i values is impossible.
Count the number of states that successfully had votes given to them, and then check if this number is \gt \frac{N}{2} or not.

TIME COMPLEXITY:

\mathcal{O}(N\log N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n, x = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    c = [max(b[i] - a[i] + 1, 0) for i in range(n)]
    
    tot = 0
    for y in sorted(c):
        if y > x: break
        x -= y
        tot += 1
    print('Yes' if tot > n - tot else 'No')