Elections
Source: codechef
Difficulty: 1133

Elections
Two candidates,$A$and$B$, are contesting an election across$N$states (where$N$is
odd
). A candidate wins in a state if they receive more votes than their opponent. The candidate who wins in more than half of the states, wins the election.
In the$i^{th}$state, candidate$A$has received$A_i$votes and candidate$B$has received$B_i$votes.
Chef has the power to cast$X$votes, and he can distribute these votes between multiple states to help candidate$A$. Determine if these additional$X$votes could secure enough state victories for Candidate$A$to win the election.
Input Format
The first line of input will contain a single integer$T$, denoting the number of test cases.
Each test case consists of multiple lines of input.
The first line of each test case contains two space-separated integers$N$and$X$— the number of states and the number of votes Chef can cast.
The second line contains$N$space separated integers denoting the number of votes received by candidate$A$in each state.
The third line contains$N$space separated integers denoting the number of votes received by candidate$B$in each state.
Output Format
For each test case, output on a new line,
YES
, if candidate$A$can win the election with Chefs additional votes. Otherwise print
NO
.
You may print each character of the string in uppercase or lowercase (for example, the strings
YES
,
yEs
,
yes
, and
yeS
will all be treated as identical).
Constraints$1 \leq T \leq 6000$$1 \leq N \leq 10^5, \ N$is odd.$1 \leq X \leq 10^8$$1 \leq A_i, B_i \leq 1000$The sum of$N$over all test cases won't exceed$2\cdot 10^5$.
Sample 1:
Explanation:
Test case$1$:
Even after Chef's vote, both candidates would have equal number of votes, and thus candidate$A$would not be the winner.
Test case$2$:
Candidate$A$is already winning in$2$out of$3$states and thus, is the winner of the election.
Test case$3$:
Chef can cast one vote in state$1$and remaining$2$votes in state$2$. Thus, candidate$A$would win in states$1$and$2$and win the election.

Sample Input:
3
1 1
2
3
3 2
2 2 3
1 3 2
3 3
3 1 5
3 2 7

Sample Output:
NO
YES
YES

C++ solution:
#include <stdio.h>
#include <stdlib.h>

// Comparison function for qsort
int cmp(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

int main() {
    int T;
    scanf("%d", &T);
    
    while (T--) {
        int N;
        long long X;
        scanf("%d %lld", &N, &X);
        
        int *A = (int *)malloc(N * sizeof(int));
        int *B = (int *)malloc(N * sizeof(int));
        
        for (int i = 0; i < N; i++) {
            scanf("%d", &A[i]);
        }
        for (int i = 0; i < N; i++) {
            scanf("%d", &B[i]);
        }
        
        // Count the number of states that candidate A is already winning.
        int wins = 0;
        // This array will hold the extra votes needed for states where A isn't winning.
        int *cost = (int *)malloc(N * sizeof(int));
        int costCount = 0;
        
        for (int i = 0; i < N; i++) {
            if (A[i] > B[i]) {
                wins++;
            } else {
                // Candidate A requires (B[i] - A[i] + 1) votes to win this state.
                cost[costCount++] = (B[i] - A[i] + 1);
            }
        }
        
        // To win overall, candidate A must win more than half the states.
        int winGoal = (N + 1) / 2;
        
        if (wins >= winGoal) {
            printf("YES\n");
        } else {
            // Sort the required extra votes in non-decreasing order.
            qsort(cost, costCount, sizeof(int), cmp);
            
            // Determine how many additional states we need to flip.
            int needed = winGoal - wins;
            
            for (int i = 0; i < costCount && needed > 0; i++) {
                if (X >= cost[i]) {
                    X -= cost[i];
                    needed--;
                }
            }
            
            if (needed == 0) {
                printf("YES\n");
            } else {
                printf("NO\n");
            }
        }
        
        // Free allocated memory
        free(A);
        free(B);
        free(cost);
    }
    
    return 0;
}

Go solution:
package main

import (
    "bufio"
    "fmt"
    "os"
    "sort"
    "strconv"
    "strings"
)

func main() {
    reader := bufio.NewReader(os.Stdin)
    writer := bufio.NewWriter(os.Stdout)
    defer writer.Flush()
    
    // Read number of test cases
    tStr, _ := reader.ReadString('\n')
    testCases, _ := strconv.Atoi(strings.TrimSpace(tStr))

    for t := 0; t < testCases; t++ {
        // Read statesCount (N) and extraVotes (X)
        firstLine, _ := reader.ReadString('\n')
        firstLineSplit := strings.Fields(firstLine)
        statesCount, _ := strconv.Atoi(firstLineSplit[0])
        extraVotes, _ := strconv.Atoi(firstLineSplit[1])

        // Read votes for candidateA in each state
        aVotesLine, _ := reader.ReadString('\n')
        candidateAVotes := make([]int, statesCount)
        for i, v := range strings.Fields(aVotesLine) {
            candidateAVotes[i], _ = strconv.Atoi(v)
        }

        // Read votes for candidateB in each state
        bVotesLine, _ := reader.ReadString('\n')
        candidateBVotes := make([]int, statesCount)
        for i, v := range strings.Fields(bVotesLine) {
            candidateBVotes[i], _ = strconv.Atoi(v)
        }

        // Determine current state wins for candidateA
        requiredWins := (statesCount / 2) + 1
        currentWinsA := 0
        neededVoteDiffs := []int{}

        for i := 0; i < statesCount; i++ {
            if candidateAVotes[i] > candidateBVotes[i] {
                currentWinsA++
            } else {
                // Calculate votes needed for candidateA to win this state
                neededVoteDiffs = append(neededVoteDiffs, candidateBVotes[i] - candidateAVotes[i] + 1)
            }
        }

        // Check if candidateA is already winning
        if currentWinsA >= requiredWins {
            fmt.Fprintln(writer, "YES")
            continue
        }

        // Sort vote differences in ascending order to use the smallest first
        sort.Ints(neededVoteDiffs)

        // Try to use extraVotes to secure additional wins for candidateA
        for _, votesNeeded := range neededVoteDiffs {
            if extraVotes >= votesNeeded {
                extraVotes -= votesNeeded
                currentWinsA++
                if currentWinsA >= requiredWins {
                    fmt.Fprintln(writer, "YES")
                    break
                }
            } else {
                break
            }
        }

        // If unable to secure enough wins
        if currentWinsA < requiredWins {
            fmt.Fprintln(writer, "NO")
        }
    }
}

Java solution:
import java.util.*;
import java.lang.*;
import java.io.*;

class Codechef
{
    public static void main (String[] args) throws java.lang.Exception
    {
        // your code goes here
//      Scanner kb=new Scanner(System.in);
//  
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
            int t=Integer.parseInt(br.readLine());
        while(t-->0){
             StringTokenizer st=new StringTokenizer(br.readLine());
            int n=Integer.parseInt(st.nextToken());
            long x=Long.parseLong(st.nextToken());
            int []voteA=new int[n];
            int []voteB=new int[n];
             st=new StringTokenizer(br.readLine());
            for(int i=0;i<n;i++){
                voteA[i]=Integer.parseInt(st.nextToken());
            }
            st=new StringTokenizer(br.readLine());
             for(int i=0;i<n;i++){
                voteB[i]=Integer.parseInt(st.nextToken());
            }
            int seatwinA=0;
            List<Integer> list=new ArrayList<>();
            for(int i=0;i<n;i++){
                  if(voteA[i]>voteB[i]) 
                  seatwinA++;
                  else
                  list.add(voteB[i]-voteA[i]);
            }
             int count=0;
            if(seatwinA<n/2 +1){
                Collections.sort(list);
           
            for(int k:list){
                if(x>=k+1){
                    x=x-k-1;
                    count++;
                }
                if(x==0)
                break;
            } 
            }
           
            
            System.out.println((seatwinA+count)>(n/2)?"YES":"NO");
        }
        

    }
}

JavaScript solution:
const readline = require("readline");

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

function solveTestCase(N, X, A_votes, B_votes) {
    const requiredWins = Math.floor(N / 2) + 1;
    let currentWins = 0;
    let additionalVotesNeeded = [];

    // Determine states A is already winning and where Chef's votes might help
    for (let i = 0; i < N; i++) {
        if (A_votes[i] > B_votes[i]) {
            currentWins++;
        } else {
            // Calculate minimum votes needed for A to win in this state
            additionalVotesNeeded.push(B_votes[i] - A_votes[i] + 1);
        }
    }

    // If A already has the majority of wins
    if (currentWins >= requiredWins) {
        return "YES";
    }

    // Sort votes needed in ascending order to try the smallest ones first
    additionalVotesNeeded.sort((a, b) => a - b);

    // Use Chef's votes to convert states to A's favor
    for (let i = 0; i < additionalVotesNeeded.length && X >= additionalVotesNeeded[i]; i++) {
        X -= additionalVotesNeeded[i];
        currentWins++;

        if (currentWins >= requiredWins) {
            return "YES";
        }
    }

    return "NO";
}

let inputLines = [];
let currentLine = 0;

rl.on("line", (line) => {
    inputLines.push(line.trim());
});

rl.on("close", () => {
    const T = parseInt(inputLines[currentLine++], 10);
    const results = [];

    for (let t = 0; t < T; t++) {
        const [N, X] = inputLines[currentLine++].split(" ").map(Number);
        const A_votes = inputLines[currentLine++].split(" ").map(Number);
        const B_votes = inputLines[currentLine++].split(" ").map(Number);

        results.push(solveTestCase(N, X, A_votes, B_votes));
    }

    console.log(results.join("\n"));
});

Python solution:
def can_win_election(N, X, A, B):
    wins = sum(1 for i in range(N) if A[i] > B[i])  # States where A is already winning
    deficits = []  # List to track votes needed in losing states
    
    for i in range(N):
        if A[i] <= B[i]:
            deficits.append(B[i] - A[i] + 1)  # Votes needed to flip the state
    
    deficits.sort()  # Sort to prioritize states that need fewer votes
    
    for votes_needed in deficits:
        if wins > N // 2:  # If A has already secured majority, stop
            return "YES"
        if X >= votes_needed:
            X -= votes_needed
            wins += 1
        else:
            break
    
    return "YES" if wins > N // 2 else "NO"

def main():
    T = int(input())
    results = []
    
    for _ in range(T):
        N, X = map(int, input().split())
        A = list(map(int, input().split()))
        B = list(map(int, input().split()))
        results.append(can_win_election(N, X, A, B))
    
    print("\n".join(results))

if __name__ == "__main__":
    main()

Ruby solution:
def main
  input = $stdin.readlines.map(&:chomp)
  ptr = 0
  test_cases = input[ptr].to_i
  ptr += 1

  test_cases.times do
    n, x = input[ptr].split.map(&:to_i)
    ptr += 1
    a = input[ptr].split.map(&:to_i)
    ptr += 1
    b = input[ptr].split.map(&:to_i)
    ptr += 1

    required_wins = (n + 1) / 2
    current_wins = 0
    needed_votes = []

    n.times do |i|
      if a[i] > b[i]
        current_wins += 1
      else
        needed_votes << (b[i] - a[i] + 1)
      end
    end

    if current_wins >= required_wins
      puts "YES"
      next
    end

    needed_votes.sort!

    needed_votes.each do |votes|
      if votes <= x
        x -= votes
        current_wins += 1
        if current_wins >= required_wins
          puts "YES"
          break
        end
      end
    end

    puts "NO" if current_wins < required_wins
  end
end

main