apnakaamkar's blog

P — Independent Set (Educational DP Contest,Atcoder)
By apnakaamkar, history, 5 years ago, In English

Could anyone please explain to me how to solve this dp problem? Link:https://atcoder.jp/contests/dp/tasks/dp_p Please help?

  • Vote: I like it
  • -20
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This can be solved by tree dp concept that dp table can be updated from leaf toward to root. Lets assume you are at node now and define the do table like this. dp[current][0]:possible number of current == black dp[current][1]:possible number of current == white

"current"

/     |  ...  \

"child1" "child2" ... "childK"

If current is black, then all childs should be white:

dp[current][black] = dp[child1][white] * dp[child2][white]*...*dp[childK][white];

If current is white, then all childs color does not matter:

dp[current][white] = (dp[child1][white] + dp[child1][black]) * (dp[child2][white] + dp[child2][black])*...*(dp[childK][white] + dp[childK][black]);

After update all nodes, the last one will be the root node and answer is dp[root][white] + dp[root][black].

My submission: https://atcoder.jp/contests/dp/submissions/12971991

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

    dp[current][black] = dp[child1][white] * dp[child2][white]*...*dp[childK][white]; why u multiplied ?

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

      Because those are independent incidents so total possible way of state is multiplication of all sub incidents' answers. Example: Root(Black:6) = Child1[Black:2] * Child2[Black:3] ==> total 2 * 3 = 6 ways.

      → Reply