HackerRank Fighting Pits Problem Solution

HackerRank Fighting Pits Problem Solution

Yashwant Parihar,

In this post, we will solve 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. Then fighters are divided into & teams, and each fighter belongs exactly one team. For each fight, the Great Masters of Meereen choose two teams, and y, that must fight each other to the death. The teams attack each other in alternating turns, with team 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: 1. The attacking team chooses a fighter from their team with strength 8. 2. 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. 1 p x Add a new fighter with strength p to team. It is guaranteed that this new fighter’s strength value will not be less than any current member of team…
    2.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 & always starts first). It is guaranteed that 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.
Input Format
The first line contains three space-separated integers describing the respective values of n (the number of fighters), k (the number of teams), and q (the number of queries). Each line & of the n subsequent lines contains two space-separated integers describing the respective values of fighter i’s strength, s. and team number, t,. Each of the q subsequent lines contains a space-separated query in one of the two formats defined in the Problem Statement above (l.e.. 1 p x or 2 x y).

Scoring
This challange has binary scoring. This means you will get a full score if your solution passes all test cases; otherwise, you will get 0 points.
Output Format
After each type 2 query, print the name of the winning team on a new line. For example, if = 1 and y = 2 are matched up and a wins, you would print 1.

Sample Input

7 2 6
1 1
2 1
1 1
1 2
1 2
1 2
2 2
2 1 2
2 2 1
1 2 1
1 2 1
2 1 2
2 2 1

Sample Output

1
2
1
1

Explanation
Team 1 has three fighters with the following strength levels: S₁ = {1,1,2}.
Team 2 has four fighters with the following strength levels: S₂ = {1, 1, 1, 2}.
The first query matching up team = 1 and y = 2 would play out as follows:

  1. Team = 1 attacks → The fighter with strength 2 can kill one fighter with strength 2 and one fighter with strength 1. Now, S₁ = {1,1,2}, and S₂ = {1, 1}.
  2. Team = 2 attacks → The fighter with strength 1 can kill the fighter with strength 2. Now, S₁ = {1, 1}, and S₂ = {1, 1}.
  3. Team = 1 attacks → The fighter with strength 1 can kill one fighter with strength 1. Now, S₁ = {1, 1}, and S₂ = {1}.
  4. Team = 2 attacks → The fighter with strength 1 can kill one fighter with strength 1. Now, S₁ = {1}, and S₂ = {1}.
  5. Team = 1 attacks → The fighter with strength 1 can kill the last fighter with strength
  6. Now, S₁ = {1}, and S₂ = {}
    After this last attack, all of Team 2’s fighters would be dead. Thus, we print 1 as team 1 would win that fight.
HackerRank Fighting Pits Problem Solution
HackerRank Fighting Pits Problem Solution

Fighting Pits C Solution

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

Fighting Pits C++ Solution

#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef pair < int, int > ii;

const int N = 2e5 + 5;

int n, k, m;
vector < ii > v[N];

int main () {

    scanf("%d %d %d", &n, &k, &m);

    vector < ii > vs;

    for(int i = 1; i <= n; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        vs.push_back({x, y});
    }

    sort(vs.begin(), vs.end());

    for(auto tmp : vs) {
        int x, y;
        tie(x, y) = tmp;
        int cnt = 1;
        if(v[y].size() and v[y].back().first == x)
            cnt += v[y].back().second;
        v[y].push_back({x, cnt});
    }

    for(int i = 1; i <= m; i++) {
        int c;
        scanf("%d", &c);
        assert(1 <= c and c <= 2);
        if(c == 1) {
            int x, y;
            scanf("%d %d", &x, &y);
            int cnt = 1;
            if(v[y].size() and v[y].back().first == x)
                cnt += v[y].back().second;
            v[y].push_back({x, cnt});
        }
        else {
            int x, y;
            scanf("%d %d", &x, &y);
            int i = v[x].size() - 1, j = v[y].size() - 1;
            while(i >= 0 and j >= 0) {
                {
                    //SQRT THING
                    int k = min((v[x][i].second - 1) / v[y][j].first, (v[y][j].second - 1) / v[x][i].first);
                    i -= k * v[y][j].first;
                    j -= k * v[x][i].first;
                }
                j -= v[x][i].first;
                if(j >= 0)
                    i -= v[y][j].first;
            }
            printf("%d\n", i >= 0 ? x : y);
        }
    }

    return 0;

}

Fighting Pits C Sharp Solution

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Text;
using System.Xml.Schema;

namespace HackerRanking
{
    class SolutionMereenFightingPits
    {
        public class RangeSum
        {
            readonly long[] tree;
            int n;
            public RangeSum(int[] nums)
            {
                if (nums.Length > 0)
                {
                    n = nums.Length;
                    tree = new long[n * 2];
                    buildTree(nums);
                }
            }
            private void buildTree(int[] nums)
            {
                for (int i = n, j = 0; i < 2 * n; i++, j++)
                    tree[i] = nums[j];
                for (int i = n - 1; i > 0; --i)
                    tree[i] = tree[i * 2] + tree[i * 2 + 1];
            }

            public void update(int pos, int val)
            {
                pos += n;
                tree[pos] = val;
                while (pos > 0)
                {
                    int left = pos;
                    int right = pos;
                    if (pos % 2 == 0)
                        right = pos + 1;
                    else
                        left = pos - 1;

                    // parent is updated after child is updated
                    tree[pos / 2] = tree[left] + tree[right];
                    pos /= 2;
                }
            }

            public long sumRange(int l, int r)
            {
                l += n;
                r += n;
                long sum = 0;
                while (l <= r)
                {
                    if ((l % 2) == 1)
                    {
                        sum += tree[l];
                        l++;
                    }
                    if ((r % 2) == 0)
                    {
                        sum += tree[r];
                        r--;
                    }
                    l /= 2;
                    r /= 2;
                }
                return sum;
            }

            public int find(long value, int startPos, int endPos)
            {
                var left = startPos;
                var right = endPos;
                while (left < right - 1)
                {
                    var mid = (left + right) >> 1;
                    var varlcp = sumRange(mid, endPos);
                    if (varlcp > value)
                        left = mid;
                    else
                        right = mid;
                }
                return right;
            }

            public static void Test()
            {
                int[] v = new int[] { -3, -1, -5, -10, -7, -3, -10, -10, -3, -7, -4, 0, -2, -2, 0, -9, -7, -4 };
                var st = new RangeSum(v);
                var t1 = st.sumRange(0, 4);
                int t = 0;
                Trace.Assert(t1 == v.Skip(0).Take(5).Sum());
                var t2 = st.sumRange(2, 4);
                Trace.Assert(t2 == v.Skip(2).Take(3).Sum());
                var t3 = st.sumRange(3, 7);
                Trace.Assert(t3 == v.Skip(3).Take(5).Sum());
                var t4 = st.sumRange(0, 8);
                Trace.Assert(t4 == v.Skip(0).Take(9).Sum());
            }

        }


        public static int lower_bound<T, K>(IList<T> seg, K value, Func<T, K> predFunc)
            where K : IComparable<K>
        {
            if (seg.Count == 0)
                return 0;

            if (predFunc(seg[seg.Count - 1]).CompareTo(value) < 0)
                return seg.Count;

            var count = seg.Count;
            int first = 0;
            while (count > 0)
            {
                var it = first;
                var step = count / 2;
                it += step;
                if (predFunc(seg[it]).CompareTo(value) < 0)
                {
                    first = ++it;
                    count -= step + 1;
                }
                else
                    count = step;
            }
            return first;
        }

        [DebuggerDisplay("{Strength} ({Count})")]
        class Fighter
        {
            public int Strength;
            public int Count;

        }

        class FightTeam
        {
            readonly List<Fighter> fighters = new List<Fighter>(1000);
            public int agg = 0;
            RangeSum rcountsum = null;
            private RangeSum rstrengthsum = null;

            public FightTeam(bool dorangesum = false)
            {
                if (dorangesum)
                {
                    rcountsum = new RangeSum(new int[50000]);
                    rstrengthsum = new RangeSum(new int[50000]);
                }
            }

            public void Add(int strength)
            {
                var idx = lower_bound(fighters, strength, fighter => fighter.Strength);
                if(idx >= fighters.Count)
                    fighters.Add(new Fighter(){Count = 1, Strength = strength});
                else
                {
                    if(fighters[idx].Strength == strength)
                        fighters[idx].Count++;
                    else 
                        fighters.Insert(idx, new Fighter(){ Count = 1, Strength = strength });
                }
                agg += strength;
                if (rcountsum != null)
                {
                    rcountsum.update(idx, fighters[idx].Count);
                    rstrengthsum.update(idx, fighters[idx].Count * fighters[idx].Strength);
                }
            }

            public class FightTeamEnumerator : IEnumerator<FightTeamEnumerator>
            {
                FightTeam team;
                public int posIdx;
                public int CurrentAggStrength;
                public int CurrentCount;
                public int TopStrength => team.fighters[posIdx].Strength;

                public FightTeamEnumerator(FightTeam team)
                {
                    this.team = team;
                    posIdx = team.fighters.Count - 1;
                    CurrentCount = team.fighters[posIdx].Count;
                    CurrentAggStrength = team.agg;
                }

                public void Dispose()
                {
                }

                public bool MoveNext()
                {
                    return false;
                }

                void checkStatus()
                {
                    /*
                    var totstrength = team.fighters.Take(posIdx).Sum(t => t.Strength * t.Count);
                    totstrength += team.fighters[posIdx].Strength * CurrentCount;
                    Debug.Assert(totstrength == CurrentAggStrength);
                    */
                }

                public bool MoveNext(int _strength, bool optimize = true)
                {
                    int strength = _strength;
                    if (optimize)
                    {
                        if (CurrentCount < team.fighters[posIdx].Count)
                        {
                            if (strength < CurrentCount)
                            {
                                CurrentCount -= strength;
                                CurrentAggStrength -= strength * team.fighters[posIdx].Strength;
                                return true;
                            }

                            strength -= CurrentCount;
                            CurrentAggStrength -= CurrentCount * team.fighters[posIdx].Strength;
                            if (--posIdx < 0)
                                return false;
                            CurrentCount = team.fighters[posIdx].Count;
                            checkStatus();
                        }

                        if (team.rcountsum != null && strength > 20 && team.fighters.Count > 20)
                        {
                            var idx = team.rcountsum.find(strength, 0, posIdx);
                            var totcnt = team.rcountsum.sumRange(idx+1, posIdx);
                            if (totcnt < strength)
                            {
                                strength -= (int) totcnt;
                                var totstrength = (int) team.rstrengthsum.sumRange(idx + 1, posIdx);
                                posIdx = idx;
                                CurrentAggStrength -= totstrength;
                                CurrentCount = team.fighters[posIdx].Count;
                            }
                            else if (totcnt == strength)
                            {
                                strength -= (int) totcnt;
                                var totstrength = (int) team.rstrengthsum.sumRange(idx, posIdx);
                                posIdx = idx - 1;
                                CurrentAggStrength -= totstrength;
                                if (posIdx < 0)
                                    return false;
                                CurrentCount = team.fighters[posIdx].Count;
                                checkStatus();
                                return true;
                            }
                        }
                    }

                    while (strength >= CurrentCount)
                    {
                        strength -= CurrentCount;
                        CurrentAggStrength -= CurrentCount * team.fighters[posIdx].Strength;
                        if (--posIdx < 0)
                            return false;
                        CurrentCount = team.fighters[posIdx].Count;
                    }

                    CurrentCount -= strength;
                    CurrentAggStrength -= strength * team.fighters[posIdx].Strength;
                    checkStatus();
                    return true;
                }

                public void Reset()
                {
                    throw new NotImplementedException();
                }

                public FightTeamEnumerator Current => this;

                object IEnumerator.Current => this;

            }

            public FightTeamEnumerator GetEnumerator()
            {
                return new FightTeamEnumerator(this);
            }
        }

        static int Fight(List<FightTeam> teams, int firstIdx, int secondIdx)
        {
            var first = teams[firstIdx].GetEnumerator();
            var second = teams[secondIdx].GetEnumerator();
            //-----------------------
            var cnt = 0;
            while (true)
            {
                if (first.CurrentAggStrength >= second.CurrentAggStrength)
                    return firstIdx;

                second.MoveNext(first.TopStrength);
                if (second.CurrentAggStrength <= 0 || second.posIdx < 0)
                    return firstIdx;

                if (second.CurrentAggStrength >= first.CurrentAggStrength)
                    return secondIdx;

                first.MoveNext(second.TopStrength);

                if (first.CurrentAggStrength <= 0 || first.posIdx < 0)
                    return secondIdx;
            }
        }


        static void Main(String[] args)
        {
            /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution */
            TextReader reader = null;
            try
            {
                reader = new StringReader(@"7 2 6
1 1
2 1
1 1
1 2
1 2
1 2
2 2
2 1 2
2 2 1
1 2 1
1 2 1
2 1 2
2 2 1");
                reader = File.OpenText(@"c:\temp\input03-MereenFightingPits.txt");
            }
            catch
            {
                reader = Console.In;
            }

            if (reader == null)
                return;

            var tuple = reader.ReadLine().Split(' ').Select(int.Parse).ToArray();
            var n = tuple[0];
            var k = tuple[1];
            var q = tuple[2];
            var teams = new List<FightTeam>(k+1);
            teams.Add(new FightTeam());

            for (int i = 0; i < n; i++)
            {
                var tp = reader.ReadLine().Split(' ').Select(int.Parse).ToArray();
                var tidx = tp[1];
                while (teams.Count <= tidx)
                    teams.Add(new FightTeam(tidx < 5));
                teams[tidx].Add(tp[0]);
            }

            var sb = new StringBuilder();
            //var results = File.ReadAllLines(@"c:\temp\output03-MereenFightingPits.txt").Select(int.Parse).ToArray();
            //var cnt = 0;
            for (int i = 0; i < q; i++)
            {
                var qry = reader.ReadLine().Split(' ').Select(int.Parse).ToArray();
                if (qry[0] == 2)
                {
                    var res = Fight(teams, qry[1], qry[2]);
                    //Debug.Assert(results[cnt] == res);
                    //cnt++;
                    sb.Append(res).AppendLine();
                }
                else if (qry[0] == 1)
                {
                    var teamIdx = qry[2];
                    while (teams.Count <= teamIdx)
                        teams.Add(new FightTeam(teamIdx < 5));
                    var team = teams[teamIdx];
                    var power = qry[1];
                    team.Add(power);
                }
            }
            Console.Write(sb.ToString());
            //File.WriteAllText(@"c:\temp\output.txt",sb.ToString().Trim());
        }

    }
}

Fighting Pits Java Solution

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

Fighting Pits JavaScript Solution

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', inputStdin => {
    inputString += inputStdin;
});

process.stdin.on('end', _ => {
    inputString = inputString.trim().split('\n').map(str => str.trim());

    main();
});

function readLine() {
    return inputString[currentLine++];
}


function fightingPits(k, fighters, queries) {
    let hash = {}, strenth = {}, hashstrenth = {};
    fighters.forEach(x => {
        hash[x[1]] = (hash[x[1]] || []);
        hash[x[1]].push(x[0]);
        strenth[x[1]] = (strenth[x[1]] || 0) + x[0];
        hashstrenth[x[1]] = (hashstrenth[x[1]] || []);
    });
    let array = [];
    for (let s in hash) {
        hash[s].sort((a, b) => a - b);
        let temp = hashstrenth[s], ttt = 0;;
        hash[s].forEach(x => {
            ttt += x;
            temp.push(ttt);
        })
    }
    queries.forEach(([q1, q2, q3]) => {
        if (q1 == 1) {
            let h = hash[q3];
            if (!h) {
                h = hash[q3] = [q2];
                strenth[q3] = q2;
                hashstrenth[q3] = [q2];
                return;
            }
            if (h[h.length - 1] <= q2) {
                h.push(q2);
                strenth[q3] += q2;
                hashstrenth[q3].push(strenth[q3]);
            }
            return;
        }
        if (q1 == 2) {
            if (strenth[q2] >= strenth[q3]) {
                return array.push(q2);
            }
            array.push(fight(hash[q2], hash[q3], q2, q3,
                strenth[q2], strenth[q3], hash[q2].length, hash[q3].length, hashstrenth[q2], hashstrenth[q3]))
        }
    })
    return array;
}
function fight(attackers, defenders, team1, team2, strenth1, strenth2, i1, i2, attackerss, defenderss) {
   
    let c = 1;
    while (true) {
        if (c == 1) {
            c = -1;
            if (strenth1 >= strenth2) return team1;
            if (i1 <= 0) {
                return team2;
            }
            if (i2 <= 0) {
                return team1;
            }
            let fighter = attackers[i1 - 1];
            i2 -= fighter;
            strenth2 = defenderss[i2 - 1] || -1;
        } else {
            if (strenth1 <= strenth2) return team2;
            c = 1;
            if (i2 <= 0) {
                return team1;
            }
            if (i1 <= 0) {
                return team2;
            }
            let fighter = defenders[i2 - 1];
            i1 -= fighter;
            strenth1 = attackerss[i1 - 1]|| - 1;
        }
    }

}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const nkq = readLine().split(' ');

    const n = parseInt(nkq[0], 10);

    const k = parseInt(nkq[1], 10);

    const q = parseInt(nkq[2], 10);

    let fighters = Array(n);

    for (let fightersRowItr = 0; fightersRowItr < n; fightersRowItr++) {
        fighters[fightersRowItr] = readLine().split(' ').map(fightersTemp => parseInt(fightersTemp, 10));
    }

    let queries = Array(q);

    for (let queriesRowItr = 0; queriesRowItr < q; queriesRowItr++) {
        queries[queriesRowItr] = readLine().split(' ').map(queriesTemp => parseInt(queriesTemp, 10));
    }

    let result = fightingPits(k, fighters, queries);

    ws.write(result.join("\n") + "\n");

    ws.end();
}

Fighting Pits Python Solution

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

    # Execute queries
    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()
c C# C++ HackerRank Solutions java javascript python