Fighting Pits – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ Fighting Pits HackerRank Solution
#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;
}
Java Fighting Pits HackerRank Solution
import java.io.*;
import java.util.*;
public class D {
BufferedReader br;
PrintWriter out;
StringTokenizer st;
boolean eof;
static final int K = 500;
int[] sz;
List<Integer>[] teamsLst;
int[][] teams;
HashMap<Long, int[][]> map = new HashMap<>();
int k;
int go(int x, int y) {
if (sz[x] < K || sz[y] < K) {
boolean moveX = true;
int ptrX = sz[x];
int ptrY = sz[y];
int[] teamX = teams[x];
int[] teamY = teams[y];
for (; ptrX > 0 && ptrY > 0; moveX = !moveX) {
if (moveX) {
ptrY -= teamX[ptrX - 1];
} else {
ptrX -= teamY[ptrY - 1];
}
}
return ptrX > 0 ? x : y;
}
long ptr1 = (long) x * k + y;
int[][] arrX = map.get(ptr1);
if (arrX == null) {
arrX = new int[2][teams[x].length + 1];
Arrays.fill(arrX[1], teams[y].length + 1);
map.put(ptr1, arrX);
}
long ptr2 = (long) y * k + x;
int[][] arrY = map.get(ptr2);
if (arrY == null) {
arrY = new int[2][teams[y].length + 1];
Arrays.fill(arrY[1], teams[x].length + 1);
map.put(ptr2, arrY);
}
boolean moveX = true;
int ptrX = sz[x];
int ptrY = sz[y];
int[] teamX = teams[x];
int[] teamY = teams[y];
int winner = -1;
for (; ptrX > 0 && ptrY > 0; moveX = !moveX) {
if (moveX) {
if (ptrY <= arrX[0][ptrX]) {
winner = x;
break;
} else if (ptrY >= arrX[1][ptrX]) {
winner = y;
break;
} else {
ptrY -= teamX[ptrX - 1];
}
} else {
if (ptrX <= arrY[0][ptrY]) {
winner = y;
break;
} else if (ptrX >= arrY[1][ptrY]) {
winner = x;
break;
} else {
ptrX -= teamY[ptrY - 1];
}
}
}
if (winner == -1) {
winner = ptrX > 0 ? x : y;
}
int finalX = ptrX;
int finalY = ptrY;
moveX = true;
ptrX = sz[x];
ptrY = sz[y];
for (; ptrX != finalX || ptrY != finalY; moveX = !moveX) {
if (moveX) {
if (winner == x) {
arrX[0][ptrX] = ptrY;
} else {
arrX[1][ptrX] = ptrY;
}
ptrY -= teamX[ptrX - 1];
} else {
if (winner == y) {
arrY[0][ptrY] = ptrX;
} else {
arrY[1][ptrY] = ptrX;
}
ptrX -= teamY[ptrY - 1];
}
}
return winner;
}
void solve() throws IOException {
int n = nextInt();
k = nextInt();
int q = nextInt();
teamsLst = new List[k];
for (int i = 0; i < k; i++) {
teamsLst[i] = new ArrayList<>();
}
for (int i = 0; i < n; i++) {
int str = nextInt();
int team = nextInt() - 1;
teamsLst[team].add(str);
}
sz = new int[k];
for (int i = 0; i < k; i++) {
Collections.sort(teamsLst[i]);
sz[i] = teamsLst[i].size();
}
int[][] qs = new int[q][3];
for (int i = 0; i < q; i++) {
for (int j = 0; j < 3; j++) {
qs[i][j] = nextInt();
}
if (qs[i][0] == 1) {
qs[i][2]--;
teamsLst[qs[i][2]].add(qs[i][1]);
} else {
qs[i][1]--;
qs[i][2]--;
}
}
teams = new int[k][];
for (int i = 0; i < k; i++) {
teams[i] = new int[teamsLst[i].size()];
for (int j = 0; j < teams[i].length; j++) {
teams[i][j] = teamsLst[i].get(j);
}
}
for (int i = 0; i < q; i++) {
if (qs[i][0] == 1) {
sz[qs[i][2]]++;
} else {
out.println(go(qs[i][1], qs[i][2]) + 1);
}
}
}
D() throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
out = new PrintWriter(System.out);
solve();
out.close();
}
public static void main(String[] args) throws IOException {
new D();
}
String nextToken() {
while (st == null || !st.hasMoreTokens()) {
try {
st = new StringTokenizer(br.readLine());
} catch (Exception e) {
eof = true;
return null;
}
}
return st.nextToken();
}
String nextString() {
try {
return br.readLine();
} catch (IOException e) {
eof = true;
return null;
}
}
int nextInt() throws IOException {
return Integer.parseInt(nextToken());
}
long nextLong() throws IOException {
return Long.parseLong(nextToken());
}
double nextDouble() throws IOException {
return Double.parseDouble(nextToken());
}
}
Python 3 Fighting Pits HackerRank Solution
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()
Python 2 Fighting Pits HackerRank Solution
# Enter your code here. Read input from STDIN. Print output to STDOUT
def accumu(lis):
total = 0
for x in lis:
total += x
yield total
def solve(x,sum_x,a,b):
x,y = x[a], x[b]
sumx,sumy = sum_x[a], sum_x[b]
cx = 1
pt_x = len(x)-1
pt_y = len(y)-1
while pt_x>=0 and pt_y>=0:
if cx == 1:
if sumx[pt_x] >= sumy[pt_y]:
res = a+1
break
pt_y -= x[pt_x]
else:
if sumx[pt_x] <= sumy[pt_y]:
res = b+1
break
pt_x -= y[pt_y]
cx = (cx+1)%2
else:
res = a+1 if pt_x>=0 else b+1
print res
n,k,q = map(int,raw_input().strip().split())
x = [[] for _ in xrange(k)]
sum_x = [[] for _ in xrange(k)]
for _ in xrange(n):
val, ind = map(int,raw_input().strip().split())
x[ind-1].append(val)
for s in xrange(k):
x[s] = sorted(x[s])
sum_x[s] = list(accumu(x[s]))
for _ in xrange(q):
t, a, b= map(int,raw_input().strip().split())
if t == 1:
x[b-1].append(a)
if len(sum_x[b-1]) > 0:
sum_x[b-1].append(sum_x[b-1][-1]+a)
else:
sum_x[b-1].append(a)
else:
solve(x,sum_x,a-1,b-1)
C Fighting Pits HackerRank Solution
#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;
}
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below