Editorial for An Animal Contest 7 P6 - S-Squirrel?
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Whenever the term "merging" is used in this editorial, it is referring to merging with Disjoint Set Union.
Subtask 1
We can observe that for each multiset, we only need to keep track of one node inside of it because all nodes inside of it will always be part of the same connected component. Thus, we can represent the multisets with an array of size , where each element is either to represent an empty multiset, or it is an arbitrary node in the multiset.
For queries of type , we simply loop through each index within and merge with if it is not equal to , and then we can set . To output the value of the graph, we can maintain the value of the graph and update it whenever we merge.
For queries of type , let be the set of components within . We know that no matter what node is randomly chosen, all of these components will be merged. So, we create a temporary value that is equal to the value of the graph after the components in are merged. We will then loop through every single node and find the value of the graph if this node was chosen. For a given node , if is in a component that is in , the value of the graph remains as . Otherwise, the value of the graph becomes where is the sum of component sizes in and is the size of 's component. We take the sum of all of the values for each possible node and then divide by to find the expected value because each node has an equal chance of being chosen.
Time Complexity:
Subtask 2
There are several solutions for this subtask, but we will go over the solution that most easily extends to the subtask 3 solution.
We can partition the array into disjoint intervals where each interval is either fully empty or "points" to the same component. For each query we will loop through the intervals that intersect and add the components to a set . Afterwards, we delete these intervals and replace it with at most intervals: one interval will be that points to , and then we will possibly need to add another interval to the left or right of this interval if we ended up erasing an interval that is only partially covered by . We will then merge everything in and update the value of the graph. We can maintain the intervals with a set. This solution is fast because every time we loop through an interval it gets erased and we are only creating up to intervals per query.
Time Complexity:
Subtask 3
The solution for this subtask is almost the same as subtask , except we need to instead add an interval that points to for type queries and also do a bit of math for the expected value. Let be the set of components within the interval , let be the sum of component sizes in , and let be the value of the graph after merging these components.
For nodes that are part of , when we choose them the value of the graph will still be . Taking the sum of all of the values after choosing these nodes, we get .
Let be a node that is not part of . If we choose , the value of the graph will be where is the size of node 's component. Expanding the expression, we get . Taking the sum across all nodes that are not part of , we get where is the sum of squares of all component sizes of and can be computed easily after looping through .
Finally, since each node has an equal chance of being chosen, we can see that the expected value of the graph is .
Time Complexity:
Comments