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

Comments

There are no comments at the moment.