HackerRank Training the army problem solution YASH PAL, 31 July 2024 In this HackerRank Training the army problem solution 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. 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()) {“mode”:”full”,”isActive”:false} 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(); } } } {“mode”:”full”,”isActive”:false} 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; } {“mode”:”full”,”isActive”:false} 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; } {“mode”:”full”,”isActive”:false} algorithm coding problems