kritipandey's blog

By kritipandey, history, 5 weeks ago, In English

Appeared in Lowes test

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I guess we can use dfs for it with having 1 variable to keep a count of the parent's color and changing it alternatively

»
5 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

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]$$$

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

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

    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      $$$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?

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        For a rooted tree that has two child node the answer was 4. So dp[v]=∏(dp[child]+1) appears correct.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it
        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

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          so dp[v]=∏(dp[child]+1)+1 for all nodes other than root node and for root node just dp[v]=∏(dp[child]+1)

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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$$$

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think you are correct. with the exception of root node bcoz we wont be able to color it white.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    oops, thought the root could be colored white

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +30 Vote: I do not like it

I added Walmart to my boycott list ;)

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

DFS
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by kritipandey (previous revision, new revision, compare).