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
2D Array-DS
Given a 6*6 2D Array, arr: 1 1 1 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 An hourglass in A is a subset of values with indices falling in this pattern in arr's graphical representation: a b c d e f g There are 16 hourglasses in arr. An hourglass sum is the sum of an hourglass' values. Calculate the hourglass sum for every hourglass in arr, then print t
View Solution →Dynamic Array
Create a list, seqList, of n empty sequences, where each sequence is indexed from 0 to n-1. The elements within each of the n sequences also use 0-indexing. Create an integer, lastAnswer, and initialize it to 0. There are 2 types of queries that can be performed on the list of sequences: 1. Query: 1 x y a. Find the sequence, seq, at index ((x xor lastAnswer)%n) in seqList.
View Solution →Left Rotation
A left rotation operation on an array of size n shifts each of the array's elements 1 unit to the left. Given an integer, d, rotate the array that many steps left and return the result. Example: d=2 arr=[1,2,3,4,5] After 2 rotations, arr'=[3,4,5,1,2]. Function Description: Complete the rotateLeft function in the editor below. rotateLeft has the following parameters: 1. int d
View Solution →Sparse Arrays
There is a collection of input strings and a collection of query strings. For each query string, determine how many times it occurs in the list of input strings. Return an array of the results. Example: strings=['ab', 'ab', 'abc'] queries=['ab', 'abc', 'bc'] There are instances of 'ab', 1 of 'abc' and 0 of 'bc'. For each query, add an element to the return array, results=[2,1,0]. Fun
View Solution →Array Manipulation
Starting with a 1-indexed array of zeros and a list of operations, for each operation add a value to each of the array element between two given indices, inclusive. Once all operations have been performed, return the maximum value in the array. Example: n=10 queries=[[1,5,3], [4,8,7], [6,9,1]] Queries are interpreted as follows: a b k 1 5 3 4 8 7 6 9 1 Add the valu
View Solution →Print the Elements of a Linked List
This is an to practice traversing a linked list. Given a pointer to the head node of a linked list, print each node's data element, one per line. If the head pointer is null (indicating the list is empty), there is nothing to print. Function Description: Complete the printLinkedList function in the editor below. printLinkedList has the following parameter(s): 1.SinglyLinkedListNode
View Solution →