Hi all.

Today at 16:00 UTC will starts June Cook-Off 2013 on Codechef.

GL & HF to all!

# | User | Rating |
---|---|---|

1 | tourist | 3707 |

2 | Benq | 3672 |

3 | Radewoosh | 3655 |

4 | ksun48 | 3547 |

5 | jiangly | 3492 |

6 | Miracle03 | 3480 |

7 | ecnerwala | 3400 |

8 | maroonrk | 3385 |

9 | peehs_moorhsum | 3384 |

10 | sunset | 3338 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 215 |

2 | YouKn0wWho | 190 |

2 | Um_nik | 190 |

4 | sus | 183 |

5 | awoo | 182 |

6 | Errichto | 179 |

7 | tourist | 177 |

8 | -is-this-fft- | 173 |

9 | Radewoosh | 170 |

10 | Ashishgup | 169 |

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/29/2021 01:54:59 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

How to solve Party Planning problem?

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.

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.