Skip to content
Programming101
Programming101

Learn everything about programming

  • Home
  • CS Subjects
    • IoT – Internet of Things
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programming101
Programming101

Learn everything about programming

HackerRank Fighting Pits problem solution

YASH PAL, 31 July 2024

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.

hackerrank fighting pits problem solution

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()

{“mode”:”full”,”isActive”:false}

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();
    }
}

{“mode”:”full”,”isActive”:false}

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

{“mode”:”full”,”isActive”:false}

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

{“mode”:”full”,”isActive”:false}

algorithm coding problems

Post navigation

Previous post
Next post
  • How AI Is Revolutionizing Personalized Learning in Schools
  • GTA 5 is the Game of the Year for 2024 and 2025
  • Hackerrank Day 5 loops 30 days of code solution
  • Hackerrank Day 6 Lets Review 30 days of code solution
  • Hackerrank Day 14 scope 30 days of code solution
©2025 Programming101 | WordPress Theme by SuperbThemes