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.
Comments