We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • HackerRank Home

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Graph Theory
  4. Training the army
  5. Discussions

Training the army

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 10 Discussions, By:

recency

Please Login in order to post a comment

  • thecodingsoluti2
    2 months ago+ 0 comments

    Here is problem solution - https://programs.programmingoneonone.com/2021/07/hackerrank-training-the-army-problem-solution.html

    0|
    Permalink
  • shehanjayalath
    3 years ago+ 0 comments

    C++ Solution

    #include <bits/stdc++.h>
    
    using namespace std;
    
    // Self Template Code BGEIN
    
    typedef long long int64;
    typedef pair<int, int> pii;
    
    int sgn(double x) { return (x > 1e-8) - (x < -1e-8); }
    int count_bit(int x) { return x == 0? 0 : count_bit(x >> 1) + (x & 1); }
    
    template<class T> inline void ckmin(T &a, const T b) { if (b < a) a = b; }
    template<class T> inline void ckmax(T &a, const T b) { if (b > a) a = b; }
    
    // Self Template Code END
    
    struct graph {
    	static const int maxn = 50 * 30 * 2 + 200 * 30 + 10;
    	static const int inf = (-1u) >> 1;
    
    	struct Adj {
    		int v, c, b;
    		Adj(int _v, int _c, int _b): v(_v), c(_c), b(_b) {}
    		Adj() {};
    	};
    	int i, n, S, T, h[maxn], cnt[maxn];
    	vector <Adj> adj[maxn];
    	void clear() {
    		for (i = 0; i < n; ++i)
    			adj[i].clear();
    		n = 0;
    	}
    	void insert(int u, int v, int c, int d = 0) {
    		// printf ("insert %d %d %d\n", u, v, c);
    		n = max(n, max(u, v) + 1);
    		adj[u].push_back(Adj(v, c, adj[v].size()));
    		adj[v].push_back(Adj(u, c * d, adj[u].size() - 1));
    	}
    	int maxflow(int _S, int _T) {
    		S = _S, T = _T;
    		fill(h, h + n, 0);
    		fill(cnt, cnt + n, 0);
    		int flow = 0;
    		while (h[S] < n)
    			flow += dfs(S, inf);
    		return flow;
    	}
    	int dfs(int u, int flow) {
    		if (u == T)
    			return flow;
    		int minh = n - 1, ct = 0;
    		for (vector<Adj>::iterator it = adj[u].begin(); flow && it != adj[u].end(); ++it) {
    			if (it -> c) {
    				if (h[it -> v] + 1 == h[u]) {
    					int k = dfs(it -> v, min(it -> c, flow));
    					if (k) {
    						it -> c -= k;
    						adj[it -> v][it -> b].c += k;
    						flow -= k;
    						ct += k;
    					}
    					if (h[S] >= n)
    						return ct;
    				}
    				minh = min(minh, h[it -> v]);
    			}
    		}
    		if (ct)
    			return ct;
    		if (--cnt[h[u]] == 0)
    			h[S] = n;
    		h[u] = minh + 1;
    		++cnt[h[u]];
    		return 0;
    	}
    };
    
    struct wizard {
    	int NA, NB;
    	vector<int> A, B;
    
    	void input() {
    		scanf ("%d", &NA);
    		A.clear();
    		rep (i, NA) {
    			int bar;
    			scanf ("%d", &bar);
    			A.push_back(--bar);
    		}
    		scanf ("%d", &NB);
    		B.clear();
    		rep (i, NB) {
    			int bar;
    			scanf ("%d", &bar);
    			B.push_back(--bar);
    		}
    	}
    };
    
    const int MAXN = 200 + 2;
    const int MAXW = 50 + 2;
    
    wizard wizards[MAXW];
    graph g;
    int num[MAXN];
    int n, w;
    
    int get_level_id(int x, int y) {
    	return y * n + x + 2;
    }
    
    int solve() {
    	// build graph
    
    	// 0 : clear
    	g.clear();
    	int S = 0, T = 1;
    
    	// 1 : build level
    	rep (i, n) {
    		rep (j, w) {
    			g.insert (get_level_id(i, j), get_level_id(i, j + 1), graph::inf);
    		}
    	}
    	rep (i, n) {
    		if (num[i]) g.insert (S, get_level_id(i, 0), num[i]);
    		g.insert (get_level_id(i, w), T, 1);
    	}
    
    	// 2 : build transform edge
    	int vertex_cnt = get_level_id(n - 1, w) + 1;
    	map<int, int> in_vertex_id, out_vertex_id;
    	rep (i, w) {
    		rep (j, wizards[i].NA) {
    			g.insert (get_level_id(wizards[i].A[j], i), vertex_cnt, 1);
    			in_vertex_id[wizards[i].A[j]] = vertex_cnt++;
    		}
    		rep (j, wizards[i].NB) {
    			g.insert (vertex_cnt, get_level_id(wizards[i].B[j], i + 1), 1);
    			out_vertex_id[wizards[i].B[j]] = vertex_cnt++;
    		}
    		rep (j, wizards[i].NA) {
    			rep (k, wizards[i].NB) {
    				g.insert (in_vertex_id[wizards[i].A[j]], out_vertex_id[wizards[i].B[k]], 1);
    			}
    		}
    	}
    
    	return g.maxflow(S, T);
    }
    
    int main() {
    	while (scanf ("%d%d", &n, &w) != EOF) {
    		rep (i, n) {
    			scanf ("%d", &num[i]);
    		}
    		rep (i, w) {
    			wizards[i].input();
    		}
    
    		printf ("%d\n", solve());
    	}
    	return 0;
    }
    
    -2|
    Permalink
  • shehanjayalath
    3 years ago+ 0 comments

    C++ Solution

    #include <bits/stdc++.h>
    
    using namespace std;
    
    // Self Template Code BGEIN
    
    #define sz(x) ((int)((x).size()))
    #define out(x) printf(#x" %d\n", x)
    #define rep(i,n) for (int i = 0; i < (n); ++i)
    #define repf(i,a,b) for (int i = (a); i <= (b); ++i)
    #define repd(i,a,b) for (int i = (a); i >= (b); --i)
    #define repcase int t, Case = 1; for (scanf ("%d", &t); t; --t)
    #define repeach(i,x) for (__typeof((x).begin()) i = (x).begin(); i != (x).end(); ++i)
    
    typedef long long int64;
    typedef pair<int, int> pii;
    
    int sgn(double x) { return (x > 1e-8) - (x < -1e-8); }
    int count_bit(int x) { return x == 0? 0 : count_bit(x >> 1) + (x & 1); }
    
    template<class T> inline void ckmin(T &a, const T b) { if (b < a) a = b; }
    template<class T> inline void ckmax(T &a, const T b) { if (b > a) a = b; }
    
    // Self Template Code END
    
    struct graph {
    	static const int maxn = 50 * 30 * 2 + 200 * 30 + 10;
    	static const int inf = (-1u) >> 1;
    
    	struct Adj {
    		int v, c, b;
    		Adj(int _v, int _c, int _b): v(_v), c(_c), b(_b) {}
    		Adj() {};
    	};
    	int i, n, S, T, h[maxn], cnt[maxn];
    	vector <Adj> adj[maxn];
    	void clear() {
    		for (i = 0; i < n; ++i)
    			adj[i].clear();
    		n = 0;
    	}
    	void insert(int u, int v, int c, int d = 0) {
    		// printf ("insert %d %d %d\n", u, v, c);
    		n = max(n, max(u, v) + 1);
    		adj[u].push_back(Adj(v, c, adj[v].size()));
    		adj[v].push_back(Adj(u, c * d, adj[u].size() - 1));
    	}
    	int maxflow(int _S, int _T) {
    		S = _S, T = _T;
    		fill(h, h + n, 0);
    		fill(cnt, cnt + n, 0);
    		int flow = 0;
    		while (h[S] < n)
    			flow += dfs(S, inf);
    		return flow;
    	}
    	int dfs(int u, int flow) {
    		if (u == T)
    			return flow;
    		int minh = n - 1, ct = 0;
    		for (vector<Adj>::iterator it = adj[u].begin(); flow && it != adj[u].end(); ++it) {
    			if (it -> c) {
    				if (h[it -> v] + 1 == h[u]) {
    					int k = dfs(it -> v, min(it -> c, flow));
    					if (k) {
    						it -> c -= k;
    						adj[it -> v][it -> b].c += k;
    						flow -= k;
    						ct += k;
    					}
    					if (h[S] >= n)
    						return ct;
    				}
    				minh = min(minh, h[it -> v]);
    			}
    		}
    		if (ct)
    			return ct;
    		if (--cnt[h[u]] == 0)
    			h[S] = n;
    		h[u] = minh + 1;
    		++cnt[h[u]];
    		return 0;
    	}
    };
    
    struct wizard {
    	int NA, NB;
    	vector<int> A, B;
    
    	void input() {
    		scanf ("%d", &NA);
    		A.clear();
    		rep (i, NA) {
    			int bar;
    			scanf ("%d", &bar);
    			A.push_back(--bar);
    		}
    		scanf ("%d", &NB);
    		B.clear();
    		rep (i, NB) {
    			int bar;
    			scanf ("%d", &bar);
    			B.push_back(--bar);
    		}
    	}
    };
    
    const int MAXN = 200 + 2;
    const int MAXW = 50 + 2;
    
    wizard wizards[MAXW];
    graph g;
    int num[MAXN];
    int n, w;
    
    int get_level_id(int x, int y) {
    	return y * n + x + 2;
    }
    
    int solve() {
    	// build graph
    
    	// 0 : clear
    	g.clear();
    	int S = 0, T = 1;
    
    	// 1 : build level
    	rep (i, n) {
    		rep (j, w) {
    			g.insert (get_level_id(i, j), get_level_id(i, j + 1), graph::inf);
    		}
    	}
    	rep (i, n) {
    		if (num[i]) g.insert (S, get_level_id(i, 0), num[i]);
    		g.insert (get_level_id(i, w), T, 1);
    	}
    
    	// 2 : build transform edge
    	int vertex_cnt = get_level_id(n - 1, w) + 1;
    	map<int, int> in_vertex_id, out_vertex_id;
    	rep (i, w) {
    		rep (j, wizards[i].NA) {
    			g.insert (get_level_id(wizards[i].A[j], i), vertex_cnt, 1);
    			in_vertex_id[wizards[i].A[j]] = vertex_cnt++;
    		}
    		rep (j, wizards[i].NB) {
    			g.insert (vertex_cnt, get_level_id(wizards[i].B[j], i + 1), 1);
    			out_vertex_id[wizards[i].B[j]] = vertex_cnt++;
    		}
    		rep (j, wizards[i].NA) {
    			rep (k, wizards[i].NB) {
    				g.insert (in_vertex_id[wizards[i].A[j]], out_vertex_id[wizards[i].B[k]], 1);
    			}
    		}
    	}
    
    	return g.maxflow(S, T);
    }
    
    int main() {
    	while (scanf ("%d%d", &n, &w) != EOF) {
    		rep (i, n) {
    			scanf ("%d", &num[i]);
    		}
    		rep (i, w) {
    			wizards[i].input();
    		}
    
    		printf ("%d\n", solve());
    	}
    	return 0;
    }
    
    1|
    Permalink
  • hackerrank1034
    4 years ago+ 0 comments

    The sample output in the description is wrong! The correct output is 3 and not 2.

    The testcases contain the same example and there the output is correct.

    Also the formulation " the maximum number of distinct skill set that can the people of country learn" is very misleading. What is meant "the maximum number of distinct skill that are known by at least one person". This means you must count people that already knew a skill at the beginning and thus did not learn anything during the transformations.

    3|
    Permalink
  • minhazmiraz
    4 years ago+ 0 comments

    Why the output is 2. It must be 3.

    2|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy