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)
        mex_set.add(grundy_c)
        
    grundy = 0
    while grundy in mex_set:
        grundy += 1
    
    res_dict[node] = grundy
    return grundy
    
def bendersPlay(n, path_dict, query, res_dict):
    # Write your code here
    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;
            map[from].add(to);
        }

        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 InputReader in;
    static PrintWriter out;

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

        go();

        out.close();
    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

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

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

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

        public String nextString() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder sb = new StringBuilder(1024);
            do {
                sb.append((char) c);
                c = read();
            } 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;
}