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

How can I solve problem GPerm ?

Автор ps06756, история, 8 лет назад, По-английски

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 ?

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

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

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.

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

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

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

      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.

      → Ответить