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
Delete duplicate-value nodes from a sorted linked list
This challenge is part of a tutorial track by MyCodeSchool You are given the pointer to the head node of a sorted linked list, where the data in the nodes is in ascending order. Delete nodes and return a sorted list with each distinct value in the original list. The given head pointer may be null indicating that the list is empty. Example head refers to the first node in the list 1 -> 2 -
View Solution →Cycle Detection
A linked list is said to contain a cycle if any node is visited more than once while traversing the list. Given a pointer to the head of a linked list, determine if it contains a cycle. If it does, return 1. Otherwise, return 0. Example head refers 1 -> 2 -> 3 -> NUL The numbers shown are the node numbers, not their data values. There is no cycle in this list so return 0. head refer
View Solution →Find Merge Point of Two Lists
This challenge is part of a tutorial track by MyCodeSchool Given pointers to the head nodes of 2 linked lists that merge together at some point, find the node where the two lists merge. The merge point is where both lists point to the same node, i.e. they reference the same memory location. It is guaranteed that the two head nodes will be different, and neither will be NULL. If the lists share
View Solution →Inserting a Node Into a Sorted Doubly Linked List
Given a reference to the head of a doubly-linked list and an integer ,data , create a new DoublyLinkedListNode object having data value data and insert it at the proper location to maintain the sort. Example head refers to the list 1 <-> 2 <-> 4 - > NULL. data = 3 Return a reference to the new list: 1 <-> 2 <-> 4 - > NULL , Function Description Complete the sortedInsert function
View Solution →Reverse a doubly linked list
This challenge is part of a tutorial track by MyCodeSchool Given the pointer to the head node of a doubly linked list, reverse the order of the nodes in place. That is, change the next and prev pointers of the nodes so that the direction of the list is reversed. Return a reference to the head node of the reversed list. Note: The head node might be NULL to indicate that the list is empty.
View Solution →Tree: Preorder Traversal
Complete the preorder function in the editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's preorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the preOrder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the tree's
View Solution →