HackerRank Far Vertices Problem Solution

In this post, we will solve HackerRank Far Vertices Problem Solution.

You are given a tree that has N vertices and N-1 edges. Your task is to mark as small 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.

Input Format
The first line of input contains two integers N and K. The next N-1 lines contain two integers (ui,vi) each, where 1 <= ui,vi <= N. Each of these lines specifies an edge.
N is no more than 100. K is less than N.

Output Format
Print an integer that denotes the result of the test.

Sample Input:

Sample Output:

Sample Input:

Sample Output:

Explanation:

In the first case you have to mark at least 3 vertices, and in the second case you don’t need to mark any vertices.

Table of Contents

Far Vertices C Solution

#include <stdio.h>

long long b[1000],a[1000][1000],i,j,k,l,m,n,t,K;


long long makaj(long long ii, long long jj, long long hh)
{
long long vv=0,tt;

for(tt=0;tt<n;tt++)
 {
  if(a[tt][jj]<a[tt][ii] && a[tt][ii]<=hh) vv++; 
  if(a[tt][jj]>a[tt][ii] && a[tt][ii]<=K-hh) vv++;
 }

return vv;
} 


int main()
{

scanf("%lld %lld\n",&n,&K);

for(i=0;i<n;i++)
 for(j=0;j<n;j++) a[i][j] = 100000000;

for(i=0;i<n;i++) a[i][i]=0;

for(i=0;i<n-1;i++)
{
 scanf("%lld %lld",&j,&l);
 a[j-1][l-1]=1;
 a[l-1][j-1]=1;
}

  for(k=0;k<n;k++)
for(i=0;i<n;i++)
 for(j=0;j<n;j++)
   if(a[i][j]> a[i][k] + a[k][j]) 
     {
     a[i][j] = a[j][i] = a[i][k]+a[k][j];
     }

m = 100000;

  for(i=0;i<n;i++)
    for(j=0;j<n;j++)
      if(a[i][j]==1)
       {
       for(l=K;l>=(K+1)/2;l--)
       k = makaj(i,j,l);
       if(n-k<m) m = n-k;       
       }



printf("%lld\n",m);

//for(i=0;i<n;i++)
// for(j=0;j<n;j++)
//  printf("%lld %lld -> %lld\n",i,j,a[i][j]);

return 0;
}

Far Vertices C++ Solution

#include <iostream>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    pair<int, int> edge[n - 1];
    int dp[n][n], result = n;
    for(auto i = 0; i < n; i++) {
        for(auto j = 0; j < n; j++) {
            dp[i][j] = n;
        }
        dp[i][i] = 0;
    }
    for(auto i = 0; cin >> edge[i].first >> edge[i].second; i++) {
        edge[i].first--;
        edge[i].second--;
        dp[edge[i].first][edge[i].second] = 1;
        dp[edge[i].second][edge[i].first] = 1;
    }
    for(auto i = 0; i < n; i++) {
        for(auto j = 0; j < n; j++) {
            for(auto k = 0; k < n; k++) {
                dp[j][k] = min(dp[j][k], dp[j][i] + dp[i][k]);
            }
        }
    }
    if(k % 2 == 0) {
        for(auto i = 0; i < n; i++) {
            auto unmarked = 0;
            for(auto j = 0; j < n; j++) {
                if(dp[i][j] <= k / 2) {
                    unmarked++;
                }
            }
            result = min(result, n - unmarked);
        }
    } else {
        for(auto i = 0; i < n - 1; i++) {
            auto unmarked = 0;
            for(auto j = 0; j < n; j++) {
                if(dp[edge[i].first][j] <= k / 2 || dp[edge[i].second][j] <= k / 2) {
                    unmarked++;
                }
            }
            result = min(result, n - unmarked);
        }
    }
    cout << result;
    return 0;
}

Far Vertices C Sharp Solution

using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Collections;
using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.Serialization;
using System.Text.RegularExpressions;
using System.Text;
using System;

class Result
{

    /*
     * Complete the 'farVertices' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts following parameters:
     *  1. INTEGER n
     *  2. INTEGER k
     *  3. 2D_INTEGER_ARRAY edges
     */

    public static int farVertices(int n, int k, List<List<int>> edges)
    {
        int removed = 0;
        Dictionary<int, int> vertexLinks = verticesReachedDic(n, k, edges);
        List<int> leaves;
        List<(int, int)> leafVertexLinks;
        // vertex, links

        while (true) {                
            leaves = findLeaves(edges);

            bool allReachable = true;
            for (int i = 0; i < leaves.Count - 1; i++) {
                for (int j = i + 1; j< leaves.Count; j++) {
                    if (!reachable(leaves[i], leaves[j], k, edges)) {
                        allReachable = false;
                        break;
                    }

                    if (!allReachable)
                        break;
                }
            }

            if (allReachable)
                break;

            leafVertexLinks = leaves.Select(x => (x, vertexLinks[x])).OrderBy(x => x.Item2).ToList();
            (int vertex, int links) current = leafVertexLinks[0];

            // Remove leaf with least links
            foreach (int vertex in verticesVisited(current.vertex, k, edges))
                vertexLinks[vertex] = vertexLinks[vertex] - 1;
            edges = edges.Where(x => !x.Contains(current.vertex)).ToList();
            removed++;
        }

        return removed;

    }

    public static List<int> findLeaves(List<List<int>> edges) {
        return edges.SelectMany(x => x).ToList().GroupBy(x => x).Where(x => x.Count() == 1).Select(x => x.First()).ToList();
    }

    public static Dictionary<int, int> verticesReachedDic(int n, int k, List<List<int>> edges) {
        List<int> vertices = Enumerable.Range(1, n).ToList();
        Dictionary<int, int> nrVerticesReached = new Dictionary<int, int>(); // vertex, nr other vertices it reaches in allowed steps
        
        for (int i = 0; i < vertices.Count; i++)
            nrVerticesReached[vertices[i]] = verticesVisited(vertices[i], k, edges).Count() + 1;

        return nrVerticesReached;
    }

    public static List<int> verticesVisited(int cur, int k, List<List<int>> edges) {
        List<List<int>> relEdges = edges.Where(x => x.Contains(cur)).Select(x => new List<int>() {cur, x.Where(y => y != cur).First()}).ToList();
        List<int> verticesVisited = new List<int>();

        for (int steps = 0; steps < k; steps++) {
            List<List<int>> newRelEdges = new List<List<int>>();
            
            foreach (List<int> edge in relEdges) {
                cur = edge[1];
                verticesVisited.Add(cur);

                int prev = edge[0];
                newRelEdges.AddRange(edges.Where(x => x.Contains(cur) && !x.Contains(prev)).Select(x => new List<int>() {cur, x.Where(y => y != cur).First()}));
            }

            relEdges = newRelEdges;
        }

        return verticesVisited.Distinct().ToList();
    }

    public static bool reachable(int cur, int target, int maxSteps, List<List<int>> edges) {
        List<List<int>> relEdges = edges.Where(x => x.Contains(cur)).Select(x => new List<int>() {cur, x.Where(y => y != cur).First()}).ToList();

        for (int steps = 0; steps < maxSteps; steps++) {
            List<List<int>> newRelEdges = new List<List<int>>();
            foreach (List<int> edge in relEdges) {
                cur = edge[1];

                if (cur == target) {
                    return true;
                }

                int prev = edge[0];
                newRelEdges.AddRange(edges.Where(x => x.Contains(cur) && !x.Contains(prev)).Select(x => new List<int>() {cur, x.Where(y => y != cur).First()}));
            }

            relEdges = newRelEdges;
        }

        return false;
    }

}

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

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

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

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

        List<List<int>> edges = new List<List<int>>();

        for (int i = 0; i < n - 1; i++)
        {
            edges.Add(Console.ReadLine().TrimEnd().Split(' ').ToList().Select(edgesTemp => Convert.ToInt32(edgesTemp)).ToList());
        }

        int result = Result.farVertices(n, k, edges);

        textWriter.WriteLine(result);

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

Far Vertices Java Solution

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("(\r\n|[\n\r\u2028\u2029\u0085])*");

        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("(\r\n|[\n\r\u2028\u2029\u0085])*");

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

Far Vertices JavaScript Solution

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', function(inputStdin) {
    inputString += inputStdin;
});

process.stdin.on('end', function() {
    inputString = inputString.split('\n');

    main();
});

function readLine() {
    return inputString[currentLine++];
}

function findArrayIntersection(arr1, arr2) {
    const intersectedArray = [];
    for (let i of arr1) {
      if (arr2.includes(i) && !intersectedArray.includes(i)) {
        intersectedArray.push(i);
      }
    }
    return intersectedArray;
  }
  
  function recursivelyProcessConnections(cMap, k, previousV, currentV, currentVisited, endVertices) {
    if (!currentVisited.includes(currentV)) {
       currentVisited.push(currentV);
    }
    if (k === 0 || (cMap[currentV].length === 1 && currentVisited.includes(cMap[currentV][0]))) {
      if (!endVertices.includes(currentV) && k === 0) {
        endVertices.push(currentV);
      }
      return currentVisited;
    }
    
    for (let x of cMap[currentV]) {
      if (x !== previousV) {
        recursivelyProcessConnections(cMap, k-1, currentV, x, currentVisited, endVertices);
      }
    }
    return currentVisited;
  }
  
  function specialProcessing(cMap, k) {
    let maxPathingForVertices = {};
    const endVertices = [];
  
    for (let i of Object.keys(cMap)) {
      const allVertices = recursivelyProcessConnections(cMap, k, null, parseInt(i, 10), [], endVertices);
      maxPathingForVertices[i] = { allVertices, endVertices: [...endVertices] };
      endVertices.splice(0);
    }
    return maxPathingForVertices;
  }
  
  function farVertices(n, k, edges) {
    // Write your code here
    const verticeConnectionMap = {};
    for (let i of edges) {
      if (!verticeConnectionMap[i[0]]) {
        verticeConnectionMap[i[0]] = [i[1]];
      } else {
        verticeConnectionMap[i[0]].push(i[1]);
      }
      
      if (!verticeConnectionMap[i[1]]) {
        verticeConnectionMap[i[1]] = [i[0]];
      } else {
        verticeConnectionMap[i[1]].push(i[0]);
      }
    }
  
    const maxPathingForVertices = specialProcessing(verticeConnectionMap, k);

    const mostConnected = {};
    for (let x of Object.keys(maxPathingForVertices)) {
      let intersection = [...maxPathingForVertices[x].allVertices];
      mostConnected[x] = [];
      for (let y of maxPathingForVertices[x].endVertices) {
        intersection = findArrayIntersection(maxPathingForVertices[x].allVertices, maxPathingForVertices[y].allVertices);
        if (intersection.length > mostConnected[x].length) {
          mostConnected[x].splice(0);
          mostConnected[x].push(...intersection);
        }
      }
    }

    let biggestConnection = 0;
    for (let x of Object.keys(mostConnected)) {
      if (mostConnected[x].length > biggestConnection) {
        biggestConnection = mostConnected[x].length;
      }
    }

    if (biggestConnection === 0) {
      return 0;
    }
    return n - biggestConnection;
  };

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const firstMultipleInput = readLine().replace(/\s+$/g, '').split(' ');

    const n = parseInt(firstMultipleInput[0], 10);

    const k = parseInt(firstMultipleInput[1], 10);

    let edges = Array(n - 1);

    for (let i = 0; i < n - 1; i++) {
        edges[i] = readLine().replace(/\s+$/g, '').split(' ').map(edgesTemp => parseInt(edgesTemp, 10));
    }

    const result = farVertices(n, k, edges);

    ws.write(result + '\n');

    ws.end();
}

Far Vertices Python Solution

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)