We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Far Vertices
  5. Discussions

Far Vertices

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 20 Discussions, By:

votes

Please Login in order to post a comment

  • 13et1148
    6 years ago+ 0 comments

    I can't understand the problem. Please anyone can explain the sample example with a tree diagram.

    11|
    Permalink
  • ankit_rohillaa
    7 years ago+ 0 comments

    problems without editorial are irritating you have the editorials for stupid and easy problems, but for these tough problems, no editorial

    6|
    Permalink
  • shahraanhussain
    3 years ago+ 0 comments

    Unclear Question

    1|
    Permalink
  • TChalla
    1 year ago+ 0 comments

    Python3 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)
    
    0|
    Permalink
  • cse_1923_b_13
    1 year ago+ 0 comments

    Let's re-word this question : You're given a graph as input (in the form of pairs of vertices; every pair represents an edge).

    "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."

    The above sentence says you need to mark (assume, mark = delete a vertex) so that the remaining number of vertices have atmost K length between them. In other words : find the minimum number of vertices you need to remove so that the remaining tree has path <= K between the vertices. Hint : Use floyd warshall algorithm.

    0|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature