In this HackerRank Fighting Pits problem solution Given the initial configuration of the teams and Q queries, perform each query so the Great Masters can plan the next fight.
Problem solution in Python.
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))
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()
Problem solution in Java.
import java.io.*;
import java.util.*;
import java.util.stream.Collectors;
public class Solution {
static class Team {
int sum = 0;
final List<Integer> p = new ArrayList<>();
void add(int power) {
p.add(power);
sum += power;
}
int member(int i) {
return p.get(i);
}
int members() {
return p.size();
}
void opt() {
p.sort(Integer::compareTo);
}
}
/*
* Complete the fightingPits function below.
*/
static void fightingPits(int k, List<List<Integer>> teams, int[][] queries, BufferedWriter writer) throws IOException {
List<List<Integer>> powers = teams.stream().map(
t -> {
t.sort(Integer::compareTo);
List<Integer> res = new ArrayList<>();
int acc = 0;
for (int p : t) {
acc += p;
res.add(acc);
}
return res;
}
).collect(Collectors.toList());
for (int[] q : queries) {
if (q[0] == 1) {
int tI = q[2] - 1;
List<Integer> p = powers.get(tI);
if (p.isEmpty()) {
p.add(q[1]);
} else {
p.add(p.get(p.size() - 1) + q[1]);
}
} else {
int xI = q[1] - 1, yI = q[2] - 1;
final List<Integer> x = powers.get(xI);
final List<Integer> y = powers.get(yI);
int xJ = x.size() - 1, yJ = y.size() - 1;
int winner;
while (true) {
if (x.get(xJ) >= y.get(yJ)) {
winner = xI + 1;
break;
}
yJ -= x.get(xJ) - (xJ < 1 ? 0 : x.get(xJ - 1));
if (yJ < 0) {
winner = xI + 1;
break;
}
if (x.get(xJ) <= y.get(yJ)) {
winner = yI + 1;
break;
}
xJ -= y.get(yJ) - (yJ < 1 ? 0 : y.get(yJ - 1));
if (xJ < 0) {
winner = yI + 1;
break;
}
}
writer.write(String.valueOf(winner));
writer.newLine();
}
}
}
public static void main(String[] args) throws IOException {
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
BufferedReader reader = new BufferedReader(new InputStreamReader(
System.in
// new FileInputStream("/home/malik/Загрузки/input04.txt")
));
String[] nkq = reader.readLine().split(" ");
int n = Integer.parseInt(nkq[0].trim());
int k = Integer.parseInt(nkq[1].trim());
int q = Integer.parseInt(nkq[2].trim());
List<List<Integer>> teams = new ArrayList<>(k);
for (int i = 0; i < k; i++) teams.add(new LinkedList<>());
for (int fightersRowItr = 0; fightersRowItr < n; fightersRowItr++) {
String[] fightersRowItems = reader.readLine().split(" ");
teams.get(Integer.parseInt(fightersRowItems[1]) - 1).add(Integer.parseInt(fightersRowItems[0]));
}
int[][] queries = new int[q][3];
for (int queriesRowItr = 0; queriesRowItr < q; queriesRowItr++) {
String[] queriesRowItems = reader.readLine().split(" ");
for (int queriesColumnItr = 0; queriesColumnItr < 3; queriesColumnItr++) {
int queriesItem = Integer.parseInt(queriesRowItems[queriesColumnItr].trim());
queries[queriesRowItr][queriesColumnItr] = queriesItem;
}
}
fightingPits(k, teams, queries, writer);
reader.close();
writer.close();
}
}
Problem solution in C++.
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int binary(vector<int> &l, int val) {
int lo = 0;
int hi = l.size();
int mid;
while (lo < hi) {
mid = (lo + hi) / 2;
if (l[mid] == val)
return mid;
if (l[mid] > val)
hi = mid;
else
lo = mid + 1;
}
return lo;
}
int find_winner(int x, int y, vector<vector<int>> &l, unsigned long long x_sum, unsigned long long y_sum) {
vector<int> &X = l[x];
vector<int> &Y = l[y];
int x_count = X.size() - 1;
int y_count = Y.size() - 1;
bool chance = true;
while (true) {
if (chance) {
if (x_sum >= y_sum)
return x;
y_count -= X[x_count];
if (y_count < 0)
return x;
for(int i = y_count + 1; i <= y_count + X[x_count]; i++) {
y_sum -= Y[i];
}
} else {
if (y_sum >= x_sum)
return y;
x_count -= Y[y_count];
if (x_count < 0)
return y;
for (int i = x_count + 1; i <= x_count + Y[y_count]; i++) {
x_sum -= X[i];
}
}
chance = !chance;
}
}
int main() {
int n, k, q;
cin >> n >> k >> q;
vector<vector<int>> l;
for (int i = 0; i <= k; i++) {
vector<int> cur;
l.push_back(cur);
}
vector<unsigned long long> sums;
for (int i = 0; i <= k; i++) {
sums.push_back(0);
}
int s, t;
for (int i = 0; i < n; i++) {
cin >> s >> t;
l[t].push_back(s);
sums[t] += s;
}
for (int i = 1; i <= k; i++) {
sort(l[i].begin(), l[i].end());
}
for (int i = 1; i <= q; i++) {
int x, y;
cin >> t >> x >> y;
if (t == 1) {
l[y].insert(l[y].begin() + binary(l[y], x), x);
sums[y] += x;
} else {
cout << find_winner(x, y, l, sums[x], sums[y]) << endl;
}
}
return 0;
}Problem solution 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;
}
0 Comments