HackerRank Fighting Pits problem solution

In this HackerRank Fighting Pits problem solution, Meereen is famous for its fighting pits where fighters fight each other to the death.

Initially, there are n fighters and each fighter has a strength value. The n fighters are divided into k teams, and each fighter belongs exactly one team. For each fight, the Great Masters of Meereen choose two teams, x and y, that must fight each other to the death. The teams attack each other in alternating turns, with team x always launching the first attack. The fight ends when all the fighters on one of the teams are dead.

Assume each team always attacks optimally. Each attack is performed as follows:

The attacking team chooses a fighter from their team with strength s.
The chosen fighter chooses at most s fighters from other team and kills all of them.
The Great Masters don’t want to see their favorite fighters fall in battle, so they want to build their teams carefully and know who will win different team matchups. They want you to perform two type of queries:

1 p x Add a new fighter with strength p to team x. It is guaranteed that this new fighter’s strength value will not be less than any current member of team x.
2 x y Print the name of the team that would win a matchup between teams x and y in their current state (recall that team x always starts first). It is guaranteed that x != y.
Given the initial configuration of the teams and q queries, perform each query so the Great Masters can plan the next fight.

Note: You are determining the team that would be the winner if the two teams fought. No fighters are actually dying in these matchups so, once added to a team, a fighter is available for all future potential matchups.

HackerRank Fighting Pits 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()

Fighting Pits 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;
}