HackerRank Far Vertices problem solution

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