JRP's blog

[G. Training Camp] ACM Arabella Collegiate Programming Contest 2015
By JRP, history, 8 years ago, In English

Hello, Can someone help me understand how the problem is solvable with dynamic programming ?
[G. Training Camp] ACM Arabella Collegiate Programming Contest 2015 http://codeforces.com/gym/100676

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

»
8 years ago, # |
← Rev. 6   Vote: I like it +1 Vote: I do not like it

Do a standard bitmask DP with a loop from 1 to N inside where at every step you decide to try taking the ith item or not. Let's call that DP[msk].

Now it comes down to knowing whether you can choose the current item or not. ( You have taken all topics required for it).

Create a graph G where edges are reversed and mark roots as nodes with indegree of zero in the original graph. We can use a node in the first DP if we can start at it, and reach a root node from all our paths using only the nodes in our msk. This can be done with another DP in N * 2 ^N.

You should also handle cases with cycle since he didn't mention anything about it being a DAG, in these cases answer should be zero D:. ( You can't take items in cycles, so if you get rid of them you will end up with a DAG ).

This gets a runtime error because a parsing error that I'm too lazy to debug but I'm sure it will work, give a try.

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

    Thank you for explaining the solution. Note: I solved it without checking if there is a cycle and got AC.

    → Reply