shubhamgoyal__'s blog

Hackerrank Problem.
By shubhamgoyal__, history, 7 years ago, In English

I was trying to solve this problem which recently appeared in a hackerrank contest. The editorial mentions a solution based on geometric interpretation of the question.But since a lot of tree path questions can be done using centroid decomposition,does anyone know how to solve it using centroid decomposition?

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

You can use centroid decomposition and persistent segtree, although I definitely do not recommend it.

Code

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain your solution briefly?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it +8 Vote: I do not like it

      Given a tree, you want to compute the number of paths through its root r which are not special. First enumerate the nodes of the tree in order of depth first search.

      We can use a persistent segment S tree for each node a, where S[b] = 1 if the path a - b is not special and S[b] = 0 otherwise. With this segment tree, we can

      • Compute the sum of all elements
      • Set a range of elements equal to 1

      Note that the sum of all elements in the segment tree will be equal to the number of non-special paths passing through r with the first endpoint at a.

      Suppose that the path a - b passes through r and is not special. Then obviously if c is a child of a,  then the path c - b is also not special. So the segment tree for c will be the same as that for a,  except a possible range modification.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        This is a really interesting solution. Thanks for the explanation!

        → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

On an related note, what is the rationale of adding hackerrank contest to codeforces calendar. The '101 Hack' is added to the calendar. However the OpenBracket and GoldmanSachs codesprints are not added.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I feel the calendar consists only short contests may be . And that is good because if we want all contests we can refer clist.by

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I don't know about OpenBracket ... but Goldman Sachs is an unrated contest ... Maybe only contests which are held by HackerRank for rating points in their website (and not hiring challenges) are added.

    → Reply
»
7 years ago, # |
  Vote: I like it +10 Vote: I do not like it

I have a solution without centroid decomposition, but it seems that it might be possible to adapt that solution for CD :P.

Suppose we want to know the number of special paths starting from some vertex v. For all vertices w, let's colour w black if and only if on the path from v to w there is another vertex with the same label as w. It is obvious that then, the answer is the size of the maximal connected subgraph that contains v and doesn't contain any black vertex.

Now, let's see how the vertices change colour if we change the starting vertex from u to v, where u and v are neighbours. It turns out that only two vertices might change color: the vertex with the same label as u and the vertex with the same label as v.

If we had a data structure that supported the 3 following operations in (amortized?) or better, then we would have a solution by DFS.

  • Change the colour of some vertex v to black.
  • Change the colour of some vertex v to white.
  • Count the size of the maximal connected subgraph containing some vertex v and no black vertices.

I have a solution in with HLD and lazy propagation. Maybe the operations can be somehow supported by centroid decomposition?

→ Reply