HackerRank Fighting Pits problem solution

In this HackerRank Fighting Pits problem solution Given the initial configuration of the teams and Q queries, perform each query so the Great Masters can plan the next fight.

Problem solution in Python.

from collections import defaultdict

def readints():
    return [int(x) for x in input().strip().split()]


class Team():
    def __init__(self, id, strengths):
        self.id = id
        self.strengths = sorted(strengths)
        self._beatable_sizes = defaultdict(lambda: [self.strengths[0]])
        self._least_winning_index = defaultdict(int)
        self.N = len(self.strengths)
        self.sum = sum(self.strengths)

    def __len__(self):
        return len(self.strengths)

    def __getitem__(self, idx):
        return self.strengths[idx]

    def add(self, strength):
        """Add a new fighter to the team.

        The new fighter is assumed to have strength no less than the
        most powerful fighter already on the team.
        """
        assert not self.strengths or strength >= self.strengths[-1]
        self.N += 1
        self.sum += strength
        self.strengths.append(strength)

    def simulate_fight(self, opponent, memoize=False):
        """Returns winner id for simulated fight."""
        return self.id if self.can_beat(opponent, memoize) else opponent.id

    def can_beat(self, opponent, memoize):
        """Return True if this team can beat the opponent, False otherwise."""
        if memoize:
            return self.beatable_size(opponent) >= opponent.N
        else:
            i_self = self.N - 1
            i_opponent = opponent.N - 1
            while i_self >= 0:
                i_opponent -= self[i_self]
                if i_opponent < 0:
                    return True
                i_self -= opponent[i_opponent]
            return False

    def beatable_size(self, opponent):
        bs = self._beatable_sizes[opponent]
        lwi = self._least_winning_index
        for i in range(len(bs), self.N):
            for lwi[opponent] in range(lwi[opponent], opponent.N):
                idx = i - opponent[lwi[opponent]]
                if idx < 0 or lwi[opponent] >= bs[idx]:
                    break
            else:
                # No enemy subteam can beat this subteam
                return opponent.N
            bs.append(lwi[opponent] + self[i])
        return bs[-1]


def main():
    team = {}

    N, K, Q = readints()
    for n in range(N):
        s, t = readints()
        team.setdefault(t, []).append(s)

    for k, v in team.items():
        t = Team(k, team[k])
        team[k] = t

    # Read Queries
    num_matches = defaultdict(int)
    queries = []
    for q in range(Q):
        qt, *args = readints()
        if qt == 2:
            key = frozenset(args)
            num_matches[key] += 1
            args += [key] 
        queries.append((qt, args))

    memoize_set = set(k for k, v in num_matches.items() if v >= 1000)
    for qt, args in queries:
        if qt == 1:
            p, x = args
            team.setdefault(x, Team(x, [])).add(p)
        else:
            x, y, key = args
            print(team[x].simulate_fight(team[y], key in memoize_set))


if __name__ == '__main__':
    main()

Problem solution in Java.

import java.io.*;
import java.util.*;
import java.util.stream.Collectors;

public class Solution {

    static class Team {
        int sum = 0;
        final List<Integer> p = new ArrayList<>();

        void add(int power) {
            p.add(power);
            sum += power;
        }

        int member(int i) {
            return p.get(i);
        }

        int members() {
            return p.size();
        }

        void opt() {
            p.sort(Integer::compareTo);
        }
    }

    /*
     * Complete the fightingPits function below.
     */
    static void fightingPits(int k, List<List<Integer>> teams, int[][] queries, BufferedWriter writer) throws IOException {

        List<List<Integer>> powers = teams.stream().map(
            t -> {
                t.sort(Integer::compareTo);

                List<Integer> res = new ArrayList<>();
                int acc = 0;
                for (int p : t) {
                    acc += p;
                    res.add(acc);
                }

                return res;
            }
        ).collect(Collectors.toList());

        for (int[] q : queries) {
            if (q[0] == 1) {
                int tI = q[2] - 1;
                List<Integer> p = powers.get(tI);
                if (p.isEmpty()) {
                    p.add(q[1]);
                } else {
                    p.add(p.get(p.size() - 1) + q[1]);
                }
            } else {
                int xI = q[1] - 1, yI = q[2] - 1;
                final List<Integer> x = powers.get(xI);
                final List<Integer> y = powers.get(yI);

                int xJ = x.size() - 1, yJ = y.size() - 1;
                int winner;
                while (true) {
                    if (x.get(xJ) >= y.get(yJ)) {
                        winner = xI + 1;
                        break;
                    }
                    yJ -= x.get(xJ) - (xJ < 1 ? 0 : x.get(xJ - 1));
                    if (yJ < 0) {
                        winner = xI + 1;
                        break;
                    }
                    if (x.get(xJ) <= y.get(yJ)) {
                        winner = yI + 1;
                        break;
                    }
                    xJ -= y.get(yJ) - (yJ < 1 ? 0 : y.get(yJ - 1));
                    if (xJ < 0) {
                        winner = yI + 1;
                        break;
                    }
                }
                writer.write(String.valueOf(winner));
                writer.newLine();
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader reader = new BufferedReader(new InputStreamReader(
            System.in
//            new FileInputStream("/home/malik/Загрузки/input04.txt")
        ));

        String[] nkq = reader.readLine().split(" ");

        int n = Integer.parseInt(nkq[0].trim());

        int k = Integer.parseInt(nkq[1].trim());

        int q = Integer.parseInt(nkq[2].trim());

        List<List<Integer>> teams = new ArrayList<>(k);

        for (int i = 0; i < k; i++) teams.add(new LinkedList<>());

        for (int fightersRowItr = 0; fightersRowItr < n; fightersRowItr++) {
            String[] fightersRowItems = reader.readLine().split(" ");
            teams.get(Integer.parseInt(fightersRowItems[1]) - 1).add(Integer.parseInt(fightersRowItems[0]));
        }

        int[][] queries = new int[q][3];

        for (int queriesRowItr = 0; queriesRowItr < q; queriesRowItr++) {
            String[] queriesRowItems = reader.readLine().split(" ");

            for (int queriesColumnItr = 0; queriesColumnItr < 3; queriesColumnItr++) {
                int queriesItem = Integer.parseInt(queriesRowItems[queriesColumnItr].trim());
                queries[queriesRowItr][queriesColumnItr] = queriesItem;
            }
        }

        fightingPits(k, teams, queries, writer);

        reader.close();
        writer.close();
    }
}

Problem solution in C++.

#include <cmath>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int binary(vector<int> &l, int val) {
    int lo = 0;
    int hi = l.size();
    int mid;
    while (lo < hi) {
        mid = (lo + hi) / 2;
        if (l[mid] == val)
            return mid;
        if (l[mid] > val)
            hi = mid;
        else
            lo = mid + 1;
    }
    return lo;
}

int find_winner(int x, int y, vector<vector<int>> &l, unsigned long long x_sum, unsigned long long y_sum) {
    vector<int> &X = l[x];
    vector<int> &Y = l[y];
    int x_count = X.size() - 1;
    int y_count = Y.size() - 1;
    bool chance = true;
    while (true) {
        if (chance) {
            if (x_sum >= y_sum)
                return x;
            y_count -= X[x_count];
            if (y_count < 0)
                return x;
            for(int i = y_count + 1; i <= y_count + X[x_count]; i++) {
                y_sum -= Y[i];
            }
        } else {
            if (y_sum >= x_sum)
                return y;
            x_count -= Y[y_count];
            if (x_count < 0)
                return y;
            for (int i = x_count + 1; i <= x_count + Y[y_count]; i++) {
                x_sum -= X[i];
            }
        }

        chance = !chance;
    }
}

int main() {
    int n, k, q;
    cin >> n >> k >> q;

    vector<vector<int>> l;
    for (int i = 0; i <= k; i++) {
        vector<int> cur;
        l.push_back(cur);
    }

    vector<unsigned long long> sums;
    for (int i = 0; i <= k; i++) {
        sums.push_back(0);
    }

    int s, t;
    for (int i = 0; i < n; i++) {
        cin >> s >> t;
        l[t].push_back(s);
        sums[t] += s;
    }

    for (int i = 1; i <= k; i++) {
        sort(l[i].begin(), l[i].end());
    }

    for (int i = 1; i <= q; i++) {
        int x, y;
        cin >> t >> x >> y;
        if (t == 1) {
            l[y].insert(l[y].begin() + binary(l[y], x), x);
            sums[y] += x;
        } else {
            cout << find_winner(x, y, l, sums[x], sums[y]) << endl;
        }
    }
    return 0;
}

Problem solution in C.

#include <stdio.h>
#include <stdlib.h>
void sort_a(int*a,int size);
void merge(int*a,int*left,int*right,int left_size, int right_size);
int s[200000],t[200000],q1[200000],q2[200000],q3[200000],team_size[200000]={0},*team[200000];
long long *team_s[200000];

int main(){
  int n,k,q,turn,i,j;
  scanf("%d%d%d",&n,&k,&q);
  for(i=0;i<n;i++){
    scanf("%d%d",s+i,t+i);
    team_size[t[i]-1]++;
  }
  for(i=0;i<q;i++){
    scanf("%d%d%d",q1+i,q2+i,q3+i);
    if(q1[i]==1)
      team_size[q3[i]-1]++;
  }
  for(i=0;i<k;i++){
    team[i]=(int*)malloc(team_size[i]*sizeof(int));
    team_s[i]=(long long*)malloc(team_size[i]*sizeof(long long));
    team_size[i]=0;
  }
  for(i=0;i<n;i++)
    team[t[i]-1][team_size[t[i]-1]++]=s[i];
  for(i=0;i<k;i++){
    sort_a(team[i],team_size[i]);
    for(j=0;j<team_size[i];j++)
      if(j)
        team_s[i][j]=team_s[i][j-1]+team[i][j];
      else
        team_s[i][j]=team[i][j];
  }
  for(i=0;i<q;i++)
    if(q1[i]==1){
      team[q3[i]-1][team_size[q3[i]-1]]=q2[i];
      if(team_size[q3[i]-1])
        team_s[q3[i]-1][team_size[q3[i]-1]]=team_s[q3[i]-1][team_size[q3[i]-1]-1]+team[q3[i]-1][team_size[q3[i]-1]];
      else
        team_s[q3[i]-1][team_size[q3[i]-1]]=team[q3[i]-1][team_size[q3[i]-1]];
      team_size[q3[i]-1]++;
    }
    else{
      j=team_size[q2[i]-1];
      k=team_size[q3[i]-1];
      turn=0;
      while(j>0 && k>0){
        if(!turn){
          if(team_s[q2[i]-1][j-1]>=team_s[q3[i]-1][k-1]){
            printf("%dn",q2[i]);
            break;
          }
          k-=team[q2[i]-1][j-1];
          if(k<=0)
            printf("%dn",q2[i]);
        }
        else{
          if(team_s[q2[i]-1][j-1]<=team_s[q3[i]-1][k-1]){
            printf("%dn",q3[i]);
            break;
          }
          j-=team[q3[i]-1][k-1];
          if(j<=0)
            printf("%dn",q3[i]);
        }
        if(j<0 || k<0)
          break;
        turn^=1;
      }
    }
  return 0;
}
void sort_a(int*a,int size){
  if (size < 2)
    return;
  int m = (size+1)/2,i;
  int *left,*right;
  left=(int*)malloc(m*sizeof(int));
  right=(int*)malloc((size-m)*sizeof(int));
  for(i=0;i<m;i++)
    left[i]=a[i];
  for(i=0;i<size-m;i++)
    right[i]=a[i+m];
  sort_a(left,m);
  sort_a(right,size-m);
  merge(a,left,right,m,size-m);
  free(left);
  free(right);
  return;
}
void merge(int*a,int*left,int*right,int left_size, int right_size){
    int i = 0, j = 0;
    while (i < left_size|| j < right_size) {
        if (i == left_size) {
            a[i+j] = right[j];
            j++;
        } else if (j == right_size) {
            a[i+j] = left[i];
            i++;
        } else if (left[i] <= right[j]) {
            a[i+j] = left[i];
            i++;                
        } else {
            a[i+j] = right[j];
            j++;
        }
    }
    return;
}