Editorial for Yet Another Contest 7 P3 - No More Math Homework
Submitting an official solution before solving the problem yourself is a bannable offence.
There are two aspects of this problem: determining an allocation of students to study groups, and determining the optimal adjustment to the plan.
Determining an allocation of students to study groups
The first thing to do is to rephrase this problem under a graph theory framework. We have a functional graph with edges from to . Define as the node reached after traversing edges, starting from node . We require that implies that and are in the same study group.
Recall that every component in a functional graph is a directed cycle, where each node on the cycle is the root of a directed tree. It follows that every student will spend the first few days moving along one of these trees, and once the have reached the root of the tree, they will move around a cycle indefinitely.
Since students on the same node must belong to the same study group, the number of study groups is bounded by the sum of cycle sizes. As it turns out, this bound is always achievable; assign student to the -th study group. (We can use some other big number instead of , such as .) We can obtain these values using by computing, for each node, the distance to a cycle and the length of that cycle. We could alternatively implement binary lifting.
Determining the optimal adjustment to the plan
We are allowed to change the successor of a single node, and want to maximise the sum of cycle sizes. How can we do this?
After some thought, the biggest increase to the sum of cycle sizes is the maximum depth of any tree. Consider the tree with the maximum depth, and assume it has more than one node (otherwise the sum of cycle sizes cannot be increased, and it suffices to choose ). Let be the root of this tree, be the deepest leaf, be the child of which contains in its subtree, and be the node which is part of the same cycle as with . Then, there are two constructions:
- Choose and , creating a new component.
- Choose and , increasing the size of the cycle in the current component.
Time complexity: or