In this HackerRank Far Vertices problem solution we have given a tree that has N vertices and N-1 edges. Your task is to mark as small a number of vertices as possible, such that, the maximum distance between two unmarked vertices is less than or equal to K. Output this value. Distance between two vertices i and j is defined as the minimum number of edges you have to pass in order to reach vertex I from vertex j.
Problem solution in Python.
n, k = [int(a) for a in input().split(" ")] count = 0 class Node(object): def __init__(self): self.neighbors = [] self.marked = False def set_neighbor(self, neighbor): self.neighbors.append(neighbor) def mark_dfs(self, depth, root = False): global count self.marked = True count += 1 if depth == 0: children = len(self.neighbors) - 1 if not root: return children return min(children, 1) num_children = 0 for neighbor in self.neighbors: if not neighbor.marked: mc = neighbor.mark_dfs(depth-1) if root: num_children = max(num_children,mc) else: num_children += mc return num_children nodes = [] for i in range(n): node = Node() nodes.append(node) def unmark_all(): for node in nodes: node.marked = False for i in range(n - 1): u, v = [int(a) - 1 for a in input().split(" ")] nodes[u].set_neighbor(nodes[v]) nodes[v].set_neighbor(nodes[u]) max_count = 0 for node in nodes: c = node.mark_dfs(k // 2, True) if k % 2 == 1: count += c if count > max_count: max_count = count unmark_all() count = 0 print(n - max_count)
Problem solution in Java.
import java.io.*; import java.math.*; import java.text.*; import java.util.*; import java.util.regex.*; public class Solution { static int[][] dist; static int[] parent; static ArrayList<ArrayList<Integer>> neighbours; /* * Complete the farVertices function below. */ static int farVertices(int n, int k, int[][] edges) { neighbours = new ArrayList<ArrayList<Integer>>(); int fr, to; parent = new int[n]; dist = new int[n][n]; for (int i = 0; i < n; i++) { neighbours.add(new ArrayList<Integer>()); Arrays.fill(dist[i], -1); dist[i][i] = 0; parent[i] = -1; } for (int[] edge : edges) { fr = edge[0] - 1; to = edge[1] - 1; dist[fr][to] = 1; dist[to][fr] = 1; neighbours.get(fr).add((to)); neighbours.get(to).add(fr); } parent[0] = -2; setParents(0); // System.out.println(Arrays.toString(parent)); // return -2; int p = -1; for (int i = 0; i < n; i++) { p = parent[i]; int d = 1; while (p != -1 && p != -2) { dist[p][i] = d; dist[i][p] = d; d += 1; p = parent[p]; } } //printTree(0); int max = 0, num = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (distance(i, j) == k) { if ((num = count(i,j,n,k)) > max) { max = num; } /* * r += rrow[i] ? 0 : 1; c += rcol[j] ? 0 : 1; rrow[i] = true; rcol[j] = true; */ } } } /* * System.out.println("max = " + max); System.out.println("maxi = " + maxi); * System.out.println("maxj = " + maxj); print(dist); */ return max == 0 ? 0 : n-max; } static int count(int i, int j, int n, int k) { int total = 0; for (int m=0; m<n; m++) { if (distance(m,i) <= k && distance(m,j) <= k) { total += 1; } } return total; } static int distance(int fr, int to) { if (dist[fr][to] != -1) return dist[fr][to]; int p = parent[fr]; int d = 1; while (p != -2 && dist[p][to] == -1) { d += 1; p = parent[p]; } dist[fr][to] = d + dist[p][to]; dist[to][fr] = dist[fr][to]; return dist[fr][to]; } private static void setParents(int i) { ArrayList<Integer> tocheck = new ArrayList<Integer>(); for (int child : neighbours.get(i)) { if (parent[child] == -1) { parent[child] = i; tocheck.add(child); } } for (int child : tocheck) { setParents(child); } } private static final Scanner scanner = new Scanner(System.in); public static void main(String[] args) throws IOException { BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH"))); String[] nk = scanner.nextLine().split(" "); scanner.skip("(rn|[nru2028u2029u0085])*"); int n = Integer.parseInt(nk[0]); int k = Integer.parseInt(nk[1]); int[][] edges = new int[n-1][2]; for (int edgesRowItr = 0; edgesRowItr < n-1; edgesRowItr++) { String[] edgesRowItems = scanner.nextLine().split(" "); scanner.skip("(rn|[nru2028u2029u0085])*"); for (int edgesColumnItr = 0; edgesColumnItr < 2; edgesColumnItr++) { int edgesItem = Integer.parseInt(edgesRowItems[edgesColumnItr]); edges[edgesRowItr][edgesColumnItr] = edgesItem; } } int result = farVertices(n, k, edges); bufferedWriter.write(String.valueOf(result)); bufferedWriter.newLine(); bufferedWriter.close(); scanner.close(); } }
Problem solution in C++.
#include <iostream> #include <cstdio> #include <cmath> #include <map> #include <cstring> #include <algorithm> #include <vector> using namespace std; typedef long long LL; const int dr[] = {-1, 0, 1, 0}, dc[] = {0, 1, 0, -1}; const double inf = 1.0e20; vector <int> g[128]; int n, k, mem[128][128]; void dfs(int a, int d, int f = 0) { int* v = mem[a], t[128]; for (int i = 0; i <= k; ++i) v[i] = 1; if (d > 0) for (vector <int>::const_iterator it = g[a].begin(), ie = g[a].end(); it != ie; ++it) if (*it != f) { dfs(*it, d - 1, a); int* p = mem[*it]; for (int i = 0; i <= d; ++i) t[i] = v[i]; for (int i = d; i >= 0; --i) { for (int j = 0, u; j < d && i + 1 + j <= k; ++j) t[u = max(i, 1 + j)] = max(t[u], v[i] + p[j]); } for (int i = 0; i <= d; ++i) v[i] = t[i]; } // for (int i = 1; i <= k; ++i) v[i] = max(v[i], v[i - 1]); } int main(void) { for (int id = 1; 2 == scanf("%d %d", &n, &k); ++id) { for (int i = 1; i <= n; ++i) g[i].clear(); for (int i = 1, a, b; i < n && 2 == scanf("%d %d", &a, &b); ++i) g[a].push_back(b), g[b].push_back(a); int best = 0; for (int i = 1; i <= n; ++i) { dfs(i, k); // best = max(best, mem[i][k]); for (int j = 0; j <= k; ++j) best = max(best, mem[i][j]); } printf("%dn", n - best); } return 0; }
Problem solution in C.
#include <assert.h> #include <limits.h> #include <math.h> #include <stdbool.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX 102 char* readline(); char** split_string(char*); /* * Complete the farVertices function below. */ struct edge{ int from; int to; }; int farVertices(int n, int k, int** edges) { struct edge sortedge[2*(n - 1)]; for(int i = 0; i < n - 1; i++){ sortedge[2*i].from = edges[i][0] - 1; sortedge[2*i].to = edges[i][1] - 1; sortedge[2*i + 1].from = edges[i][1] - 1; sortedge[2*i + 1].to = edges[i][0] - 1; } for(int i = 0; i < 2*(n - 1); i++){ int curr = i; while(curr > 0){ int next = (curr - 1)/2; if(sortedge[curr].from > sortedge[next].from){ struct edge temp = sortedge[curr]; sortedge[curr] = sortedge[next]; sortedge[next] = temp; curr = next; } else{ break; } } } for(int i = 2*n - 3; i >= 0; i--){ struct edge temp = sortedge[0]; sortedge[0] = sortedge[i]; sortedge[i] = temp; int curr = 0; while (true) { int next = curr; if(2*curr + 1 < i && sortedge[2*curr + 1].from > sortedge[next].from){ next = 2*curr + 1; } if(2*curr + 2 < i && sortedge[2*curr + 2].from > sortedge[next].from){ next = 2*curr + 2; } if(next != curr){ struct edge temp = sortedge[curr]; sortedge[curr] = sortedge[next]; sortedge[next] = temp; curr = next; } else{ break; } } } int edgebounds[n + 1]; edgebounds[0] = 0; for(int i = 0; i < n; i++){ int index = edgebounds[i]; while(index < 2*n - 2 && sortedge[index].from == i){ index++; } edgebounds[i + 1] = index; } int parentlist[n]; int *childrenlist[n]; int numchildren[n]; for(int i = 0; i < n; i++){ parentlist[i] = -2; childrenlist[i] = NULL; numchildren[i] = 0; } int parentqueue[n]; int queuesize = 1; parentqueue[0] = 0; int queuedone = 0; parentlist[0] = -1; while(queuedone < queuesize){ int currnode = parentqueue[queuedone]; for(int i = edgebounds[currnode]; i < edgebounds[currnode + 1]; i++){ int nextnode = sortedge[i].to; if(parentlist[nextnode] == -2){ parentlist[nextnode] = currnode; queuesize++; parentqueue[queuesize - 1] = nextnode; numchildren[currnode]++; childrenlist[currnode] = realloc(childrenlist[currnode], numchildren[currnode]*sizeof(int)); childrenlist[currnode][numchildren[currnode] - 1] = nextnode; } } queuedone++; } int bestsub[n][k + 1];//bestsub[i][j] = size of largest subtree rooted at i of depth j and diam <= k for(int i = n - 1; i >= 0; i--){ int currnode = parentqueue[i]; for(int l = 0; l <= k; l++){ bestsub[currnode][l] = 1; } for(int j = 0; j < numchildren[currnode]; j++){ int childnode = childrenlist[currnode][j]; int check = bestsub[childnode][k - 1] + 1; bestsub[currnode][k] = (check > bestsub[currnode][k]? check : bestsub[currnode][k]); for(int l = k - 1; 2*l > k; l--){ int altl = k - l; check = bestsub[currnode][l] + bestsub[childnode][altl - 1]; bestsub[currnode][l] = (check > bestsub[currnode][l]? check : bestsub[currnode][l]); check = bestsub[currnode][altl] + bestsub[childnode][l - 1]; bestsub[currnode][l] = (check > bestsub[currnode][l]? check : bestsub[currnode][l]); } for(int l = k/2; l > 0; l--){ bestsub[currnode][l] += bestsub[childnode][l - 1]; } } } int max = 1; for(int i = 0; i < n; i++){ printf("%d:t", i); for(int j = 0; j <= k; j++){ printf("%d %dt", j, bestsub[i][j]); max = (bestsub[i][j] > max? bestsub[i][j] : max); } printf("n"); } return n - max; } int main() { FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w"); char** nk = split_string(readline()); char* n_endptr; char* n_str = nk[0]; int n = strtol(n_str, &n_endptr, 10); if (n_endptr == n_str || *n_endptr != ' ') { exit(EXIT_FAILURE); } char* k_endptr; char* k_str = nk[1]; int k = strtol(k_str, &k_endptr, 10); if (k_endptr == k_str || *k_endptr != ' ') { exit(EXIT_FAILURE); } int** edges = malloc((n-1) * sizeof(int*)); for (int edges_row_itr = 0; edges_row_itr < n-1; edges_row_itr++) { *(edges + edges_row_itr) = malloc(2 * (sizeof(int))); char** edges_item_temp = split_string(readline()); for (int edges_column_itr = 0; edges_column_itr < 2; edges_column_itr++) { char* edges_item_endptr; char* edges_item_str = *(edges_item_temp + edges_column_itr); int edges_item = strtol(edges_item_str, &edges_item_endptr, 10); if (edges_item_endptr == edges_item_str || *edges_item_endptr != ' ') { exit(EXIT_FAILURE); } *(*(edges + edges_row_itr) + edges_column_itr) = edges_item; } } int result = farVertices(n, k, edges); fprintf(fptr, "%dn", result); fclose(fptr); return 0; } char* readline() { size_t alloc_length = 1024; size_t data_length = 0; char* data = malloc(alloc_length); while (true) { char* cursor = data + data_length; char* line = fgets(cursor, alloc_length - data_length, stdin); if (!line) { break; } data_length += strlen(cursor); if (data_length < alloc_length - 1 || data[data_length - 1] == 'n') { break; } size_t new_length = alloc_length << 1; data = realloc(data, new_length); if (!data) { break; } alloc_length = new_length; } if (data[data_length - 1] == 'n') { data[data_length - 1] = ' '; } data = realloc(data, data_length); return data; } char** split_string(char* str) { char** splits = NULL; char* token = strtok(str, " "); int spaces = 0; while (token) { splits = realloc(splits, sizeof(char*) * ++spaces); if (!splits) { return splits; } splits[spaces - 1] = token; token = strtok(NULL, " "); } return splits; }