Editorial for DMOPC '18 Contest 5 P6 - An XOR Problem
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
For the first subtask, a few initial observations are needed. Note that if for some
and
, then nodes
and
may be connected at no cost, even after updates. So multiple nodes with the same value may be discarded and there will be at most
important nodes. Another observation is that there are only
residues modulo
, so we can precompute the answer for each of these residues and then answer each update in
. With these in mind, a straightforward implementation of Kruskal's can pass in time.
Time Complexity:
For the next subtask, the Kruskal's must be optimized to subquadratic time. Split the nodes into two sets: those with the largest bit, and those without. Note that because the edges are sorted by weight, the edges between nodes in the same set will always be considered before the edges between the two sets. To combine the two sets, only one edge is necessary (since each set is already connected) and this edge can be found by building a trie from one set and checking every node in the other set against the trie.
Time Complexity:
Note that the Kruskal's in the solution to the second subtask implicitly formed a binary tree. For the third subtask, we will focus on this structure. Consider the subtrees with height from the bottom of the complete binary tree. Note that if
divides
, then for
, these subtrees will move but they themselves will not change. Then we can precompute the total weight within each of these subtrees, as well as the minimum weight between every two of these subtrees. Then for each update, we only need to apply the Kruskal's to the first
levels and use the precomputed values. Finally, since
divides
, there are only
important residues mod
.
Time Complexity:
For the final subtask, we build on this idea of unchanging subtrees of height . To force this condition in subtask 3, we can construct a sequence of
's which has most
's divisible by
. For example, when
, one such sequence of
's would be
which covers all residues mod
. However, even after constructing this sequence, we cannot simply apply the exact same idea as subtask 3. This is because we need to do the precomputing between every pair of subtrees for each time
is not divisible by
, which is
times. This would lead to a time complexity of
for precomputing alone.
To deal with this, an optimization is necessary for the precomputation. Consider subtrees of height in these subtrees of height
. There are only
possible subtrees. The minimum edge weight between every two of these subtrees can be precomputed and this only needs to be done once. Then, these values are used in precomputing the values of subtrees of height
, and then the solution from subtask 3 can be used.
Time Complexity:
In the model solution, we choose .
Comments