HackerRank Training the army problem solution YASH PAL, 31 July 202424 January 2026 In this HackerRank Training the army problem solution In the magical kingdom of Kasukabe, people strive to possess skillsets. Higher the number of skillset present among the people, the more content people will be.There are N types of skill set present and initially there exists Ci people possessing ith skill set, where i relate to [1,N]. There are T wizards in the kingdom and they have the ability to transform the skill set of a person into another skill set. Each of the these wizards has two lists of skill sets associated with them, A and B. He can only transform the skill set of person whose initial skill set belongs to the list to one of the final skill set which belongs to the list B.Once a transformation is done, both skill is removed from the respective lists. In the above example, if he perform 3->1 transformation on a person, list A will be updated to [2,6] and list B will be [2]. This updated list will be used for further transformations.Few points to note are: One person can possess only one skill set.A wizard can perform zero or more transformation as long as they satisfies the above criteria.A person can go through multiple transformation of skill set.Same class transformation is also possible. That is a person’ skill set can be transformed into his current skill set. Eg. 2->2 in the above example.Your goal is to design a series of transformations that results in a maximum number of skill sets with a non-zero number of people knowing it.HackerRank Training the army problem solution in Python.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()) Training the army problem solution in Java.import java.io.*; import java.util.*; public class Solution { private static Reader in; private static PrintWriter out; public static void main(String[] args) throws IOException { in = new Reader(); out = new PrintWriter(System.out, true); int M = in.nextInt(), T = in.nextInt(); N = 2 + M + T * 2; E = 2 * N + N * T * 2 + T; flow = new int[2 * E]; capa = new int[2 * E]; now = new int[N]; eadj =new int[2 * E]; eprev = new int[2 * E]; elast = new int[N]; level = new int[N]; Arrays.fill (elast, -1); eidx = 0; for (int i = 0; i < M; i++) { int a = in.nextInt(); if (a != 0) { add_edge(N - 1, i, a); } add_edge(i, N - 2, 1); } for (int i = 0; i < T; i++) { int num = in.nextInt(); for (int j = 0; j < num; j++) { add_edge(in.nextInt() - 1, M + i, 1); } num = in.nextInt(); for (int j = 0; j < num; j++) { add_edge(M + i, in.nextInt() - 1, 1); } } out.println(dinic(N - 1, N - 2)); out.close(); System.exit(0); } private static int [] flow, capa, now; public static int[] eadj, eprev, elast; public static int eidx; public static int N, E; public static int INF = 1 << 29; private static void add_edge (int a, int b, int c) { eadj[eidx] = b; flow[eidx] = 0; capa[eidx] = c; eprev[eidx] = elast[a]; elast[a] = eidx++; eadj[eidx] = a; flow[eidx] = c; capa[eidx] = c; eprev[eidx] = elast[b]; elast[b] = eidx++; } private static int dinic (int source, int sink) { int res, flow = 0; while (bfs (source, sink)) { // see if there is an augmenting path System.arraycopy (elast, 0, now, 0, N); while ((res = dfs (source, INF, sink)) > 0) { // push all possible flow through flow += res; } } return flow; } private static int [] level; private static boolean bfs (int source, int sink) { Arrays.fill (level, -1); int front = 0, back = 0; int [] queue = new int [N]; level[source] = 0; queue[back++] = source; while (front < back && level[sink] == -1) { int node = queue[front++]; for (int e = elast[node]; e != -1; e = eprev[e]) { int to = eadj[e]; if (level[to] == -1 && flow[e] < capa[e]) { level[to] = level[node] + 1; queue[back++] = to; } } } return level[sink] != -1; } private static int dfs (int cur, int curflow, int goal) { if (cur == goal) { return curflow; } for (int e = now[cur]; e != -1; now[cur] = e = eprev[e]) { if (level[eadj[e]] > level[cur] && flow[e] < capa[e]) { int res = dfs (eadj[e], Math.min (curflow, capa[e] - flow[e]), goal); if (res > 0) { flow[e] += res; flow[e ^ 1] -= res; return res; } } } return 0; } static class Reader { final private int BUFFER_SIZE = 1 << 16; private DataInputStream din; private byte[] buffer; private int bufferPointer, bytesRead; public Reader() { din = new DataInputStream(System.in); buffer = new byte[BUFFER_SIZE]; bufferPointer = bytesRead = 0; } public Reader(String file_name) throws IOException { din = new DataInputStream(new FileInputStream(file_name)); buffer = new byte[BUFFER_SIZE]; bufferPointer = bytesRead = 0; } public String readLine() throws IOException { byte[] buf = new byte[1024]; int cnt = 0, c; while ((c = read()) != -1) { if (c == 'n') break; buf[cnt++] = (byte) c; } return new String(buf, 0, cnt); } public int nextInt() throws IOException { int ret = 0; byte c = read(); while (c <= ' ') c = read(); boolean neg = (c == '-'); if (neg) c = read(); do { ret = ret * 10 + c - '0'; } while ((c = read()) >= '0' && c <= '9'); if (neg) return -ret; return ret; } public long nextLong() throws IOException { long ret = 0; byte c = read(); while (c <= ' ') c = read(); boolean neg = (c == '-'); if (neg) c = read(); do { ret = ret * 10 + c - '0'; } while ((c = read()) >= '0' && c <= '9'); if (neg) return -ret; return ret; } public double nextDouble() throws IOException { double ret = 0, div = 1; byte c = read(); while (c <= ' ') c = read(); boolean neg = (c == '-'); if (neg) c = read(); do { ret = ret * 10 + c - '0'; } while ((c = read()) >= '0' && c <= '9'); if (c == '.') while ((c = read()) >= '0' && c <= '9') ret += (c - '0') / (div *= 10); if (neg) return -ret; return ret; } private void fillBuffer() throws IOException { bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE); if (bytesRead == -1) buffer[0] = -1; } private byte read() throws IOException { if (bufferPointer == bytesRead) fillBuffer(); return buffer[bufferPointer++]; } public void close() throws IOException { if (din == null) return; din.close(); } } } Problem solution in C++.#include <bits/stdc++.h>using namespace std;typedef long long ll;const int MAXN = 10000;const int MAXM = 100000;const ll inf = 1LL << 50;int cnt, box[MAXN], pre[MAXN], gap[MAXN], h[MAXN], cur[MAXN];int N, NS, NT;ll flow[MAXN];struct edge { int to, ne; ll w;} e[MAXM * 2];void adds(int u, int v, ll w) { e[cnt].to = v; e[cnt].w = w; e[cnt].ne = box[u]; box[u] = cnt++;}void add(int u, int v, ll w) { adds(u, v, w); adds(v, u, 0LL);}ll mins(ll x, ll y) { return x < y ? x : y;}int qu[MAXN];void bfs() { memset(h,-1,sizeof(h)); memset(gap,0,sizeof(gap)); h[NT]=0; gap[0]=1; int st=0,ed=1; qu[ed]=NT; while(st!=ed) { int u=qu[++st]; for(int p=box[u]; p!=-1; p=e[p].ne) if (h[e[p].to]==-1) { h[e[p].to]=h[u]+1; qu[++ed]=e[p].to; ++gap[ h[e[p].to]=h[u]+1 ]; } }}ll sap() { int u,v,p; ll flowans=0; //memset(gap,0,sizeof(gap));gap[0]=N; // memset(h,0,sizeof(h)); bfs(); for(int i=0; i<N; i++) cur[i]=box[i]; flow[NS]=inf; u=NS; while(h[NS]<N) { for(p=cur[u]; p!=-1; p=e[p].ne) if (e[p].w&&h[e[p].to]+1==h[u]) { cur[u]=p; v=e[p].to; flow[v]=mins(flow[u],e[p].w); pre[v]=p; u=v; if (u==NT) { flowans+=flow[NT]; while(u!=NS) { e[pre[u]].w-=flow[NT]; e[pre[u]^1].w+=flow[NT]; u=e[pre[u]^1].to; } } break; } if (p==-1) { cur[u]=box[u]; if (--gap[h[u]]==0) break; h[u]=N; for(p=box[u]; p!=-1; p=e[p].ne) if (e[p].w&&h[e[p].to]+1<h[u]) h[u]=h[e[p].to]+1; gap[h[u]]++; if (u!=NS) u=e[pre[u]^1].to; } } return flowans;}int main() { memset(box, -1, sizeof(box)); cnt = 0; int n, m; scanf("%d%d", &n, &m); N = n + m * 2 + 2; NS = N - 1; NT = N - 2; for (int i = 0; i < n; i ++) { int val; scanf("%d", &val); add(NS, i, val); add(i, NT, 1); } int cntx = n; for (int i = 0; i < m; i ++) { for (int j = 0; j < 2; j ++) { int num; scanf("%d", &num); for (int k = 0; k < num; k ++) { int p; scanf("%d", &p); if (j == 0) { add(p - 1, cntx, 1); } else { add(cntx, p - 1, 1); } } cntx ++; } add(cntx - 2, cntx - 1, inf); } printf("%lldn", sap()); return 0;}Problem solution in C.#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; } Algorithms coding problems solutions AlgorithmsHackerRank