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;
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;
}
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() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.precision(10);
cout << fixed;
#ifdef LOCAL_DEFINE
freopen("input.txt", "rt", stdin);
#endif
int n, k, q;
cin >> n >> k >> q;
forn(i, n) {
int s, t;
cin >> s >> t;
teams[--t].pb(s);
}
forn(i, k) {
sort(all(teams[i]));
same[i].pb(0);
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;
--id;
if (!teams[id].empty() && p == teams[id].back()) same[id].pb(same[id][same[id].size() - 1] + 1);
else same[id].pb(1);
teams[id].pb(p);
} else {
int x, y;
cin >> x >> y;
--x; --y;
cout << (emulate(x, y) ? x : y) + 1 << '\n';
}
}
#ifdef LOCAL_DEFINE
cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
return 0;
}
Solution in Java :
in Java :
import java.io.*;
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));
teamSizes[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));
teamSizes[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(System.in);
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) {
break;
}
strength = unpackhigh(queueItem);
team = unpacklow(queueItem);
teams[team][teamSizes[team]] = strength;
teamSizes[team]++;
}
//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) {
repeatCount++;
teamIndex[k][indexPos++] = pack(storePos+1, repeatCount);
} else {
// Save the compressed version
storePos++;
teams[k][storePos] = pack(prevValue, repeatCount);
repeatCount = 1;
prevValue = (int) teams[k][searchPos];
teamIndex[k][indexPos++] = pack(storePos+1, repeatCount);
}
searchPos++;
}
// Save the compressed version
storePos++;
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.");
//}
sb.append(winner);
sb.append("\n");
} 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
teams[team][compSize]++;
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) {
teamCompressedSizes[team]++;
compSize++;
}
teams[team][compSize] = pack(strength, 1);
teamIndex[team][teamSizes[team]++] = pack(compSize, 1);
}
}
if (queue.isEmpty()) {
break;
}
queueItem = queue.removeFirst().longValue();
}
System.out.println(sb);
//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) {
iterations++;
// 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):
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()
View More Similar Problems
Self Balancing Tree
An AVL tree (Georgy Adelson-Velsky and Landis' tree, named after the inventors) is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. We define balance factor for each node as : balanceFactor = height(left subtree) - height(righ
View Solution →Array and simple queries
Given two numbers N and M. N indicates the number of elements in the array A[](1-indexed) and M indicates number of queries. You need to perform two types of queries on the array A[] . You are given queries. Queries can be of two types, type 1 and type 2. Type 1 queries are represented as 1 i j : Modify the given array by removing elements from i to j and adding them to the front. Ty
View Solution →Median Updates
The median M of numbers is defined as the middle number after sorting them in order if M is odd. Or it is the average of the middle two numbers if M is even. You start with an empty number list. Then, you can add numbers to the list, or remove existing numbers from it. After each add or remove operation, output the median. Input: The first line is an integer, N , that indicates the number o
View Solution →Maximum Element
You have an empty sequence, and you will be given N queries. Each query is one of these three types: 1 x -Push the element x into the stack. 2 -Delete the element present at the top of the stack. 3 -Print the maximum element in the stack. Input Format The first line of input contains an integer, N . The next N lines each contain an above mentioned query. (It is guaranteed that each
View Solution →Balanced Brackets
A bracket is considered to be any one of the following characters: (, ), {, }, [, or ]. Two brackets are considered to be a matched pair if the an opening bracket (i.e., (, [, or {) occurs to the left of a closing bracket (i.e., ), ], or }) of the exact same type. There are three types of matched pairs of brackets: [], {}, and (). A matching pair of brackets is not balanced if the set of bra
View Solution →Equal Stacks
ou have three stacks of cylinders where each cylinder has the same diameter, but they may vary in height. You can change the height of a stack by removing and discarding its topmost cylinder any number of times. Find the maximum possible height of the stacks such that all of the stacks are exactly the same height. This means you must remove zero or more cylinders from the top of zero or more of
View Solution →