# 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

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]

"""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 = {}

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

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

num_matches = defaultdict(int)
queries = []
for q in range(Q):
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
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<>();

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

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()) {
} else {
}
} 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));
System.in
//            new FileInputStream("/home/malik/Ð—Ð°Ð³Ñ€ÑƒÐ·ÐºÐ¸/input04.txt")
));

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 fightersRowItr = 0; fightersRowItr < n; fightersRowItr++) {
}

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

for (int queriesRowItr = 0; queriesRowItr < q; queriesRowItr++) {

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

fightingPits(k, teams, queries, writer);

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("%d\n",q2[i]);
break;
}
k-=team[q2[i]-1][j-1];
if(k<=0)
printf("%d\n",q2[i]);
}
else{
if(team_s[q2[i]-1][j-1]<=team_s[q3[i]-1][k-1]){
printf("%d\n",q3[i]);
break;
}
j-=team[q3[i]-1][k-1];
if(j<=0)
printf("%d\n",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}