Editorial for ICPC NEERC 2010 C - Cactus Revolution
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
- Use DFS to find and enumerate all loops in the graph.
- Use DFS on a cactus to partition it:
- Each partitioning procedure returns the remainder nodes that do not sum up to the target size of partition ().
- Partition a node by recursively partitioning the loops it is a part of (with the exception of a parent loop, if any) and its child nodes (with the exception of a parent node, if any)
- Remainders must add up to less than target size
- Loops (without one node) are partitioned by recursively partitioning all nodes on a loop, then combining result.
- To combine the result we have to find an integer , so that some number of first remainders sum up to , some next ones sum up to , next to , etc.
- is a running sum of remainders modulo .
- Find which sum modulo is the most popular and try it as a candidate
- Treat zero reminders on a loop in a special way
Comments