Fighting Pits

Problem Statement :

Meereen is famous for its fighting pits where fighters fight each other to the death.

Initially, there are  fighters and each fighter has a strength value. The  fighters are divided into  teams, and each fighter belongs exactly one team. For each fight, the Great Masters of Meereen choose two teams,  and , 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:

The attacking team chooses a fighter from their team with strength .
The chosen fighter chooses at most  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  to team . It is guaranteed that this new fighter's strength value will not be less than any current member of team .
2 x y Print the name of the team that would win a matchup between teams  and  in their current state (recall that team  always starts first). It is guaranteed that .
Given the initial configuration of the teams and  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  (the number of fighters),  (the number of teams), and  (the number of queries).
Each line  of the  subsequent lines contains two space-separated integers describing the respective values of fighter 's strength, , and team number, .
Each of the  subsequent lines contains a space-separated query in one of the two formats defined in the Problem Statement above (i.e., 1 p x or 2 x y).

Output Format

After each type  query, print the name of the winning team on a new line. For example, if  and  are matched up and  wins, you would print .

Solution :


                            Solution in C :

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;
    team_s[i]=(long long*)malloc(team_size[i]*sizeof(long long));
      while(j>0 && k>0){
        if(j<0 || k<0)
  return 0;
void sort_a(int*a,int size){
  if (size < 2)
  int m = (size+1)/2,i;
  int *left,*right;
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];
        } else if (j == right_size) {
            a[i+j] = left[i];
        } else if (left[i] <= right[j]) {
            a[i+j] = left[i];
        } else {
            a[i+j] = right[j];

                        Solution in C++ :

In  C++  :

#include <iostream>
#include <vector>
#include <cmath>
#include <ctime>
#include <cassert>
#include <cstdio>
#include <queue>
#include <set>
#include <map>
#include <fstream>
#include <cstdlib>
#include <string>
#include <cstring>
#include <algorithm>
#include <numeric>

#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;

template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }

const int maxn = 210000;
vi teams[maxn], same[maxn];

bool emulate(int x, int y) {
    int xi = teams[x].size() - 1, yi = teams[y].size() - 1;
    while (xi >= 0 && yi >= 0) {
        int skip = min((same[x][xi] - 1) / teams[y][yi], (same[y][yi] - 1) / teams[x][xi]);
        uax(skip, 0);
        xi -= skip * teams[y][yi];
        yi -= skip * teams[x][xi];
        yi -= teams[x][xi];
        if (yi < 0) break;
        xi -= teams[y][yi];
    return xi >= 0;

int main() {
    cout << fixed;
    freopen("input.txt", "rt", stdin);

    int n, k, q;
    cin >> n >> k >> q;
    forn(i, n) {
        int s, t;
        cin >> s >> t;
    forn(i, k) {
        for1(j, teams[i].size() - 1) {
            if (teams[i][j] != teams[i][j - 1]) same[i].pb(1);
            else same[i].pb(same[i][j - 1] + 1);
    forn(i, q) {
        int t;
        cin >> t;
        if (t == 1) {
            int p, id;
            cin >> p >> id;
            if (!teams[id].empty() && p == teams[id].back()) same[id].pb(same[id][same[id].size() - 1] + 1);
            else same[id].pb(1);
        } else {
            int x, y;
            cin >> x >> y;
            --x; --y;
            cout << (emulate(x, y) ? x : y) + 1 << '\n';

    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
    return 0;

                        Solution in Java :

in   Java :

import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

	public static  long iterations = 0;
	public static final long MASKLOW =  0x000000000003FFFFL;
	public static final long MASKMID =  0x0000000FFFFC0000L;
	public static final long MASKHIGH = 0x0000001000000000L;
	public static void fillQueueFromInput(Scanner scan, ArrayDeque<Long> queue, int[] teamSizes, int N, int Q) {
        // Read each fighter's attributes
        int cmd, op1, op2, strength, team;
        for (int n=0; n<N; n++) {
            strength = scan.nextInt();
            team = scan.nextInt();
            queue.addLast(pack(strength, team));

        // Read all the queries
        for (int q=0; q<Q; q++) {
            cmd = scan.nextInt();
            op1 = scan.nextInt();
            op2 = scan.nextInt();

            if (cmd == 1) {
                // Add fighter of strength (op1) to team (op2)
                queue.addLast(pack(op1, op2));
            } else if (cmd == 2) {
                // Print winning team; (op1 goes first, vs. op2)
                queue.addLast(MASKHIGH + pack(op1, op2));
    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
    	Scanner scan = new Scanner(;
        int N = scan.nextInt(); // number of fighters
        int K = scan.nextInt(); // number of teams
        int Q = scan.nextInt(); // number of queries

    	//long startTime = System.nanoTime();

        long queueItem = 0;
        int op1, op2, strength, team;
        // Figure out the optimal size for our data structures
        // Holds the queries to execute
        ArrayDeque<Long> queue = new ArrayDeque<Long>(Q+N);        
        int[] teamSizes = new int[K+1]; // 1-based indexing
        int[] teamCompressedSizes = new int[K+1];  // 1-based indexing
        fillQueueFromInput(scan, queue, teamSizes, N, Q);
        // scan.close();
        //System.out.println("After Queue Filled: " + ((System.nanoTime() - startTime) /1000000));

        // Allocate sufficient space & init all teams
        long[][] teams = new long[K+1][];   // 1-based indexing
        long[][] teamIndex = new long[K+1][];  // 1-based indexing
        for (int k=1; k<=K; k++) {
            teams[k] = new long[(teamSizes[k] == 0 ? 1 : teamSizes[k])];
            teamIndex[k] = new long[(teamSizes[k] == 0 ? 1 : teamSizes[k])];

        //System.out.println("After Teams Allocated: " + ((System.nanoTime() - startTime) /1000000));

        // Reset the team sizes to zero
        teamSizes = new int[K+1];
        // Process queue until first (print) is found        
        while (!queue.isEmpty()) {
            queueItem = queue.removeFirst().longValue();
            if (queueItem >= MASKHIGH) {
            strength = unpackhigh(queueItem);
            team = unpacklow(queueItem);
            teams[team][teamSizes[team]] = strength; 

        //System.out.println("After Queue 1st Processed: " + ((System.nanoTime() - startTime) /1000000));
        // Sort each team by fighter strength (weak to strong)
        // Also, convert the (teams[]) and (teamSizes[]) arrays to a compressed format after sorting.
        for (int k=1; k<=K; k++) {
        	if (teamSizes[k] > 0) {
	            Arrays.sort(teams[k], 0, teamSizes[k]);
	            // Step thru the array and count the number of duplicate values
	            int searchPos = 1;
	            int storePos = -1;
	            int maxSearchPos = teamSizes[k];
	            int indexPos = 1;
	            int prevValue = (int) teams[k][0];
	            int repeatCount = 1;
	            teamIndex[k][0] = pack(storePos+1, repeatCount);
	            while (searchPos < maxSearchPos) {
	            	if (teams[k][searchPos] == prevValue) {
	    	            teamIndex[k][indexPos++] = pack(storePos+1, repeatCount);
	            	} else {
	            		// Save the compressed version
	            		teams[k][storePos] = pack(prevValue, repeatCount);
	            		repeatCount = 1;
	            		prevValue = (int) teams[k][searchPos];
	    	            teamIndex[k][indexPos++] = pack(storePos+1, repeatCount);
	            // Save the compressed version
	            teams[k][storePos] = pack(prevValue, repeatCount);
	    		// Save the compressed version of (teamSizes)
	    		teamCompressedSizes[k] = storePos;
        	} else {
        		teams[k][0] = 0;	// Empty team
        		teamIndex[k][0] = 0;

        //System.out.println("After Sort/Compress: " + ((System.nanoTime() - startTime) /1000000));
        StringBuilder sb = new StringBuilder(Q * 4);
        // process queries (continue with previously read queueItem)
        while (true) {            
            if (queueItem >= MASKHIGH) {
                // Print winning team (op1 goes first, vs. op2)
                queueItem -= MASKHIGH;
                op1 = unpackhigh(queueItem);
                op2 = unpacklow(queueItem);
                //int expectedWinner = scan.nextInt();
                int winner = determineWinner(teams, teamIndex, teamSizes, teamCompressedSizes, op1, op2);
                //if (winner != expectedWinner) {
                //	System.out.println("ERROR: " + expectedWinner + " should have won.");

            } else {
                // Add fighter of strength (op1) to team (op2)
                // (op1) is guaranteed to be >= strongest fighter
                strength = unpackhigh(queueItem);
                team = unpacklow(queueItem);
                int compSize = teamCompressedSizes[team];
                int repValue = unpackhigh(teams[team][compSize]);
                int repCount = unpacklow(teams[team][compSize]);
                if (strength == repValue) {
                	// if this value already exists, just increment its repeat count
                	teamIndex[team][teamSizes[team]++] = pack(compSize, repCount + 1);
                } else {
                	// value doesn't exist. We need to store it in next location
                	// Handle case where no one is on this team yet. (repCount ==0 and repValue == 0)
                	if (repValue != 0) {
                	teams[team][compSize] = pack(strength, 1);
                	teamIndex[team][teamSizes[team]++] = pack(compSize, 1);
            if (queue.isEmpty()) {
            queueItem = queue.removeFirst().longValue();
        //System.out.println("End: " + ((System.nanoTime() - startTime) /1000000));

        //System.out.println("Iterations = " + iterations);
    public static int determineWinner(long[][] teams, long[][] teamIndex, int[] teamSizes, int[] compressedSizes, int firstTeam, int secondTeam) {
        // teamX always goes first
        long[] teamX = teams[firstTeam];
        long[] teamY = teams[secondTeam];
        long[] teamXIndex = teamIndex[firstTeam];
        long[] teamYIndex = teamIndex[secondTeam];
        // Track which living fighter is strongest on each team
        int onX = teamSizes[firstTeam] - 1; 
        int onY = teamSizes[secondTeam] - 1;  
        int onXcomp = compressedSizes[firstTeam];
        int onYcomp = compressedSizes[secondTeam];
        int onXstrength = unpackhigh(teamX[onXcomp]);
        int onXrepeat = unpacklow(teamX[onXcomp]);
        int onYstrength = unpackhigh(teamY[onYcomp]);
        int onYrepeat = unpacklow(teamY[onYcomp]);
        // Fight
        while (true) {

        	// Since the list of strengths is sorted, when we reach strengths of 1
        	// on both teams, we can just calculate the winner in some
        	// decisive cases.
        	int reductionCount = min(((onYrepeat-1) / onXstrength), ((onXrepeat-1) / onYstrength));
        	if (reductionCount > 0) {
        		onXrepeat -= (onYstrength * reductionCount);
        		onYrepeat -= (onXstrength * reductionCount);
         		onX -= (onYstrength * reductionCount);
        		onY -= (onXstrength * reductionCount);
        	// teamX's strongest fighter kills strongest opponents
        	onY -= onXstrength;
        	if (onY < 0) {
        		return firstTeam;
        	onYcomp = unpackhigh(teamYIndex[onY]);
        	onYrepeat = unpacklow(teamYIndex[onY]);
        	onYstrength = unpackhigh(teamY[onYcomp]);
        	reductionCount = min(((onYrepeat-1) / onXstrength), ((onXrepeat-1) / onYstrength));
        	if (reductionCount > 0) {
        		onXrepeat -= (onYstrength * reductionCount);
        		onYrepeat -= (onXstrength * reductionCount);
         		onX -= (onYstrength * reductionCount);
        		onY -= (onXstrength * reductionCount);

        	// teamY's strongest fighter kills
        	onX -= onYstrength;
        	if (onX < 0) {
        		return secondTeam;
        	onXcomp = unpackhigh(teamXIndex[onX]);
        	onXrepeat = unpacklow(teamXIndex[onX]);
        	onXstrength = unpackhigh(teamX[onXcomp]);
    public static final int min(int a, int b) {
    	return (a<b ? a: b);
    public static final long pack(int a, int b) {
    	return ((long)a << 18) + (long)b;
    public static final int unpacklow(long l) {
    	return (int)(l & MASKLOW);
    public static final int unpackhigh(long l) {
    	return (int)(l >> 18);

                        Solution in Python : 
In   Python3 :

from collections import defaultdict

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

class Team():
    def __init__(self, id, strengths): = 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

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

    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
            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]:
                # 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)
            x, y, key = args
            print(team[x].simulate_fight(team[y], key in memoize_set))

if __name__ == '__main__':

View More Similar Problems

Swap Nodes [Algo]

A binary tree is a tree which is characterized by one of the following properties: It can be empty (null). It contains a root node only. It contains a root node with a left subtree, a right subtree, or both. These subtrees are also binary trees. In-order traversal is performed as Traverse the left subtree. Visit root. Traverse the right subtree. For this in-order traversal, start from

View Solution →

Kitty's Calculations on a Tree

Kitty has a tree, T , consisting of n nodes where each node is uniquely labeled from 1 to n . Her friend Alex gave her q sets, where each set contains k distinct nodes. Kitty needs to calculate the following expression on each set: where: { u ,v } denotes an unordered pair of nodes belonging to the set. dist(u , v) denotes the number of edges on the unique (shortest) path between nodes a

View Solution →

Is This a Binary Search Tree?

For the purposes of this challenge, we define a binary tree to be a binary search tree with the following ordering requirements: The data value of every node in a node's left subtree is less than the data value of that node. The data value of every node in a node's right subtree is greater than the data value of that node. Given the root node of a binary tree, can you determine if it's also a

View Solution →

Square-Ten Tree

The square-ten tree decomposition of an array is defined as follows: The lowest () level of the square-ten tree consists of single array elements in their natural order. The level (starting from ) of the square-ten tree consists of subsequent array subsegments of length in their natural order. Thus, the level contains subsegments of length , the level contains subsegments of length , the

View Solution →

Balanced Forest

Greg has a tree of nodes containing integer data. He wants to insert a node with some non-zero integer value somewhere into the tree. His goal is to be able to cut two edges and have the values of each of the three new trees sum to the same amount. This is called a balanced forest. Being frugal, the data value he inserts should be minimal. Determine the minimal amount that a new node can have to a

View Solution →

Jenny's Subtrees

Jenny loves experimenting with trees. Her favorite tree has n nodes connected by n - 1 edges, and each edge is ` unit in length. She wants to cut a subtree (i.e., a connected part of the original tree) of radius r from this tree by performing the following two steps: 1. Choose a node, x , from the tree. 2. Cut a subtree consisting of all nodes which are not further than r units from node x .

View Solution →