HackerRank Black and White Tree Problem Solution

HackerRank Black and White Tree Solution

Yashwant Parihar,

In this post, we will solve HackerRank Black and White Tree Problem Solution.

Nikita is making a graph as a birthday gift for her boyfriend, a fellow programmer! She drew an undirected connected graph with N nodes numbered from 1 to N in her notebook. Each node is shaded in either white or black. We define ny to be the number of white nodes, and no to be the number of black nodes. The graph is drawn in such a way that:

  • No 2 adjacent nodes have same coloring.
  • The value of nw – np. which we’ll call D, is minimal.

Nikita’s mischievous little brother erased some of the edges and all of the coloring from her graph! As a result, the graph is now decomposed into one or more components. Because you’re her best friend, you’ve decided to help her reconstruct the graph by adding K edges such that the aforementioned graph properties hold true.
Given the decomposed graph, construct and shade a valid connected graph such that the difference nw – ng between its shaded nodes is minimal.
Input Format
The first line contains 2 space-separated integers, N (the number of nodes in the original graph) and M (the number of edges in the decomposed graph), respectively. The M subsequent lines each contain 2 space-separated integers, u and v, describing a bidirectional edge between nodes u and v in the decomposed graph.

Output Format
You must have K + 1 lines of output. The first line contains 2 space-separated integers: D (the minimum possible value of ng-nw) and K (the number of edges you’ve added to the graph), respectively.
Each of the K subsequent lines contains 2 space-separated integers, u and v. describing a newly-added bidirectional edge in your final graph (i.e.: new edge u <> v).
You may print any 1 of the possible reconstructions of Nikita’s graph such that the value of
D in the reconstructed shaded graph is minimal.

Sample Input 0

 8 8
 1 2
 2 3
 3 4
 4 1
 1 5
 2 6
 3 7
 4 8

Sample output 0

0 0

Sample Input 1

 8 6
 1 2
 3 4
 3 5
 3 6
 3 7
 3 8

Sample Output 1

4 1
1 5

Sample Input 2

 5 4
 1 2
 2 3
 3 4
 4 1

Sample Output 2

  1 2
  2 5
  4 5

Explanation

In the figure below, the solid lines show the decomposed graph after Nikita’s brother erased the edges, and the dotted lines show one possible correct answer:

In Sample 0, no additional edges are added and K = 0. Because nw = 4 and np = 4, we get nw ng = 0. Thus, we print o o on a new line (there is only 1 line of output, as – K = 0).
In Sample 1. the only edge added is (5, 1), so K = 1. Here, nw = 6 and np = 2,50 nw ng = 4. Thus, we print 4 1 on the first line. Next, we must print K lines describing each edge added; because K = 1, we print a single line describing the 2 space-separated nodes connected by our new edge: 1 5.
In Sample 2, we can either add 1 edge (2,5) or (4, 5), or both of them. In both cases we get nw = 2 and np = 3, so nw ng = 1. Thus D = 1 and K = 1 or 2 both are correct.

HackerRank Black and White Tree Problem Solution
HackerRank Black and White Tree Problem Solution

Black and White Tree C Solution

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define HASH_SIZE 1234555
typedef struct _node{
  int t;
  int i;
  int c;
  int a;
  struct _node *next;
} node;
typedef struct _lnode{
  int x;
  int w;
  struct _lnode *next;
} lnode;
int abss(int x);
void insert_edge(int x,int y,int w);
void dfs(int x,int c);
void sort_a2(int*a,int*b,int size);
void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int left_size, int right_size);
void sort_a_ad(int*a,int*c,int size,int*new_size);
void merge_ad(int*a,int*left_a,int*right_a,int*c,int*left_c,int*right_c,int left_size, int right_size,int*new_size);
void insert(int target,int idx,int c,int a);
int search(int target,int idx,int *c);
int solve(int target,int target2,int idx);
void clean_table();
int N,w,b,ngs,*cans,*cdiff,*c,idx[200000],*trace,mark[200000]={0},diff[200000],f[200000],s[200000],*remain;
lnode **table;
node *hash[HASH_SIZE]={0};

int main(){
  int M,x,y,gs,sum,ans,target,i,j,k;
  scanf("%d%d",&N,&M);
  table=(lnode**)malloc(N*sizeof(lnode*));
  memset(table,0,N*sizeof(lnode*));
  for(i=0;i<M;i++){
    scanf("%d%d",&x,&y);
    insert_edge(x-1,y-1,1);
  }
  trace=(int*)malloc(N*sizeof(int));
  memset(trace,0,N*sizeof(int));
  for(i=gs=0;i<N;i++)
    if(!trace[i]){
      w=b=0;
      dfs(i,0);
      x=i;
      if(table[i])
        y=table[i]->x;
      else
        y=-1;
      if(w>b){
        diff[gs]=w-b;
        f[gs]=x;
        s[gs]=y;
      }
      else{
        diff[gs]=b-w;
        f[gs]=y;
        s[gs]=x;
      }
      idx[gs]=gs;
      gs++;
    }
  free(trace);
  clean_table();
  free(table);
  cdiff=(int*)malloc(gs*sizeof(int));
  c=(int*)malloc(gs*sizeof(int));
  for(i=sum=0,ans=200001;i<gs;i++){
    sum+=diff[i];
    cdiff[i]=diff[i];
    c[i]=1;
  }
  target=sum/2;
  sort_a2(diff,idx,gs);
  sort_a_ad(cdiff,c,gs,&ngs);
  remain=(int*)malloc(ngs*sizeof(int));
  if(!M || ngs==1){
    printf("%d %d\n",gs%2*cdiff[0],gs-1);
    for(i=0;i<gs-1;i++)
      printf("%d %d\n",f[i]+1,f[i+1]+1);
    return 0;
  }
  for(i=0;i<ngs;i++)
    if(i==0)
      remain[i]=c[i]*cdiff[i];
    else
      remain[i]=remain[i-1]+c[i]*cdiff[i];
  ans=solve(target,(sum+1)/2,ngs-1);
  cans=remain;
  memset(cans,0,ngs*sizeof(int));
  for(i=ngs-1;i>=0;i--){
    if(target<=0)
      break;
    if(i==0){
      cans[i]=(target-1)/cdiff[i]+1;
      break;
    }
    search(target,i,&cans[i]);
    if(cans[i]==-1){
      for(j=i;j>=0;j--)
        cans[j]=c[j];
      break;
    }
    target-=cans[i]*cdiff[i];
  }
  for(j=0,k=0;j<gs && k<ngs;k++){
    x=j+cans[k];
    for(;j<x;j++)
      mark[j]=1;
    while(diff[j]==cdiff[k] && j<gs)
      j++;
  }
  printf("%d %d\n",abss(2*ans-sum),gs-1);
  for(i=0;i<gs;i++)
    if(s[idx[i]]!=-1)
      k=i;
  for(i=0;i<gs;i++){
    if(i==k)
      continue;
    if(mark[i]!=mark[k])
      printf("%d %d\n",f[idx[i]]+1,f[idx[k]]+1);
    else
      printf("%d %d\n",f[idx[i]]+1,s[idx[k]]+1);
  }
  return 0;
}
int abss(int x){
  return (x<0)?-x:x;
}
void insert_edge(int x,int y,int w){
  lnode *t=malloc(sizeof(lnode));
  t->x=y;
  t->w=w;
  t->next=table[x];
  table[x]=t;
  t=malloc(sizeof(lnode));
  t->x=x;
  t->w=w;
  t->next=table[y];
  table[y]=t;
  return;
}
void dfs(int x,int c){
  lnode *p;
  trace[x]=1;
  if(c)
    b++;
  else
    w++;
  for(p=table[x];p;p=p->next)
    if(!trace[p->x])
      dfs(p->x,c^1);
  return;
}
void sort_a2(int*a,int*b,int size){
  if (size < 2)
    return;
  int m = (size+1)/2,i;
  int*left_a,*left_b,*right_a,*right_b;
  left_a=(int*)malloc(m*sizeof(int));
  right_a=(int*)malloc((size-m)*sizeof(int));
  left_b=(int*)malloc(m*sizeof(int));
  right_b=(int*)malloc((size-m)*sizeof(int));
  for(i=0;i<m;i++){
    left_a[i]=a[i];
    left_b[i]=b[i];
  }
  for(i=0;i<size-m;i++){
    right_a[i]=a[i+m];
    right_b[i]=b[i+m];
  }
  sort_a2(left_a,left_b,m);
  sort_a2(right_a,right_b,size-m);
  merge2(a,left_a,right_a,b,left_b,right_b,m,size-m);
  free(left_a);
  free(right_a);
  free(left_b);
  free(right_b);
  return;
}
void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int left_size, int right_size){
  int i = 0, j = 0;
  while (i < left_size|| j < right_size) {
    if (i == left_size) {
      a[i+j] = right_a[j];
      b[i+j] = right_b[j];
      j++;
    } else if (j == right_size) {
      a[i+j] = left_a[i];
      b[i+j] = left_b[i];
      i++;
    } else if (left_a[i] <= right_a[j]) {
      a[i+j] = left_a[i];
      b[i+j] = left_b[i];
      i++;
    } else {
      a[i+j] = right_a[j];
      b[i+j] = right_b[j];
      j++;
    }
  }
  return;
}
void sort_a_ad(int*a,int*c,int size,int*new_size){
  if (size < 2){
    (*new_size)=size;
    return;
  }
  int m = (size+1)/2,i;
  int *left_a,*right_a,*left_c,*right_c;
  left_a=(int*)malloc(m*sizeof(int));
  right_a=(int*)malloc((size-m)*sizeof(int));
  left_c=(int*)malloc(m*sizeof(int));
  right_c=(int*)malloc((size-m)*sizeof(int));
  for(i=0;i<m;i++){
    left_a[i]=a[i];
    left_c[i]=c[i];
  }
  for(i=0;i<size-m;i++){
    right_a[i]=a[i+m];
    right_c[i]=c[i+m];
  }
  int new_l_size=0,new_r_size=0;
  sort_a_ad(left_a,left_c,m,&new_l_size);
  sort_a_ad(right_a,right_c,size-m,&new_r_size);
  merge_ad(a,left_a,right_a,c,left_c,right_c,new_l_size,new_r_size,new_size);
  free(left_a);
  free(right_a);
  free(left_c);
  free(right_c);
  return;
}
void merge_ad(int*a,int*left_a,int*right_a,int*c,int*left_c,int*right_c,int left_size, int right_size,int*new_size){
  int i = 0, j = 0,index=0;
  while (i < left_size|| j < right_size) {
    if (i == left_size) {
      c[index] = right_c[j];
      a[index++] = right_a[j];
      j++;
    } else if (j == right_size) {
      c[index] = left_c[i];
      a[index++] = left_a[i];
      i++;
    } else if (left_a[i] <= right_a[j]) {
      c[index] = left_c[i];
      a[index++] = left_a[i];
      i++;
    } else {
      c[index] = right_c[j];
      a[index++] = right_a[j];
      j++;
    }
    if(index>1&&a[index-2]==a[index-1]){
      c[index-2]+=c[index-1];
      index--;
    }
  }
  (*new_size)=index;
  return;
}
void insert(int target,int idx,int c,int a){
  int bucket=(target*200000LL+idx)%HASH_SIZE;
  node *t;
  t=(node*)malloc(sizeof(node));
  t->t=target;
  t->i=idx;
  t->c=c;
  t->a=a;
  t->next=hash[bucket];
  hash[bucket]=t;
  return;
}
int search(int target,int idx,int *c){
  int bucket=(target*200000LL+idx)%HASH_SIZE;
  node *t=hash[bucket];
  while(t){
    if(t->t==target && t->i==idx){
      *c=t->c;
      return t->a;
    }
    t=t->next;
  }
  return -1;
}
int solve(int target,int target2,int idx){
  if(target<=0)
    return 0;
  if(target>remain[idx])
    return -1;
  if(target==remain[idx]){
    insert(target,idx,-1,target);
    return target;
  }
  int t,ans=200000,ansc,i;
  if(idx==0){
    t=(target-1)/cdiff[idx]+1;
    return t*cdiff[idx];
  }
  t=search(target,idx,&w);
  if(t!=-1)
    return t;
  for(i=0;i<=c[idx];i++){
    t=solve(target-i*cdiff[idx],target2-i*cdiff[idx],idx-1);
    if(t!=-1){
      if(t+i*cdiff[idx]<ans){
        ans=t+i*cdiff[idx];
        ansc=i;
      }
      if(t+i*cdiff[idx]==target || t+i*cdiff[idx]==target2){
        insert(target,idx,i,t+i*cdiff[idx]);
        return t+i*cdiff[idx];
      }
    }
    if(target-i*cdiff[idx]<=0)
      break;
  }
  insert(target,idx,ansc,ans);
  return ans;
}
void clean_table(){
  int i;
  lnode *p,*pp;
  for(i=0;i<N;i++)
    if(table[i]){
      p=table[i];
      while(p){
        pp=p->next;
        free(p);
        p=pp;
      }
      table[i]=NULL;
    }
  return;
}

Black and White Tree C++ Solution

#include <bits/stdc++.h>
// #include "testlib.h"
using namespace std ;

#define ft first
#define sd second
#define pb push_back
#define all(x) x.begin(),x.end()

#define ll long long int
#define vi vector<int>
#define vii vector<pair<int,int> >
#define pii pair<int,int>
#define vl vector<ll>
#define vll vector<pair<ll,ll> >
#define pll pair<ll,ll>
#define pli pair<ll,int>
#define mp make_pair

#define sc1(x) scanf("%d",&x)
#define sc2(x,y) scanf("%d%d",&x,&y)
#define sc3(x,y,z) scanf("%d%d%d",&x,&y,&z)

#define scll1(x) scanf("%lld",&x)
#define scll2(x,y) scanf("%lld%lld",&x,&y)
#define scll3(x,y,z) scanf("%lld%lld%lld",&x,&y,&z)

#define pr1(x) printf("%d\n",x)
#define pr2(x,y) printf("%d %d\n",x,y)
#define pr3(x,y,z) printf("%d %d %d\n",x,y,z)

#define prll1(x) printf("%lld\n",x)
#define prll2(x,y) printf("%lld %lld\n",x,y)
#define prll3(x,y,z) printf("%lld %lld %lld\n",x,y,z)

#define pr_vec(v) for(int i=0;i<v.size();i++) cout << v[i] << " " ;

#define f_in(st) freopen(st,"r",stdin)
#define f_out(st) freopen(st,"w",stdout)

#define fr(i, a, b) for(i=a; i<=b; i++)
#define fb(i, a, b) for(i=a; i>=b; i--)

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;
const int N=200010;
int w[2];
vector <int> v[N];
int a[N], d[N], p[N], c[N], col[N], sz, ccol[2][N];
bool f[N];
queue<int> q[N];
void dfs(int x,int y){
    f[x]=1;
    w[y]++;
    col[x] = y;
    ccol[y][sz] = x;
    for (int i=0;i<v[x].size();i++)
    if (!f[v[x][i]])
        dfs(v[x][i],(y^1));
    else if( col[v[x][i]] != 1 - y ) 
        assert(0);
}

int main() {
    int n,m;
    scanf("%d%d",&n,&m);
    for (int i=0,x,y;i<m;i++){
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }

    int k=0;
    for (int i=1;i<=n;i++) {
        if (!f[i]) {
            w[0] = w[1]=0;
            dfs(i,0);
            c[i] = (w[0] < w[1]);
            k+=abs(w[0]-w[1]);
            a[abs(w[0]-w[1])]++;
            q[abs(w[0]-w[1])].push( i );
        }
    }

    for (int j=1;j<=k;j++) d[j]=N;

    for (int i=1;i<=n;i++)
        if (a[i]) {
            for (int j=0;j+i<=k;j++) {
                if( d[i+j] == N && d[j] != N ) {
                    d[i+j] = d[j] + 1;
                    p[i+j] = j;
                }
            }

            for (int j=1;j<=k;j++) {
                if (d[j]>a[i]) {
                    d[j]=N;
                    p[j]=0;
                } else {
                    d[j]=0;
                }
            }
        }

    int ans=k, v = 0;
    for (int i=0;i<=k;i++) {
        if(d[i]<N) {
            if( ans >= abs(k - 2 * i) ) {
                ans = abs(k - 2 * i);
                v = i;
            }
        }
    }

    memset(f, 0, sizeof f);
    while( v != 0 ) {
        int diff = v - p[v];
        int nd = q[diff].front();
        q[diff].pop();
        sz ++;
        dfs(nd, c[nd]);
        v = p[v];
    }

    for(int i=1; i<=n; i++) {
        if( !f[i] ) {
            sz ++;
            dfs(i, 1 - c[i]);
        }
    }

    int blk, wht, idb, idw;
    blk = wht = idb = idw = -1;
    for(int i=1; i<=sz; i++) {

        if( ccol[0][i] ) {
            blk = ccol[0][i];
            idb = i;
        }

        if( ccol[1][i] ) {
            wht = ccol[1][i];
            idw = i;
        }
    }
    cout << ans << " " << sz - 1 << "\n";
    if( idb != idw ) cout << blk << " " << wht << "\n";
    for(int i=1; i<=sz; i++) {
        if( i != idb && i != idw ) {
            if( ccol[0][i] ) {
                cout << wht << " " << ccol[0][i] << "\n";
            } else {
                cout << blk << " " << ccol[1][i] << "\n";
            }
        }
    }
    return 0;
}

Black and White Tree Java Solution

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Stack;
public class BlackAndWhiteTree {
    static final List<Graph> graphs = new ArrayList<>();
    static int ones = 0;
    static int zeroes = 0;
    public static void main(String[] args) throws Exception {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            String[] line = br.readLine().split(" ");
            Node[] nodes = new Node[Integer.parseInt(line[0])];
            for (int e = 0; e < nodes.length; e++) {
                nodes[e] = new Node(e);
            }
            for (int e = Integer.parseInt(line[1]); e > 0; e--) {
                line = br.readLine().split(" ");
                nodes[Integer.parseInt(line[0]) - 1].adjacent.add(nodes[Integer.parseInt(line[1]) - 1]);
                nodes[Integer.parseInt(line[1]) - 1].adjacent.add(nodes[Integer.parseInt(line[0]) - 1]);
            }
            int components = 0;
            for (int e = 0; e < nodes.length; e++)
                if (!nodes[e].visited) {
                    Graph g = new Graph(nodes[e]);
                    if (g.diffs == 0) {
                        zeroes++;
                    } else if (g.diffs == 1) {
                        ones++;
                    } else {
                        components += g.diffs;
                    }
                    graphs.add(g);
                }
            Collections.sort(graphs, (g1, g2) -> Math.abs(g1.diffs) - Math.abs(g2.diffs));
            final int SIZE = components / 2 + 1;
            boolean[] dinam = new boolean[SIZE];
            int[] parent = new int[SIZE];
            Arrays.fill(parent, Integer.MAX_VALUE);
            dinam[0] = true;
            int lastMax = 0;
            for (int g = ones + zeroes; g < graphs.size(); g++) {
                final int dif = graphs.get(g).diffs, top = Math.min(SIZE, lastMax + dif + 1);
                for (int e = top - 1; e >= dif; e--) {
                    dinam[e] |= dinam[e - dif];
                    if (dinam[e - dif]) {
                        parent[e] = Math.min(parent[e], dif);
                    }
                }
                lastMax += dif;
            }
            int min = 0;
            int mindiff = components;
            for (int e = 0; e < SIZE; e++)
                if (dinam[e] && calcMin(Math.abs(components - 2 * e)) < calcMin(Math.abs(components - 2 * min))) {
                    min = e;
                    mindiff = Math.abs(components - 2 * e);
                }
            final int minValue = calcMin(Math.abs(components - 2 * min));
            for (int g = graphs.size() - 1; g >= 0; g--) {
                if (graphs.get(g).diffs == 0) {
                } else if (graphs.get(g).diffs == 1) {
                    graphs.get(g).signum = g < zeroes + mindiff || (g % 2) == 1;
                } else if (min > 0 && parent[min] == graphs.get(g).diffs) {
                    graphs.get(g).signum = true;
                    min -= graphs.get(g).diffs;
                }
            }
            Collections.sort(graphs, (g1, g2) -> Boolean.compare(g1.signum, g2.signum));
            Graph root = graphs.get(graphs.size() - 1);
            System.out.println(minValue + " " + (graphs.size() - 1));
            for (int g = 0; g < graphs.size() - 1; g++) {
                if (graphs.get(g).signum == root.signum) {
                    root.root.adjacent.get(0).adjacent.add(graphs.get(g).root);
                    graphs.get(g).root.adjacent.add(root.root.adjacent.get(0));
                    System.out.println(root.root.adjacent.get(0).id + " " + graphs.get(g).root.id);
                } else {
                    root.root.adjacent.add(graphs.get(g).root);
                    graphs.get(g).root.adjacent.add(root.root);
     System.out.println(root.root.id + " " + graphs.get(g).root.id);
                }
            }
        }
    }
    public static int calcMin(int x) {
        if (ones < x) {
            return x - ones;
        }
        return (ones - x) % 2;
    }
    static class Graph {
        Node root;
        int whites, blacks, diffs, size;
        boolean signum = false;
        public Graph(Node root) {
            this.root = root;
            Stack<Node> n = new Stack<>();
            n.add(root);
            while (!n.isEmpty()) {
                Node next = n.pop();
                if (next.visited)
                    continue;
                next.parent = root.parent;
                next.visited = true;
                if (next.isWhite) {
                    whites++;
                } else {
                    blacks++;
                }
                for (Node e : next.adjacent) {
                    e.isWhite = !next.isWhite;
                    n.push(e);
                }
            }
            diffs = blacks - whites;
            size = blacks + whites;
            if (blacks - whites < 0) {
                invert();
            }
        }
        public void invert() {
            root = root.adjacent.get(0);
            int t = blacks;
            blacks = whites;
            whites = t;
            diffs = blacks - whites;
            size = blacks + whites;
        }
    }
    static class Node {
        int parent, id;
        boolean isWhite, visited;
        ArrayList<Node> adjacent = new ArrayList<>();
        public Node(int parent) {
            this.parent = parent;
            this.id = parent + 1;
        }
    }
}
c C++ HackerRank Solutions java