HackerRank Cut Tree Problem Solution

In this post, we will solve HackerRank Cut Tree Problem Solution.

Given a tree T with n nodes, how many subtrees (T’) of T have at most K edges connected to (T – T’)?

Input Format

The first line contains two integers n and K followed by n-1 lines each containing two integers a & b denoting that there’s an edge between a & b.

Constraints

1 <= K <= n <= 50
Every node is indicated by a distinct number from 1 to n.

Output Format

A single integer which denotes the number of possible subtrees.

Sample Input

3 1
2 1
2 3

Sample Output

Explanation

There are 2^3 possible sub-trees:

{} {1} {2} {3} {1, 2} {1, 3} {2, 3} {1, 2, 3}

But:
the sub-trees {2} and {1,3} are not valid. {2} isn’t valid because it has 2 edges connecting to it’s complement {1,3} whereas K = 1 in the sample test-case {1,3} isn’t valid because, well, it’s not a sub-tree. The nodes aren’t connected.

Table of Contents

Cut Tree C Solution

#include <stdio.h>
#include <stdlib.h>
void dfs(int x,int parent);
int table[50][50]={0},c[50]={0},p[50],q[51]={0},N;
long long dp1[50][51]={0},dp2[50][51]={0},temp[51],ans; // 1 without 2 with [node][K]
int main(){
  int K,x,y,i,j,k;
  scanf("%d%d",&N,&K);
  for(i=0;i<N-1;i++){
    scanf("%d%d",&x,&y);
    table[x-1][y-1]=-1;
    table[y-1][x-1]=-1;
  }
  dfs(0,0);
  for(i=0;i<N;i++)
    if(!c[i])
      q[++q[0]]=i;
  while(q[0]){
    x=q[q[0]--];
    dp1[x][0]=dp2[x][0]=1;
    for(i=0;i<N;i++)
      if(table[x][i]==1){
        for(j=1;j<=K;j++)
          temp[j]=0;
        for(j=1;j<=K;j++){
          dp1[x][j]+=dp1[i][j]+dp2[i][j-1];
          for(k=0;k<=j;k++)
            if(k==1)
              temp[j]+=(dp2[i][k]+1)*dp2[x][j-k];
            else
              temp[j]+=dp2[i][k]*dp2[x][j-k];
        }
        for(j=1;j<=K;j++)
          dp2[x][j]=temp[j];
      }
    if(x){
      c[p[x]]--;
      if(!c[p[x]])
        q[++q[0]]=p[x];
    }
  }
  for(i=0,ans=0;i<=K;i++)
    ans+=dp1[0][i]+dp2[0][i];
  printf("%lld",ans);
  return 0;
}
void dfs(int x,int parent){
  int i;
  p[x]=parent;
  for(i=0;i<N;i++)
    if(table[x][i] && i!=parent){
      table[x][i]+=2;
      c[x]++;
      dfs(i,x);
    }
  return;
}

Cut Tree C++ Solution

#include <bits/stdc++.h>

using namespace std;

vector<string> split_string(string);

/*
 * Complete the cuttree function below.
 */
pair<vector<long>, vector<long> > br(const vector<vector<int> >& g, int i, int i0)
{
    vector<long> w(1, 1), wo;
    for (auto j: g[i]) if (j != i0)
    {
        auto [wp, wop] = br(g, j, i);
        if (wop.size() > wo.size()) wo.resize(wop.size(), 0);
        for (int i = 0; i < wop.size(); ++i) wo[i] += wop[i];
        if (wp.size() + 1 > wo.size()) wo.resize(wp.size() + 1, 0);
        for (int i = 0; i < wp.size(); ++i) wo[i+1] += wp[i];
        vector<long> w2(max(1+int(w.size()), int(wp.size() + w.size()) - 1), 0);
        for (int i = 0; i < w.size(); ++i)
        {
            w2[i+1] += w[i];
            for (int k = 0; k < wp.size(); ++k) w2[i+k] += w[i]*wp[k];
        }
        swap(w, w2);
    }
    return {w, wo};
}

long cutTree(int n, int k, vector<vector<int>> edges) {
    /*
     * Write your code here.
     */
    vector<vector<int> > g(n);
    for (auto& v: edges)
    {
        --v[0]; --v[1];
        g[v[0]].push_back(v[1]);
        g[v[1]].push_back(v[0]);
    }
    auto [w, wo] = br(g, 0, -1);
    for (auto k: w) cout << k << " "; cout << "\n";
    for (auto k: wo) cout << k << " "; cout << "\n";
    long res = 0;
    for (int i = 0; i < min<int>(w.size(), k+1); ++i) res += w[i];
    for (int i = 0; i < min<int>(wo.size(), k+1); ++i) res += wo[i];
    return res+1;
}

int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));

    string nk_temp;
    getline(cin, nk_temp);

    vector<string> nk = split_string(nk_temp);

    int n = stoi(nk[0]);

    int k = stoi(nk[1]);

    vector<vector<int>> edges(n-1);
    for (int edges_row_itr = 0; edges_row_itr < n-1; edges_row_itr++) {
        edges[edges_row_itr].resize(2);

        for (int edges_column_itr = 0; edges_column_itr < 2; edges_column_itr++) {
            cin >> edges[edges_row_itr][edges_column_itr];
        }

        cin.ignore(numeric_limits<streamsize>::max(), '\n');
    }

    long result = cutTree(n, k, edges);

    fout << result << "\n";

    fout.close();

    return 0;
}

vector<string> split_string(string input_string) {
    string::iterator new_end = unique(input_string.begin(), input_string.end(), [] (const char &x, const char &y) {
        return x == y and x == ' ';
    });

    input_string.erase(new_end, input_string.end());

    while (input_string[input_string.length() - 1] == ' ') {
        input_string.pop_back();
    }

    vector<string> splits;
    char delimiter = ' ';

    size_t i = 0;
    size_t pos = input_string.find(delimiter);

    while (pos != string::npos) {
        splits.push_back(input_string.substr(i, pos - i));

        i = pos + 1;
        pos = input_string.find(delimiter, i);
    }

    splits.push_back(input_string.substr(i, min(pos, input_string.length()) - i + 1));

    return splits;
}

Cut Tree C Sharp Solution

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

class Solution {
    private class Node {
        public int Id { get; set; }
        public List<Node> Children { get; set; }
    }

    /*
     * Complete the cuttree function below.
     */
    static long cutTree(int n, int k, int[][] edges) {
        var dp = new long[n, k + 1];
        var graph = new List<int>[n];
        
        for (var i = 0; i < n; ++i) {
            graph[i] = new();
        }
        
        foreach (var edge in edges) {
            var u = edge[0] - 1;
            var v = edge[1] - 1;
            graph[u].Add(v);
            graph[v].Add(u);
        }

        var rootNode = new Node {
            Id = 0,
            Children = new()
        };
        
        BuildTree(graph, rootNode, -1);
        
        return Solve(rootNode, dp, k) + 1;
    }
    
    private static void BuildTree(List<int>[] graph, Node curNode, int parentNodeId) {
        foreach (var childNodeId in graph[curNode.Id].Where(n => n != parentNodeId)) {
            var childNode = new Node {
                Id = childNodeId,
                Children = new()
            };
            curNode.Children.Add(childNode);
            BuildTree(graph, childNode, curNode.Id);
        }
    }
    
    private static long Solve(Node node, long[,] dp, int k) {
        if (node.Children.Count == 0) {
            dp[node.Id, 0] = 1;
            return 1;
        }
        
        var ans = 0L;
        
        foreach (var childNode in node.Children) {
            ans += Solve(childNode, dp, k);
        }
        
        var dp2 = new long[k + 1, node.Children.Count];
        
        for (var i = 0; i <= k; ++i) {
            dp2[i, 0] = dp[node.Children[0].Id, i];
            
            if (i == 1) {
                ++dp2[i, 0];
            }
            
            for (var j = 1; j < node.Children.Count; ++j) {
                for (var k2 = 0; k2 <= i; ++k2) {
                    var extra = i - k2 == 1 ? 1 : 0;
                    dp2[i, j] += dp2[k2, j - 1] * (dp[node.Children[j].Id, i - k2] + extra);
                }
            }
            
            dp[node.Id, i] = dp2[i, node.Children.Count - 1];
            
            if (i < k || node.Id == 0) {
                ans += dp[node.Id, i];
            }
        }
        
        return ans;
    }

    static void Main(string[] args) {
        TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);

        string[] nk = Console.ReadLine().Split(' ');

        int n = Convert.ToInt32(nk[0]);

        int k = Convert.ToInt32(nk[1]);

        int[][] edges = new int[n-1][];

        for (int edgesRowItr = 0; edgesRowItr < n-1; edgesRowItr++) {
            edges[edgesRowItr] = Array.ConvertAll(Console.ReadLine().Split(' '), edgesTemp => Convert.ToInt32(edgesTemp));
        }

        var result = 0L;

        checked {
            result = cutTree(n, k, edges);
        }
        
        textWriter.WriteLine(result);

        textWriter.Flush();
        textWriter.Close();
    }
}

Cut Tree Java Solution

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

public class cuttree extends PrintWriter {
    cuttree() { super(System.out, true); }
    Scanner sc = new Scanner(System.in);
    public static void main(String[] $) {
        cuttree o = new cuttree(); o.main(); o.flush();
    }

    int[] eo; int[][] ej;
    void append(int i, int j) {
        int o = eo[i]++;
        if (o >= 2 && (o & o - 1) == 0)
            ej[i] = Arrays.copyOf(ej[i], o << 1);
        ej[i][o] = j;
    }
    long[][] dp; long[] tt; int k;
    void init(int n) {
        eo = new int[n]; ej = new int[n][2];
        dp = new long[n][k + 1]; tt = new long[k + 1];
    }
    void mult(long[] aa, long[] bb) {
        Arrays.fill(tt, 0);
        for (int i = 0; i <= k; i++)
            for (int j = 0; i + j <= k; j++)
                tt[i + j] += aa[i] * bb[j];
        System.arraycopy(tt, 0, aa, 0, k + 1);
    }
    long ans = 1;
    void dfs(int p, int i) {
        dp[i][0] = 1;
        for (int o = eo[i]; o-- > 0; ) {
            int j = ej[i][o];
            if (j != p) {
                dfs(i, j);
                dp[j][1]++;
                mult(dp[i], dp[j]);
            }
        }
        for (int h = p == -1 ? k : k - 1; h >= 0; h--)
            ans += dp[i][h];
    }
    void main() {
        int n = sc.nextInt();
        if (n == 1) {
            println(2);
            return;
        }
        k = sc.nextInt();
        if (k == n)
            k = n - 1;
        init(n);
        for (int h = 0; h < n - 1; h++) {
            int i = sc.nextInt() - 1;
            int j = sc.nextInt() - 1;
            append(i, j);
            append(j, i);
        }
        dfs(-1, 0);
        println(ans);
    }
}

Cut Tree Python Solution

line = input().split()
n = int(line[0])
K = int(line[1])

adjlst = [[1]]
for i in range(n):
    adjlst.append([])
adjlst[1].append(0)

for i in range(n - 1):
    line = input().split()
    x = int(line[0])
    y = int(line[1])
    adjlst[x].append(y)
    adjlst[y].append(x)

def dfs(node, par, adjlst, K):
    conlst = [0] * (K + 1)
    dislst = [0] * (K + 1)
    conlst[0] = 1
    for chld in adjlst[node]:
        if chld != par:
            tcl, tdl = dfs(chld, node, adjlst, K)
            # print(str(tcl))
            # print(str(tdl))
            dislst[0] += tdl[0]
            tcl2 = [0] * (K + 1)
            for i in range(K):
                dislst[i + 1] += tcl[i] + tdl[i + 1]
                tcl2[i + 1] += conlst[i]
            for i in range(K + 1):
                for j in range(K + 1):
                    if i + j <= K:
                        tcl2[i + j] += tcl[i] * conlst[j]
            conlst = list(tcl2)
    return conlst, dislst

conlst, dislst = dfs(1, 0, adjlst, K)
# print(str(conlst))
# print(str(dislst))
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))

Cut Tree C Solution

Cut Tree C++ Solution

Cut Tree C Sharp Solution

Cut Tree Java Solution

Cut Tree Python Solution

Related Posts