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