HackerEarth Replace Assignment problem solution

In this HackerEarth Replace Assignment problem solution In this problem the word "set" will always denote a multiset (link to wikipedia). Thus, some of its elements can be the same. The order of elements doesn't matter. Multisets {a, a, a, b, c, b} and {a, b, c, a, b, a} are the same. Multisets {a, a, b} and {a, b, b} are different.

You have a set consisting of some elements. A set can either be empty, or contain other sets. Note that sets in this problem may contain multiple copies of the same set. More formally, a set satisfies the following context free grammar with start symbol S:

S -> {T}

T -> ST | ε

In this context free grammar, S denotes a set, while T denotes a list of the elements which are sets themselves. For example, valid sets are {}, {{}}, {{}{}}, {{}{{}{}}}.

We can define an element of a set to be one of the sets that make up the set. For example, a set {a, a, b} has three elements, that is a, a, and b. The set {} has no elements. The set {{}} has one element {}. The set {{}{{}{}}} has two elements {}, {{}{}}.

Two sets are said to the same if they have the same multiset of elements. Note that the order of elements in the sets doesn't matter. For example, the sets {{}{{}}} and {{{}}{}} are the same, but the sets {{}{}} and {{}} are different.

Call a set S transitive if x is an element of S, then all elements in x are elements of S as well.

For example, the empty set {} is transitive. The set {{}} is also transitive. However, the set S = {{{}}} is not transitive, as {{}} is an element of S, but {} is an element of {{}} but not of S. We can make it transitive by adding the element {} to the set to get the transitive set {{{}}{}}.

You’re given a string with n characters representing a set. You would like to make this set transitive with the minimum number of moves. In one move, you can either add an arbitrary set or remove an arbitrary element from S. You are not allowed to add or remove elements in sets that are elements of S. Compute the minimum number moves you need to make the set transitive.

HackerEarth Replace problem solution.

import java.io.*;
import java.util.*;

public class Replace {
  public static MaxFlow f;
  public static char[] c;
  public static int nidx;
  public static int curpos;
  public static HashSet<Integer> directChildren;
  public static HashSet<Integer> allSubsets;
  public static HashMap<String, Integer> mp;
  public static int hidx;
  public static int[] freq;
  
  public static int dfs(int node) {
    ArrayList<Integer> subhashes = new ArrayList<>();
    while (curpos < c.length && c[curpos] == '{') {
      ++curpos;
      subhashes.add(dfs(nidx++));
      assert c[curpos] == '}';
      ++curpos;
    }
    if (node == 0) {
      directChildren.addAll(subhashes);
      for (int x : subhashes) freq[x]++;
      return -1;
    }
    Collections.sort(subhashes);
    StringBuilder sb = new StringBuilder("!");
    for (int x : subhashes) {
      sb.append(x+"!");
    }
    String key = sb.toString();
    if (!mp.containsKey(key)) {
      for (int x : subhashes) f.add_edge(hidx, x, INF);
      mp.put(key, hidx++);
    }
    int hash = mp.get(key);
    allSubsets.add(hash);
    return hash;
  }
  public static void main (String[] args) {
    Scanner in = new Scanner (System.in);
    PrintWriter out = new PrintWriter (System.out, true);
    // flow graph:
    // for each subtree, create a node.
    // Connect parent to subtree with infinite capacity
    // If subtree is direct child, then connect to source to subtree with capacity equal to number of times it appears in as a direct child
    // Otherwise, connect source to subtree node with capacity 1.
    // The answer is the max flow in this graph (this is because any finite cut encodes the cost of a particular transitive set, and any transitive set can be encoded as a finite cut, so min cut will find the minimum cost).
    int t = in.nextInt();
    while(t-->0) {
      c = in.next().toCharArray();
      int n = c.length+2, m = 2*n;
      f = new MaxFlow(n,m);
      nidx = 0;
      curpos = 1;
      hidx = 0;
      directChildren = new HashSet<>();
      allSubsets = new HashSet<>();
      mp = new HashMap<>();
      freq = new int[n];
      dfs(nidx++);
      for (int x : allSubsets) {
        if (directChildren.contains(x)) {
          f.add_edge(n-1, x, freq[x]);
        } else {
          f.add_edge(x, n-2, 1);
        }
      }
      out.println(f.dinic(n-1,n-2));
    }
    out.close();
    System.exit(0);
  }
  
  public static long INF = 1 << 29;
  static class MaxFlow {
    public long[] flow, capa;
    public int[] now, level, eadj, eprev, elast;
    public int eidx, N, M;
    
    public MaxFlow(int nodes, int edges) {
      this.N = nodes;
      this.M = edges;
      
      flow = new long[2*M];
      capa = new long[2*M];
      eadj = new int[2*M];
      eprev = new int[2*M];
      elast = new int[N];
      level = new int[N];
      now = new int[N];
      Arrays.fill(elast, -1);
      eidx = 0;
    }
    
    public void add_edge(int a, int b, long 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++;
    }
  
    public long dinic(int source, int sink) {
      long res, flow = 0;
      while (bfs(source, sink)) {
        System.arraycopy(elast, 0, now, 0, N);
        while ((res = dfs(source, INF, sink)) > 0)
          flow += res;
      }
      return flow;
    }
  
    private 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 long dfs(int cur, long 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]) {
          long 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;
    }
  }
}

Second solution

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 1e9 + 5;

char sl[50123];
map<vector<int>, int> toHash;
set<int> descendants[50123];
int counter = 0;
int count_direct[50123];

void clear() {
  toHash.clear();
  for(int i = 0; i <= counter; ++i) {
    count_direct[i] = 0;
    descendants[i].clear();
  }
  counter = 0;
}

int rec(int & i) {
  assert(sl[i] == '{');
  vector<int> children;
  ++i;
  while(sl[i] == '{') children.push_back(rec(i));
  ++i;
  sort(children.begin(), children.end());
  if(toHash.count(children) == 0) {
    int my_id = ++counter;
    toHash[children] = my_id;
    set<int> & my_set = descendants[my_id];
    for(int child : children) {
      my_set.insert(child);
      for(int descen : descendants[child])
        my_set.insert(descen);
    }
  }
  return toHash[children];
}

void te() {
  scanf("%s", sl);
  for(int i = 1; i < (int) strlen(sl) - 1;)
    ++count_direct[rec(i)];
  int ans = inf;
  
  vector<int> direct;
  for(int i = 0; i <= counter; ++i)
    if(count_direct[i] > 0)
      direct.push_back(i);
  int n = direct.size();
  printf("%d\n", n);
  for(int mask = 0; mask < (1 << n); ++mask) {
    set<int> needed;
    int removed = 0;
    for(int i = 0; i < n; ++i) {
      int my_id = direct[i];
      if(mask & (1 << i)) {
        // we don't remove it
        for(int a : descendants[my_id])
          needed.insert(a);
        needed.insert(my_id);
      }
      else removed += count_direct[my_id];
    }
    ans = min(ans, removed + int(needed.size()) - __builtin_popcount(mask));
  }
  
  printf("%d\n", ans);
  assert(ans != inf);
  clear();
}

int main() {
  int z;
  scanf("%d", &z);
  while(z--) te();
  return 0;
}