HackerRank Training the army Problem Solution

HackerRank Training the army Problem Solution

Yashwant Parihar,

In this post, we will solve 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 C, people possessing ith skill set, where i Є [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 A to one of the final skill set which belongs to the list B. That is, if A = [2,3,6] and B = [1,2] then following transformation can be done by that trainer.
2 →1
2 →2
3 →1
3 →2
6 →1
6 →2
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 transformation which results into maximum number of skill set with non-zero number of people knowing it.
Input Format
The first line contains two numbers, N T. where N represent the number of skill set and T represent the number of wizards.
Next line contains N space separated integers, C1 C2 … CN. where C, represents the number of people with ith skill. Then follows 2 x T lines, where each pair of line represent the configuration of each wizard.
First line of the pair will start with the length of list A and followed by list A in the same line. Similarly second line of the pair starts with the length of list B and then the list B.

Output Format

The output must consist of one number, the maximum number of distinct skill set that can the people of country learn, after making optimal transformation steps.

Sample Input

3 3
3 0 0
1 1
2 2 3
1 2
1 3
1 1
1 2

Sample Output

2

Explanation
There are 3 types of skill sets present along with 3 wizards. Initially, all three people know the 1st skill set but no one knows the 2nd and 3rd skill sets.
The 1st wizard’s initial lists are: A = [1] and B = [2, 3]. Suppose, he performs 1 → 2 transformation one any one of person with the 1st skill set, then it’s list A will be updated to an empty list [] and list B will be [3].
Now, we have two people knowing the 1st skill set and one person knowing the 2nd skill set.
The 3rd wizard’s initial lists are: A = [1] and B = [2]. He will use the transformation 1 → 2 one of the person with the 1st skill set, then it’s lists will also be updated to an empty lists A: [ and B: [].
Now, we have 1 person with 1st skillset and and 2 people knowing the 2nd skillset.
The 2nd wizard’s initial lists are: A = [2] and B = [3]. He will transform one of the person with 2nd skillset to 3rd one using the transformation 2 → 3. It’s lists will also be updated to an empty lists A: [] and B: [].
At this point, no further transformations are possible and we have achieved our maximum possible answer. Thus, each of the skill set, is known by 1 person.. This means there are three skill sets available in the kingdom.

HackerRank Training the army Problem Solution
HackerRank Training the army Problem Solution

Training the army C 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;
}

Training the army 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;
}

Training the army C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Diagnostics;

class Solution {
    
    public class Wizard
    {
        public int Key;
        public List<int> from = new List<int>();
        public List<int> to = new List<int>();
        public Wizard GetCopy()
            {
                var result = new Wizard();
                result.Key = Key;
                var tempFrom = new int[from.Count];
                from.CopyTo(tempFrom);
                var tempTo = new int[to.Count];
                to.CopyTo(tempTo);
                result.from = new List<int>(tempFrom);
                result.to = new List<int>(tempTo);
                return result;
            }
    }

    private static void ReplaceSkill(Dictionary<int, int> skillsDict, int skillId, Wizard wizard, int skillFromId)
    {
        //Replace skill
        wizard.from.Remove(skillFromId);
        wizard.to.Remove(skillId);

        skillsDict[skillFromId]--;
        skillsDict[skillId]++;
    }

    static int Max(int[] peopleSkills, List<Wizard> wizards, bool opt)
    {
        //Find optimal skill transformations to have maximum number off skills in people
        var totalNumberOfPeople = peopleSkills.Sum();
        var skillsDict = peopleSkills.Select((num, index) => new { index = index + 1, value = num }).ToDictionary(x => x.index, x => x.value);
        var failedSkills = skillsDict.Where(x => x.Value == 0 && wizards.All(w => w.to.Contains(x.Key) == false)).ToDictionary(x => x.Key, x => x.Value);

        var repeatedSkills = skillsDict.Where(x => x.Value > 0 && wizards.Any(w => w.to.Contains(x.Key)) ).ToDictionary(x => x.Key, x => wizards.Where(w => w.to.Contains(x.Key)));

        var availablePeople = skillsDict.Where(x => x.Value >= 1).ToDictionary(x => x.Key, x => x.Value);
        var availablePeople2 = skillsDict.Where(x => x.Value == 1).ToDictionary(x => x.Key, x => x.Value);
        var availablePeopleAll = skillsDict.Where(x => x.Value >= 1).ToDictionary(x => x.Key, x => x.Value);

        var megaLoop = skillsDict.Where(x => failedSkills.ContainsKey(x.Key) == false && x.Value == 0).ToDictionary(x => x.Key,
                                x => wizards.Where(w => w.to.Contains(x.Key) && w.from.Any(f => availablePeople.Keys.Contains(f)))
                                ).OrderBy(x => Math.Min(x.Value.Sum(z => z.from.Count), x.Value.Sum(c => c.to.Count)));

        var loopEnded = false;
        while (loopEnded == false)
        {
            loopEnded = true;

            availablePeople = skillsDict.Where(x => x.Value >= 1).ToDictionary(x => x.Key, x => x.Value);
            megaLoop = skillsDict.Where(x => failedSkills.ContainsKey(x.Key) == false && x.Value == 0).ToDictionary(x => x.Key,
                                    x => wizards.Where(w => w.to.Contains(x.Key) && w.from.Any(f => availablePeople.Keys.Contains(f)))
                                    ).OrderBy(x => Math.Min(x.Value.Sum(z => z.from.Count), x.Value.Sum(c => c.to.Count)));
            Debug.WriteLine("Starting megaLoop:" + megaLoop.Count());
            foreach (var skill in megaLoop)
            {
                //Find wizard and person for transformation to that skill
                //Available with skills to trade > 1
                availablePeople = skillsDict.Where(x => x.Value > 1).ToDictionary(x=>x.Key, x=>x.Value);
                availablePeople2 = skillsDict.Where(x => x.Value == 1).ToDictionary(x => x.Key, x => x.Value);
                availablePeopleAll = skillsDict.Where(x => x.Value >= 1).ToDictionary(x => x.Key, x => x.Value);

                var wizards0 = skill.Value.OrderBy(x=>x.from.Count).ToArray();

                var wizards1 = wizards.Where(x => x.to.Contains(skill.Key) &&
                                                        x.from.Any(z => availablePeople.Keys.Contains(z))).ToArray();

                
                var wizards2 = wizards.Where(x => x.to.Contains(skill.Key) &&
                                                    x.from.Any(z => availablePeople2.Keys.Contains(z))).ToArray();

                var wizard = wizards0.FirstOrDefault();
                if (wizard != null)
                {
                    var nextSkills = megaLoop.Where(x => skillsDict[x.Key] == 0 && x.Key != skill.Key && x.Value.Contains(wizard) == false).Select(x => x.Key).ToArray();
                    var availableFroms = wizard.from.Where(x => availablePeople.Keys.Contains(x))
                                .ToDictionary(x => x,
                                    x => wizards.Where(z => z.from.Contains(x) && z.to.Any(s => nextSkills.Contains(s)) && wizard != z).Sum(w =>
                                                                        (w.to.Count(s => nextSkills.Contains(s))) 
                                                                        ));
                    if (availableFroms.Count() == 0)
                    {
                        availableFroms = wizard.from.Where(x => availablePeopleAll.Keys.Contains(x))
                                .ToDictionary(x => x,
                                    x => wizards.Count(z => z.to.Contains(x)) + (skillsDict[x] - 1));
                    }

                    var takeFromSkillId = availableFroms.OrderBy(x => x.Value).First().Key;
                    ReplaceSkill(skillsDict, skill.Key, wizard, takeFromSkillId);

                    loopEnded = false;
                    //break;
                }
                else 
                {
                    if (opt)
                        continue;

                    //Case
                    if (wizards2.Count() == 0)
                    {
                        wizards2 = wizards.Where(x => x.to.Contains(skill.Key)).ToArray();
                    }

                    //Find substrasformations to fix this one?
                    foreach (var wizard2 in wizards2.OrderBy(x => x.to.Count()))
                    {
                        var nextSkills = megaLoop.Where(x => skillsDict[x.Key] == 0 && x.Key != skill.Key && x.Value.Contains(wizard2) == false).Select(x => x.Key).ToArray();
                        /*
                        var availableFroms = wizard2.from.Where(x => availablePeople2.Keys.Contains(x))
                                .ToDictionary(x => x,
                                    x => wizards.Count(z => z.to.Contains(x)) + (skillsDict[x] - 1))
                                .OrderByDescending(x => x.Value);
                        */
                        var availableFroms = wizard2.from.Where(x => skillsDict.Keys.Contains(x))
                                .ToDictionary(x => x,
                                    x => wizards.Where(z => z.from.Contains(x) && z.to.Any(s => nextSkills.Contains(s)) && wizard2 != z).Sum(w =>
                                                                        (w.to.Count(s => nextSkills.Contains(s)))
                                                                        //(skillsDict[x] - 1)
                                                                        ));

                        if(availableFroms.Count == 0)
                        {
                            var wizSkills = new List<int>(wizard2.from).ToArray();
                            availableFroms = wizard2.from.Where(x => skillsDict.Keys.Contains(x))
                                .ToDictionary(x => x,
                                    x => wizards.Where(z => z.from.Contains(x) && z.to.Any(s => wizSkills.Contains(s)) && wizard2 != z).Sum(w =>
                                                                        (w.to.Count(s => wizSkills.Contains(s)))
                                                                        //(skillsDict[x] - 1)
                                                                        ));
                        }

                        var replaced = false;
                        foreach (var skillFromId in availableFroms.OrderBy(x=>x.Value))//.Where(x=> x.Value > 0))
                        {
                            var wizardsToRestoreMissingSkill = wizards.Where(x => x.to.Contains(skillFromId.Key) && x.from.Any(s => availablePeople.ContainsKey(s)));
                            if (wizardsToRestoreMissingSkill.Count() == 0)
                            {
                                //Alarm, we can not replace this one...
                                Debug.WriteLine(@"Failed skill {0}:{1}>{2} attemp to use:{3} wizard:{4}", skill.Key, skill.Value.Count(), skillsDict[skill.Key], skillFromId.Key, wizard2.Key);
                            }
                            else
                            {
                                //Double check if from skill available...
                                ReplaceSkill(skillsDict, skill.Key, wizard2, skillFromId.Key);
                                loopEnded = false;
                                replaced = true;

                                //Replace wizards
                                if (skillsDict[skillFromId.Key] < 0)
                                {
                                    var wizSel = wizardsToRestoreMissingSkill.ToDictionary(x => x,
                                                                                    x => x.from.Where(z=> availablePeople.ContainsKey(z)).Sum(z=> availablePeople[z]));
                                    var done = false;
                                    foreach (var wizard3 in wizSel.OrderBy(x=>x.Value))
                                    {
                                        var availableFroms3 = wizard3.Key.from.Where(x => availablePeople.Keys.Contains(x))
                                            .ToDictionary(x => x,
                                                x => wizards.Where(z => z.from.Contains(x) && z.to.Any(s => nextSkills.Contains(s)) && wizard2 != z).Sum(w =>
                                                                                    (w.to.Count(s => nextSkills.Contains(s)))
                                                                                    ));
                                        foreach (var item in availableFroms3)
                                        {
                                            ReplaceSkill(skillsDict, skillFromId.Key, wizard3.Key, item.Key);
                                            done = true;
                                            break;
                                        }
                                        if (done)
                                        {
                                            break;
                                        }
                                    }
                                }
                                break;
                            }
                        }
                        if (replaced)
                        {
                            break;
                        }
                    }

                }
            }

            Debug.WriteLine("MegaLoop ends");
        }

        //Try to replace some from by adding extra
        availablePeople = skillsDict.Where(x => x.Value > 1).ToDictionary(x => x.Key, x => x.Value);
        megaLoop = skillsDict.Where(x => failedSkills.ContainsKey(x.Key) == false && x.Value == 0).ToDictionary(x => x.Key,
                                x => wizards.Where(w => w.from.Count > 0 && w.to.Contains(x.Key) )
                                ).OrderBy(x => Math.Min(x.Value.Sum(z => z.from.Count), x.Value.Sum(c => c.to.Count)));

        var anyAwailableWizards = wizards.Where(x => x.to.Count > 0 && x.from.Any(from => availablePeople.ContainsKey(from)));
        var megaLoopChain = megaLoop.ToDictionary(x => x.Key, x => new List<Wizard>());

        availablePeople = skillsDict.Where(x => x.Value > 1).ToDictionary(x => x.Key, x => x.Value);
        foreach (var skill in megaLoop)
        {
            //Find chain of wizards to get needed skill...
            var Chain = new List<int>();
            foreach (var wizard in skill.Value)
            {
                //WizFrom -> not in available list -> find wizard to replace
                //Find chain from available wizards to wanted wizard froms
                var targetFroms = new List<int>(wizard.from).ToArray();

                var unlockChain = UnlockWizards(wizards, anyAwailableWizards, targetFroms);
                if(unlockChain.Count > 0)
                {
                    //good?
                    unlockChain.Add(wizard);
                    megaLoopChain[skill.Key] = unlockChain;

                    var lastTo = 0;
                    //Replace straight?
                    for (int i = 0; i < unlockChain.Count - 1; i++)
                    {
                        availablePeople = skillsDict.Where(x => x.Value > 1).ToDictionary(x => x.Key, x => x.Value);

                        var wiz1 = unlockChain[i];
                        var wiz2 = unlockChain[i + 1];

                        var skillFrom = wiz1.from.FirstOrDefault(x => availablePeople.ContainsKey(x));
                        lastTo = wiz1.to.FirstOrDefault(x => wiz2.from.Contains(x));
                        if (skillFrom > 0 && lastTo > 0)
                        {
                            //Replace...
                            ReplaceSkill(skillsDict, lastTo, wiz1, skillFrom);
                        }
                        else
                        {
                            break;
                        }
                    }

                    //target skill
                    ReplaceSkill(skillsDict, skill.Key, wizard, lastTo);
                }
            }
        }

        return skillsDict.Count(x => x.Value > 0);
    }
    
    private static List<Wizard> UnlockWizards(List<Wizard> wizards, IEnumerable<Wizard> anyAwailableWizards, int[] wizSkillsFrom)
    {
        foreach (var availableWiz in anyAwailableWizards)
        {
            var result = new List<Wizard>();
            result.Add(availableWiz);
            //wizard can change skills
            //find skills to unlock other wizards?
            var wizardsToUnlock = wizards.Where(x => x != availableWiz && x.to.Count > 0 && x.from.Any(f => availableWiz.to.Contains(f)));
            var wizardFound = wizardsToUnlock.FirstOrDefault(f => f.to.Any(s => wizSkillsFrom.Contains(s)));
            if (wizardFound == null && wizardsToUnlock.Count() > 0)
            {
                //Try to unlock more wizards
                var next = UnlockWizards(wizards, wizardsToUnlock, wizSkillsFrom);
                if(next.Count > 0)
                {
                    return next;
                }
            }
            if (wizardFound != null)
            {
                // Return this one...
                //result.Add(availableWiz);
                result.Add(wizardFound);
                return result;
            }
        }
        return new List<Wizard>() ;
    }
    
    static int MaxSkills(int[] peopleSkills, List<Wizard> wizards)
    {
        var a = Max(peopleSkills, wizards.Select(x=>x.GetCopy()).ToList(), true);
        var b = Max(peopleSkills, wizards.Select(x => x.GetCopy()).ToList(), false);
        return Math.Max(a, b);
    }
    
    static void Main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution */
        
        var line = Console.ReadLine().Split(' ');
        var N = int.Parse(line[0]);
        var T = int.Parse(line[1]);
        var peopleSkills = Console.ReadLine().Split(' ').Select(x=>(int.Parse(x))).ToArray();

        var wizardsList = new List<Wizard>();
        for (int i = 0; i < T; i++)
        {
            var wizardFrom = Console.ReadLine().Split(' ').Skip(1).Select(x => (int.Parse(x))).ToList();
            var wizardTo = Console.ReadLine().Split(' ').Skip(1).Select(x => (int.Parse(x))).ToList();
            wizardsList.Add(new Wizard() { from = wizardFrom, to = wizardTo });
        }

        var result = MaxSkills(peopleSkills, wizardsList);
        Console.WriteLine(result);
    }
}

Training the army Java Solution

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();
        }
    }
}

Training the army JavaScript Solution

'use strict'


/** v1 using DFS with quite a bit of pruning,
 * but during implementation it became obvious this wouldn't cut it,
 * and that using a network flow algorithm would be a good fit

let max_skills;
let max_possible_skills;

function processData(input) {
    const lines = input.split('\n');
    
    const first_line = parse(lines[0]);
    const N = first_line[0];
    const T = first_line[1];
    const initial_skills = parse(lines[1]);
    
    const initial_wizards = [];
    for (let i = 0; i < T; i++) {
        let A = parse(lines[i*2+2]);
        A.shift();
        let B = parse(lines[i*2+3]);
        B.shift();
        
        initial_wizards.push([ A.map(x => x-1), B.map(x => x-1) ]);
    }

    log(0, initial_wizards);
    const pruned_wizards = prune_wizards(initial_wizards, initial_skills);
    log(0, pruned_wizards);

    let num_skills = 0;
    for (const s of initial_skills) {
        if (s > 0) num_skills++;
    }
    max_skills = num_skills;

    // Compute the maximum possible moves
    let max_moves = 0;
    for (const wizard of pruned_wizards) {
        max_moves += Math.min(wizard[0].length, wizard[1].length);
    }
    max_possible_skills = num_skills + max_moves;


    log(0, num_skills, max_possible_skills, initial_skills);
    log(0, '-----------------------------------------');
    
    recurse(0, pruned_wizards, initial_skills, num_skills);
    
    log(0, '** Final Answer **');
    console.log(max_skills);
}

function recurse(depth, wizards, skills, num_skills) {
    if (max_skills >= max_possible_skills) return;

    for (let iw = 0; iw < wizards.length; iw++) {
        const wizard = wizards[iw];
        for (let ia = 0; ia < wizard[0].length; ia++) {
            let a = wizard[0][ia];
            if (a === -1) continue;
            for (let ib = 0; ib < wizard[1].length; ib++) {
                let b = wizard[1][ib];
                if (b === -1 || a === b || skills[a] === 0 || skills[b] > 0) continue;

                wizard[0][ia] = -1;
                wizard[1][ib] = -1;
                skills[a]--;
                skills[b]++;
                if (skills[a] === 0) num_skills--;
                if (skills[b] === 1) num_skills++;
                if (num_skills > max_skills) max_skills = num_skills;

                log(depth, iw, a, b, wizards);
                log(depth, num_skills, skills);
                recurse(depth+1, wizards, skills, num_skills);
                
                // Undo everything before the recurse
                wizard[0][ia] = a;
                wizard[1][ib] = b;
                skills[a]++;
                skills[b]--;
                if (skills[a] === 1) num_skills++;
                if (skills[b] === 0) num_skills--;
            }
        }
    }
}
*/

/** v2 uses a max network flow algorithm (Ford-Fulkerson)
 * I've kept the pruning from v1 since it worked really well.
 */
function processData(input) {
    const lines = input.split('\n');
    
    const first_line = parse(lines[0]);
    const N = first_line[0];
    const T = first_line[1];
    const skills = parse(lines[1]);
    
    let wizards = [];
    for (let i = 0; i < T; i++) {
        let A = parse(lines[i*2+2]);
        A.shift();
        let B = parse(lines[i*2+3]);
        B.shift();
        
        wizards.push([ A.map(x => x-1), B.map(x => x-1) ]);
    }

    log(0, wizards);
    wizards = prune_wizards(wizards, skills);
    log(0, wizards);

    // Initialize the graph
    const graph = [];
    const size = 1 + skills.length + wizards.length + 1;
    for (let i = size-1; i >= 0; i--) {
        const row = [];
        for (let j = size-1; j >= 0; j--) row[j] = 0;
            graph.push(row);
    }

    // Define the network
    for (let i = 0; i < skills.length; i++) {
        graph[0][i+1] = skills[i];
        graph[i+1][size-1] = 1;
    }

    for (let i = 0; i < wizards.length; i++) {
        for (let j = 0; j < wizards[i][0].length; j++) {
            graph[wizards[i][0][j]+1][i+skills.length+1] = 1;
        }
        for (let j = 0; j < wizards[i][1].length; j++) {
            graph[i+skills.length+1][wizards[i][1][j]+1] = 1;
        }
    }

    log(0, graph);

    // Find max flow
    let max = fordFulkerson(graph, 0, size-1);
    log(0, '** Final Answer **');
    console.log(max);
}

function prune_wizards(wizards, skills) {
    // Remove any skills from wizards' A if they will always be 0
    // Loop over this process while removing wizards with empty A or B sets
    let num_wizards;
    do {
        const zeros = new Set();
        num_wizards = wizards.length;

        for (let i = 0; i < skills.length; i++) {
            if (skills[i] === 0) {
                zeros.add(i);
            }
        }
        for (const wizard of wizards) {
            for (const b of wizard[1]) {
                zeros.delete(b);
            }
        }
        for (const wizard of wizards) {
            wizard[0] = wizard[0].filter(item => !zeros.has(item));
        }
        wizards = wizards.filter(wiz => wiz[0].length > 0 && wiz[1].length > 0);

    } while (wizards.length !== num_wizards);

    return wizards;
}

function parse(line) {
    return line.split(' ').map(f => parseInt(f));
}

function log(depth, ...message) {
    if (false) console.log(' '.repeat(depth*3), ...message);
}


process.stdin.resume();
process.stdin.setEncoding("ascii");
let _input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});




// from https://github.com/prabod/Graph-Theory-Ford-Fulkerson-Maximum-Flow
function bfs(rGraph, s, t, parent) {
    var visited = [];
    var queue = [];
    var V = rGraph.length;
    // Create a visited array and mark all vertices as not visited
    for (var i = 0; i < V; i++) {
        visited[i] = false;
    }
    // Create a queue, enqueue source vertex and mark source vertex as visited
    queue.push(s);
    visited[s] = true;
    parent[s] = -1;

    while (queue.length != 0) {
        var u = queue.shift();
        for (var v = 0; v < V; v++) {
            if (visited[v] == false && rGraph[u][v] > 0) {
                queue.push(v);
                parent[v] = u;
                visited[v] = true;
            }
        }
    }
    //If we reached sink in BFS starting from source, then return true, else false
    return (visited[t] == true);
}

function fordFulkerson(graph, s, t) {
    /* Create a residual graph and fill the residual graph
     with given capacities in the original graph as
     residual capacities in residual graph

     Residual graph where rGraph[i][j] indicates
     residual capacity of edge from i to j (if there
     is an edge. If rGraph[i][j] is 0, then there is
     not)
    */
  if (s < 0 || t < 0 || s > graph.length-1 || t > graph.length-1){
    throw new Error("Ford-Fulkerson-Maximum-Flow :: invalid sink or source");
  }
  if(graph.length === 0){
    throw new Error("Ford-Fulkerson-Maximum-Flow :: invalid graph");
  }
    var rGraph = [];
    for (var u = 0; u < graph.length; u++) {
        var temp = [];
    if(graph[u].length !== graph.length){
      throw new Error("Ford-Fulkerson-Maximum-Flow :: invalid graph. graph needs to be NxN");
    }
        for (v = 0; v < graph.length; v++) {
            temp.push(graph[u][v]);
        }
        rGraph.push(temp);
    }
    var parent = [];
    var maxFlow = 0;

    while (bfs(rGraph, s, t, parent)) {
        var pathFlow = Number.MAX_VALUE;
        for (var v = t; v != s; v = parent[v]) {
            u = parent[v];
            pathFlow = Math.min(pathFlow, rGraph[u][v]);
        }
        for (v = t; v != s; v = parent[v]) {
            u = parent[v];
            rGraph[u][v] -= pathFlow;
            rGraph[v][u] += pathFlow;
        }


        maxFlow += pathFlow;
    }
    // Return the overall flow
    return maxFlow;
}

Training the army Python 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 C# C++ HackerRank Solutions java javascript python