Editorial for COCI '19 Contest 3 #5 Sob
Submitting an official solution before solving the problem yourself is a bannable offence.
Let's consider an ordered pair to be good if .
We can solve the first subtask by matching with for which holds.
The second subtask can be solved with the following algorithm. Let be the positions of ones in a binary notation of . We will match the smallest elements of and such that we match those and for which holds. Then we take the following elements and match those that are equal modulo , and so on. The proof of correctness is left as an exercise for the reader.
The third subtask can be solved in multiple ways. One of those ways is to build a bipartite graph in which each node corresponds to one member of the sets and . Naturally, we add edges between all good pairs of nodes. The problem now boils down to bipartite matching which could have been implemented by a standard algorithm, where denotes the number of edges and denotes the number of nodes. Note that we can deduce the upper bound on .
The other way is by using the following greedy algorithm. We will traverse through the elements of from largest to smallest and we will match the current element with the smallest unmatched element from which forms a good pair with our current element in .
If we run this algorithm on a couple of examples, we can observe the following. Suppose that the largest element of , i.e. , is matched with . Then, will also be matched with for each . After we remove those matched pairs, we are left with the same problem on smaller sets and . This solution can easily be implemented in .
Proof of the former observation:
Let and let , as before, be the smallest element of for which . With index we will denote the digit of weight . If there is nothing left to prove, so we will assume that and introduce . Let be the position of the smallest significant one in . Obviously it must hold that for all . If , then would hold and wouldn't be the smallest element in that can be matched with . Therefore, . Now it's obvious that is a good pair for . If , we are done, otherwise we observe the next smallest significant one in and go through the same procedure inductively. The only thing left to prove is that there is always a which can be matched with , but we will leave this part of the proof as an exercise for the reader.