yermak0v's blog

June Cook-Off 2013
By yermak0v, 11 years ago, In English

Hi all.
Today at 16:00 UTC will starts June Cook-Off 2013 on Codechef.
GL & HF to all!

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

»
11 years ago, # |
  Vote: I like it +5 Vote: I do not like it

How to solve Party Planning problem?

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

    The graph in this problem is a set of cycles with some trees attached to them. The answer for the whole graph is the product of answers for all connected components.

    In order to solve the problem for one connected component one can pick any vertex which belongs to the cycle and remove it from the graph trying both possibilities: to take this vertex to our set and not to take it. After removing one vertex the graph becomes a set of several trees. One can solve the problem separately for each tree and then multiply all the answers.

    Finally, for a single tree the problem can be solved with a simple DP where the state is the number of vertex and boolean parameter which says whether we take this vertex to our set or not.

    → Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 5   Vote: I like it +5 Vote: I do not like it

    Our answer is a product of answers for each component. In each component there are no more then 1 cycle. We pick guy from this cycle(or anybody, if there are no cycles) and calcucating answer when we will invite this guy and when won't. After this our graph won't have any cycles. Each part can be solved with dynamic on tree.

    → Reply