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.

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 ( $t = n/k$ ~t = n/k~).
- 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 $s$ ~s~ $(0 \le s < t)$ ~(0 \le s < t)~, so that some number of first remainders sum up to $s$ ~s~, some next ones sum up to $s+t$ ~s+t~, next to $s+2t$ ~s+2t~, etc.
- $s$ ~s~ is a running sum of remainders modulo $t$ ~t~.
- Find which sum modulo $t$ ~t~ is the most popular and try it as a candidate $s$ ~s~
- Treat zero reminders on a loop in a special way

Comments

There are no comments at the moment.