Table of Contents
Training the army – 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++ Training the army HackerRank Solution
#include <cstdio>
#include <cstring>
#include <algorithm>
// the maximum number of vertices
#define NN 1000
// adjacency matrix (fill this up)
// If you fill adj[][] yourself, make sure to include both u->v and v->u.
int cap[NN][NN], deg[NN], adj[NN][NN];
// BFS stuff
int q[NN], prev[NN];
int dinic( int n, int s, int t )
{
int flow = 0;
// init the adjacency list adj[][] from cap[][]
memset( deg, 0, sizeof( deg ) );
for( int u = 0; u < n; u++ )
for( int v = 0; v < n; v++ ) if( cap[u][v] || cap[v][u] )
adj[u][deg[u]++] = v;
while( true )
{
memset( prev, -1, sizeof( prev ) );
int qf = 0, qb = 0;
prev[q[qb++] = s] = -2;
while( qb > qf && prev[t] == -1 )
for( int u = q[qf++], i = 0, v; i < deg[u]; i++ )
if( prev[v = adj[u][i]] == -1 && cap[u][v] )
prev[q[qb++] = v] = u;
if( prev[t] == -1 ) break;
for( int z = 0; z < n; z++ ) if( cap[z][t] && prev[z] != -1 )
{
int bot = cap[z][t];
for( int v = z, u = prev[v]; u >= 0; v = u, u = prev[v] )
bot = std::min(bot, cap[u][v]);
if( !bot ) continue;
cap[z][t] -= bot;
cap[t][z] += bot;
for( int v = z, u = prev[v]; u >= 0; v = u, u = prev[v] )
{
cap[u][v] -= bot;
cap[v][u] += bot;
}
flow += bot;
}
}
return flow;
}
int n,t,k,c;
int main() {
scanf("%d %d", &n, &t);
int src = 0;
int sink = n+t+1;
for (int i = 1; i <= n; i++) {
scanf("%d", &c);
cap[src][i] = c;
cap[i][sink] = 1;
}
for (int i = 1; i <= t; i++) {
int k;
for (scanf("%d", &k); k; k--) {
scanf("%d", &c);
cap[c][n+i]++;
}
for (scanf("%d", &k); k; k--) {
scanf("%d", &c);
cap[n+i][c]++;
}
}
printf("%d\n", dinic(n+t+2, src, sink));
}
Java Training the army HackerRank Solution
import java.io.*;
import java.util.Arrays;
public class HR_training_the_army {
public static void solve(Input in, PrintWriter out) throws IOException {
int n = in.nextInt();
int m = in.nextInt();
int gn = n + m + 2;
int s = n + m;
int t = n + m + 1;
int[][] g = new int[gn][gn];
for (int i = 0; i < n; ++i) {
g[s][i] = in.nextInt();
g[i][t] = 1;
}
for (int it = 0; it < m; ++it) {
int as = in.nextInt();
for (int i = 0; i < as; ++i) {
int a = in.nextInt() - 1;
g[a][n + it] = 1;
}
int bs = in.nextInt();
for (int i = 0; i < bs; ++i) {
int b = in.nextInt() - 1;
g[n + it][b] = 1;
}
}
boolean[] col = new boolean[gn];
int ans = 0;
while (dfs(s, t, g, col)) {
ans++;
Arrays.fill(col, false);
}
out.println(ans);
}
private static boolean dfs(int s, int t, int[][] g, boolean[] col) {
if (s == t) {
return true;
}
if (col[s]) {
return false;
}
col[s] = true;
for (int j = 0; j < g.length; ++j) {
if (g[s][j] > 0 && dfs(j, t, g, col)) {
g[s][j]--;
g[j][s]++;
return true;
}
}
return false;
}
public static void main(String[] args) throws IOException {
PrintWriter out = new PrintWriter(System.out);
solve(new Input(new BufferedReader(new InputStreamReader(System.in))), out);
out.close();
}
static class Input {
BufferedReader in;
StringBuilder sb = new StringBuilder();
public Input(BufferedReader in) {
this.in = in;
}
public Input(String s) {
this.in = new BufferedReader(new StringReader(s));
}
public String next() throws IOException {
sb.setLength(0);
while (true) {
int c = in.read();
if (c == -1) {
return null;
}
if (" \n\r\t".indexOf(c) == -1) {
sb.append((char)c);
break;
}
}
while (true) {
int c = in.read();
if (c == -1 || " \n\r\t".indexOf(c) != -1) {
break;
}
sb.append((char)c);
}
return sb.toString();
}
public int nextInt() throws IOException {
return Integer.parseInt(next());
}
public long nextLong() throws IOException {
return Long.parseLong(next());
}
public double nextDouble() throws IOException {
return Double.parseDouble(next());
}
}
}
Python 3 Training the army HackerRank Solution
import collections
class Node:
def __init__(self, id_):
self.id = id_
self.residual_flows = {}
class MaxFlow_LinkedList:
INF = 100000
def __init__(self, N_):
self.N = N_
self.node_table = []
for i in range(0, self.N):
self.node_table.append(Node(i))
self.source = 0
self.sink = N_ - 1
self.max_flow = 0
self.parent_links = [-1] * self.N
self.main_flows = []
def getMainFlows(self):
net_flows = []
for [u, v, c] in self.main_flows:
net_flows.append([u, v, c, self.node_table[v].residual_flows[u]])
return net_flows
def addCapacity(self, u, v, c):
self.node_table[u].residual_flows[v] = c
self.node_table[v].residual_flows[u] = 0
self.main_flows.append([u, v, c])
def addCapacityBoth(self, u, v, c_uv, c_vu):
self.node_table[u].residual_flows[v] = c_uv
self.node_table[v].residual_flows[u] = c_vu
self.main_flows.append([u, v, c_uv])
self.main_flows.append([v, u, c_vu])
def bfs(self):
visited = [False] * self.N
pending = collections.deque();
visited[self.source] = True
pending.append(self.source)
self.parent_links[self.source] = -1
while len(pending) > 0:
curr_node = pending.popleft()
if curr_node == self.sink:
return True
for adj_node, res_flow in self.node_table[curr_node].residual_flows.items():
if res_flow > 0 and not visited[adj_node]:
self.parent_links[adj_node] = curr_node
pending.append(adj_node)
visited[adj_node] = True
return False
def findMaxFlow(self):
max_total_flow = 0
while self.bfs():
# find maximum possible flow in the BFS path
max_path_flow = MaxFlow_LinkedList.INF
v = self.sink
while v != self.source:
u = self.parent_links[v]
max_path_flow = min(max_path_flow, self.node_table[u].residual_flows[v])
v = u
# modify the residual flows:
# - remove the flow from residual flows from source to sink
# - add the flow to residual flows from sink to source
v = self.sink
while v != self.source:
u = self.parent_links[v]
self.node_table[u].residual_flows[v] -= max_path_flow
self.node_table[v].residual_flows[u] += max_path_flow
v = u
max_total_flow += max_path_flow
return max_total_flow
[n, k] = list(map(int, input().split()))
C = list(map(int, input().split()))
A = []
B = []
for i in range(0, k):
a = list(map(int, input().split()))
b = list(map(int, input().split()))
A.append(a[1:])
B.append(b[1:])
def getAIdx(w, i):
return sum(len(a) for a in A[:w]) + i + 1 + n*2
def getBIdx(w, i):
return sum(len(a) for a in A) + sum(len(b) for b in B[:w]) + i + 1 + 2*n
# total nodes = 1sink + 1source + 2*N + sum_of_sizes_A + sum_of_sizes_B
total_nodes = 2 + 2 * n + sum(len(a) for a in A) + sum(len(b) for b in B)
flow_network = MaxFlow_LinkedList(total_nodes)
for [i, c] in enumerate(C):
flow_network.addCapacity(0, i+1, c)
flow_network.addCapacityBoth(i+1, n+1+i, 1, 1000000)
flow_network.addCapacity(n+1+i, total_nodes-1, 1)
for w in range(0, len(A)):
for i in range(0, len(A[w])):
flow_network.addCapacity(A[w][i], getAIdx(w, i), 1)
for w in range(0, len(B)):
for i in range(0, len(B[w])):
flow_network.addCapacity(getBIdx(w, i), n+B[w][i], 1)
for w in range(0, len(A)):
for i in range(0, len(A[w])):
for j in range(0, len(B[w])):
flow_network.addCapacity(getAIdx(w, i), getBIdx(w, j), 1)
print (flow_network.findMaxFlow())
C Training the army HackerRank Solution
#include <stdio.h>
#include <stdlib.h>
typedef struct _node{
int x;
struct _node* next;
} node;
typedef struct _queue{
node *head;
node *tail;
} queue;
typedef struct _list_node{
int x;
int c;
int *p;
struct _list_node *next;
} list_node;
void add_edge(int x,int y,int c);
void list_insert(list_node **head,list_node *x);
void ini_q();
void free_q();
void en_q(node *x);
int de_q();
queue q;
list_node **table;
int main(){
int N,T,ALen=0,BLen=0,AC,BC,t,i,j,k,ans=0;
int **A,**B,*C,*AA,*BB,*pp;
node *tt;
list_node *temp;
scanf("%d%d",&N,&T);
A=(int**)malloc(T*sizeof(int*));
B=(int**)malloc(T*sizeof(int*));
C=(int*)malloc(N*sizeof(int));
for(i=0;i<N;i++)
scanf("%d",C+i);
for(i=0;i<T;i++){
scanf("%d",&t);
ALen+=t;
A[i]=(int*)malloc((t+1)*sizeof(int));
A[i][0]=t;
for(j=1;j<=t;j++){
scanf("%d",&A[i][j]);
A[i][j]--;
}
scanf("%d",&t);
BLen+=t;
B[i]=(int*)malloc((t+1)*sizeof(int));
B[i][0]=t;
for(j=1;j<=t;j++){
scanf("%d",&B[i][j]);
B[i][j]--;
}
}
table=(list_node**)malloc((N+ALen+BLen+2)*sizeof(list_node*));
AA=(int*)malloc(ALen*sizeof(int));
BB=(int*)malloc(BLen*sizeof(int));
pp=(int*)malloc((N+ALen+BLen+2)*sizeof(int));
for(i=0;i<N+ALen+BLen+2;i++)
table[i]=NULL;
for(i=0;i<N;i++){
if(C[i])
add_edge(N+ALen+BLen,i,C[i]);
add_edge(i,N+ALen+BLen+1,1);
}
AC=BC=0;
for(i=0;i<T;i++){
for(j=0;j<A[i][0];j++)
for(k=0;k<B[i][0];k++)
if(A[i][j+1]!=B[i][k+1])
add_edge(N+AC+j,N+ALen+BC+k,1);
for(j=0;j<A[i][0];j++)
AA[AC++]=A[i][j+1];
for(j=0;j<B[i][0];j++)
BB[BC++]=B[i][j+1];
}
for(i=0;i<N;i++){
for(j=0;j<ALen;j++)
if(AA[j]==i)
add_edge(i,N+j,1);
for(j=0;j<BLen;j++)
if(BB[j]==i)
add_edge(N+ALen+j,i,1);
}
do{
for(i=0;i<N+ALen+BLen+2;i++)
pp[i]=-1;
pp[N+ALen+BLen]=N+ALen+BLen;
ini_q();
tt=(node*)malloc(sizeof(node));
tt->x=N+ALen+BLen;
en_q(tt);
while(q.head){
t=de_q();
for(temp=table[t];temp;temp=temp->next)
if(temp->c && pp[temp->x]==-1){
pp[temp->x]=t;
if(temp->x==N+ALen+BLen+1)
goto out;
tt=(node*)malloc(sizeof(node));
tt->x=temp->x;
en_q(tt);
}
}
out:
free_q();
t=N+ALen+BLen+1;
pp[N+ALen+BLen]=-1;
while(pp[t]!=-1){
for(temp=table[pp[t]];temp;temp=temp->next)
if(temp->x==t){
temp->c--;
(*(temp->p))++;
break;
}
t=pp[t];
}
if(pp[N+ALen+BLen+1]!=-1)
ans++;
}while(pp[N+ALen+BLen+1]!=-1);
printf("%d",ans);
return 0;
}
void add_edge(int x,int y,int c){
list_node *t1,*t2;
t1=(list_node*)malloc(sizeof(list_node));
t2=(list_node*)malloc(sizeof(list_node));
t1->x=y;
t1->c=c;
t2->x=x;
t2->c=0;
t1->p=&(t2->c);
t2->p=&(t1->c);
list_insert(&table[x],t1);
list_insert(&table[y],t2);
return;
}
void list_insert(list_node **head,list_node *x){
x->next=*head;
*head=x;
return;
}
void ini_q(){
q.head=q.tail=NULL;
return;
}
void free_q(){
node *p=q.head,*t;
while(p){
t=p;
p=p->next;
free(t);
}
return;
}
void en_q(node *x){
if(!q.tail){
q.head=q.tail=x;
x->next=NULL;
}
else{
q.tail->next=x;
q.tail=x;
q.tail->next=NULL;
}
return;
}
int de_q(){
int x=q.head->x;
node *p=q.head;
q.head=q.head->next;
if(q.head==NULL)
q.tail=NULL;
free(p);
return x;
}
Leave a comment below
