Блог пользователя kritipandey

No of ways of coloring a tree black such that root is colored black initially and a node can only be colored black if its parent node is black?
Автор kritipandey, история, 3 года назад, По-английски

Appeared in Lowes test

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

It can be solved by a dynamic approach. In order to get an answer for vertex, we can calculate answers for all children and then multiply them.

$$$dp[v]$$$ — number of ways color black the subtree of $$$v$$$.

$$$dp[leaf] = 1$$$, for all leafs

$$$dp[v] = \prod (dp[child] + 1)$$$

You can calculate it by simple dfs. Answer will be in $$$dp[root]$$$

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится -7 Проголосовать: не нравится

    isn't it $$$dp[v] = 1 + \prod dp[child]$$$?

    → Ответить
    • »
      »
      »
      3 года назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      $$$v$$$ has to be black, and a child can contain no black node at all, this is why there are $$$(dp[child] + 1)$$$ variations from each child. Am I wrong?

      → Ответить
      • »
        »
        »
        »
        3 года назад, # ^ |
        ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится 
        root
       /   \
      a     d
     / \
    c   b

        for this the answer should be 10 ig.

        when a is black, we can give c,b pair 4(2*2) different combinations. when a is white, c and b must be white . so here 4+1=5. 5 when d is white and 5 when d is black. so 5+5=10. as root can't be white ans will be 10

        → Ответить
        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          And by the algorithm above you get exactly this answer.

          $$$dp[c] = dp[b] = dp[d] = 1$$$

          $$$dp[a] = (1 + 1) * (1 + 1) = 4$$$

          $$$dp[root] = (4 + 1) * (1 + 1) = 10$$$

          → Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I think we need to color the whole tree with black color, and what matters is the ordering of coloring.. So, this dp approach won't work .. As it does not take into account the relative ordering.

    → Ответить
    • »
      »
      »
      3 года назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Can you please show a case where the above solution won't work?

      → Ответить
    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I think in this problem you don't need to consider an order of coloring, as it is not states so. Also, the author mentioned in comments that the answer for a rooted tree with two children is $$$4$$$ that proves order not matter.

      → Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    oops, thought the root could be colored white

    → Ответить
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

https://atcoder.jp/contests/dp/tasks/dp_v Harder version of the same problem.

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

I added Walmart to my boycott list ;)

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    You might want to add Lowe's as well . This problem appeared in my set in Lowe's Hiring contest Round 1 .

    → Ответить
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

This was the same question which was asked earlier in the LOWE's exam also. I solved it using DFS.

DFS
→ Ответить