ps06756's blog

How can I solve problem GPerm ?

By ps06756, history, 9 years ago, In English

Hello, I have been trying to solve the following problem which was a part of Topcoder SRM 696 Div1 Easy.

I am unable to find a editorial for the problem and I am not able to solve it. Can someone please tell me how to approach this problem ?

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

»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Let's M is set of all vertices, that have degree more than 1. If there are edges where both vertices have degrees 1 — add one vertex from each such edge to M.

You can see that size of M is no more than 20. So wee can color all vertices not in the M, after that write dp[mask] = mininal fee if mask — colored vertices from M.

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

    Can you please elaborate a little more, I am not able to understand the purpose of the set M ?

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

      Imagine, that you have only 20 vertices in graph — you could brute all bitmasks of vertex subsets and write dp[mask] without problem.

      But there you have 50 vertices, but only 20 edges. So I divide all vertices on two sets: set M, for subsets of that dp[mask] can be written, and all other, that can be colored before set M and will be constantly colored while calculating answer for dp.

      Set M includes all vertices, that have degree 2 and more, and one (not both) of the vertices from edge, where both vertices have degree 1. It's obvious, that maximal size of set M is 20, that acceptable for dp in bitmasks.

      → Reply