# HackerRank Play on benders problem solution

In this HackerRank Play on benders problem solution, General Iroh and Commandant Bumi are heading to the Republic City to stop a rebellion. But it's quite a long travel, so in the meantime, they have started discussing possible attacking plans. Right now, they're arguing about the best ways for moving soldiers during the battle. Tired of not getting a final and concise strategy, Iroh proposed a particularly original idea.

## Problem solution in Python.

```#!/bin/python3

import math
import os
import random
import re
import sys
from collections import defaultdict

def recursive_solve(node, path_dict, res_dict):
if node in res_dict:
return res_dict[node]
if node not in path_dict:
res_dict[node] = 0
return 0
child_list = path_dict[node]
mex_set = set()
for c in child_list:
grundy_c = recursive_solve(c, path_dict, res_dict)

grundy = 0
while grundy in mex_set:
grundy += 1

res_dict[node] = grundy
return grundy

def bendersPlay(n, path_dict, query, res_dict):
k = len(query)
soldier_dict = defaultdict(int)
for i in range(k):
b_i = query[i]
soldier_dict[b_i] += 1

res = 0
for b_i, num in soldier_dict.items():
if num % 2 == 0:
continue
new = recursive_solve(b_i, path_dict, res_dict)
res ^= new
winner = "Iroh" if res == 0 else "Bumi"
return winner

if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')

first_multiple_input = input().rstrip().split()

n = int(first_multiple_input[0])

m = int(first_multiple_input[1])

paths = []

for _ in range(m):
paths.append(list(map(int, input().rstrip().split())))

path_dict = defaultdict(list)
for i in range(m):
u, v = paths[i]
path_dict[u].append(v)

res_dict = dict()
q = int(input().strip())

for q_itr in range(q):
query_count = int(input().strip())

query = list(map(int, input().rstrip().split()))

result = bendersPlay(n, path_dict, query, res_dict)

fptr.write(result + '\n')

fptr.close()```

## Problem solution in Java.

```import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;

public class Solution {
static List<Integer>[] map = null;
static boolean[] visited = null;
static int[] order = null;

static int idx = 0;

static void go() {

int n = in.nextInt();
int m = in.nextInt();
map = new List[n];
for(int i = 0; i < n; i++)
map[i] = new ArrayList<Integer>();

while(m-- > 0) {
int from = in.nextInt() - 1;
int to = in.nextInt() - 1;
}

visited = new boolean[n];
order = new int[n];
idx = 0;
for(int i = 0; i < n; i++) {
if(!visited[i]) {
dfs(i);
}
}

int[] nim = new int[n];
for(int i = 0; i < n; i++) {
int c = order[i];
int len = map[c].size();
int[] y = new int[len];
for(int j = 0; j < len; j++) {
y[j] = nim[map[c].get(j)];
}
int x = 0;
while(x < len) {
int z = y[x];
if (z == x) {
x++;
continue;
}
if (z < x || z >= len || y[z] == z) {
y[x] = y[--len];
} else {
y[x] = y[z];
y[z] = z;
}
}
nim[c] = x;
}

int q = in.nextInt();
while(q-- > 0) {
int k = in.nextInt();
int N = 0;
for(int i = 0; i < k; i++) {
int next = in.nextInt() - 1;
N ^= nim[next];
}
if (N == 0) {
out.println("Iroh");
} else {
out.println("Bumi");
}
}
}

static void dfs(int c) {
visited[c] = true;
for(int next : map[c]) {
if(!visited[next])
dfs(next);
}
order[idx++] = c;
}

static PrintWriter out;

public static void main(String[] args) {
out = new PrintWriter(System.out);

go();

out.close();
}

private InputStream stream;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;

this.stream = stream;
}

if (numChars == -1)
throw new InputMismatchException();
if (curChar >= numChars) {
curChar = 0;
try {
} catch (IOException e) {
throw new InputMismatchException();
}
if (numChars <= 0)
return -1;
}
return buf[curChar++];
}

public int nextInt() {
return (int) nextLong();
}

public long nextLong() {
while (isSpaceChar(c))
int sgn = 1;
if (c == '-') {
sgn = -1;
}
long res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
} while (!isSpaceChar(c));
return res * sgn;
}

public String nextString() {
while (isSpaceChar(c))
StringBuilder sb = new StringBuilder(1024);
do {
sb.append((char) c);
} while (!isSpaceChar(c));
return sb.toString();
}

public static boolean isSpaceChar(int c) {
switch (c) {
case -1:
case ' ':
case '\n':
case '\r':
case '\t':
return true;
default:
return false;
}
}
}
}```

## Problem solution in C++.

```#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <bitset>
#include <set>
#include <map>
#include <assert.h>
#include <math.h>
#include <vector>
#include <time.h>

using namespace std;

#define forn(i, x, n) for(int i = int(x); i <= int(n); ++i)
#define for1(i, n, x) for(int i = int(n); i >= int(x); --i)
#define file "1."
#define pb push_back
#define F first
#define S second
#define mk_pr make_pair
#define _bits __builtin_popcount

typedef long long ll;
typedef double ld;
typedef pair <ll, ll> PII;
typedef const int const_i;

const int maxn = 200100;
const int INF = 1e9 + 9;
const int bae = 1e9 + 7;

int n, m;
vector <int> g[maxn];

int d[maxn];
bool used[maxn];

int Grundy(const int &x) {
if (used[x]) return d[x];
used[x] = 1;
vector <bool> to_state(g[x].size() + 1, 0);
forn(i, 0, g[x].size() - 1) {
int to = g[x][i];
int grundy_to = Grundy(to);
if (grundy_to > g[x].size()) continue;
to_state[grundy_to] = 1;
}
forn(i, 0, to_state.size() - 1) {
if (to_state[i]) continue;
return d[x] = i;
}
return d[to_state.size()];
}

int q, k;
int bender[maxn];

int main() {
#ifndef ONLINE_JUDGE

#endif

scanf("%d %d", &n, &m);
forn(i, 1, m) {
int f = 0, t = 0;
scanf("%d %d", &f, &t);
g[f].pb(t);
}

scanf("%d", &q);
forn(i, 1, q) {
scanf("%d", &k);
forn(j, 1, k)
scanf("%d", &bender[j]);
int ans = 0;
forn(j, 1, k)
ans ^= Grundy(bender[j]);
printf(ans ? "Bumi\n" : "Iroh\n");
if (ans < 0)
printf("Chong\n");
}

return 0;
}
```

## Problem solution in C.

```#include<stdio.h>
#include<stdlib.h>
void sort_a2(int *a,int *b,int size);
void merge2(int *a,int *left_a,int *right_a,int *b,int *left_b,int *right_b,int left_size,int right_size);
void process(int N,int M,int *u,int *v,int *v_right,int *list_index,int *left_index,int *right_index,int *d,int *l,int *ans,int *temp);
int main(){
int N,M,Q,K,b,a,i;
int *u,*v,*v_right,*d,*l,*ans,*temp,*list_index,*left_index,*right_index;
scanf("%d%d",&N,&M);
u=(int*)malloc(M*sizeof(int));
v=(int*)malloc(M*sizeof(int));
v_right=(int*)malloc(M*sizeof(int));
list_index=(int*)malloc(M*sizeof(int));
left_index=(int*)malloc(N*sizeof(int));
right_index=(int*)malloc(N*sizeof(int));
d=(int*)malloc(N*sizeof(int));
l=(int*)malloc((N+1)*sizeof(int));
ans=(int*)malloc(N*sizeof(int));
temp=(int*)malloc(N*sizeof(int));
for(i=0;i<N;i++)
d[i]=temp[i]=0;
for(i=0;i<M;i++){
scanf("%d%d",u+i,v+i);
list_index[i]=i;
d[u[i]-1]++;
}
sort_a2(u,v,M);
for(i=0;i<M;i++)
v_right[i]=v[i];
sort_a2(v_right,list_index,M);
for(i=0;i<M;i++){
if(i==0||u[i]!=u[i-1])
left_index[u[i]]=i;
if(i==0||v_right[i]!=v_right[i-1])
right_index[v_right[i]]=i;
}
l[0]=0;
for(i=0;i<N;i++)
if(!d[i])
l[++l[0]]=i+1;
while(l[0])
process(N,M,u,v,v_right,list_index,left_index,right_index,d,l,ans,temp);
scanf("%d",&Q);
while(Q--){
scanf("%d",&K);
a=0;
while(K--){
scanf("%d",&b);
a=a^ans[b-1];
}
if(a)
printf("Bumi\n");
else
printf("Iroh\n");
}
return 0;
}
void sort_a2(int *a,int *b,int size){
if(size<2)
return;
int m=(size+1)/2,i;
int *left_a,*left_b,*right_a,*right_b;
left_a=(int*)malloc(m*sizeof(int));
right_a=(int*)malloc((size-m)*sizeof(int));
left_b=(int*)malloc(m*sizeof(int));
right_b=(int*)malloc((size-m)*sizeof(int));
for(i=0;i<m;i++){
left_a[i]=a[i];
left_b[i]=b[i];
}
for(i=0;i<size-m;i++){
right_a[i]=a[i+m];
right_b[i]=b[i+m];
}
sort_a2(left_a,left_b,m);
sort_a2(right_a,right_b,size-m);
merge2(a,left_a,right_a,b,left_b,right_b,m,size-m);
free(left_a);
free(right_a);
free(left_b);
free(right_b);
return;
}
void merge2(int *a,int *left_a,int *right_a,int *b,int *left_b,int *right_b,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_a[j];
b[i+j]=right_b[j];
j++;
}
else if(j==right_size){
a[i+j]=left_a[i];
b[i+j]=left_b[i];
i++;
}
else if(left_a[i]<=right_a[j]){
a[i+j]=left_a[i];
b[i+j]=left_b[i];
i++;
}
else{
a[i+j]=right_a[j];
b[i+j]=right_b[j];
j++;
}
}
return;
}
void process(int N,int M,int *u,int *v,int *v_right,int *list_index,int *left_index,int *right_index,int *d,int *l,int *ans,int *temp){
int x=l[l[0]--],i,flag=0;
for(i=left_index[x];i>=0&&i<M&&u[i]==x;i++){
flag=1;
temp[ans[v[i]-1]+1]++;
if(ans[v[i]-1]+1>temp[0])
temp[0]=ans[v[i]-1]+1;
}
if(flag){
for(i=1;i<temp[0]+2;i++)
if(!temp[i]){
ans[x-1]=i-1;
break;
}
for(i=temp[0];i>=0;i--)
temp[i]=0;
}
else
ans[x-1]=0;
for(i=right_index[x];i>=0&&i<M&&v_right[i]==x;i++){
d[u[list_index[i]]-1]--;
if(!d[u[list_index[i]]-1])
l[++l[0]]=u[list_index[i]];
}
return;
}```