Editorial for COCI '19 Contest 3 #5 Sob

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Let's consider an ordered pair $(a, b)$ ~(a, b)~ to be good if $a \mathbin\& b = a$ ~a \mathbin\& b = a~.

We can solve the first subtask by matching $a \in A$ ~a \in A~ with $b \in B$ ~b \in B~ for which $b \bmod N = a$ ~b \bmod N = a~ holds.

The second subtask can be solved with the following algorithm. Let $i_1 > i_2 > \dots > i_k$ ~i_1 > i_2 > \dots > i_k~ be the positions of ones in a binary notation of $N$ ~N~. We will match the smallest $2^{i_1}$ ~2^{i_1}~ elements of $A$ ~A~ and $B$ ~B~ such that we match those $a$ ~a~ and $b$ ~b~ for which $a \equiv b \pmod{2^{i_1}}$ ~a \equiv b \pmod{2^{i_1}}~ holds. Then we take the following $2^{i_2}$ ~2^{i_2}~ elements and match those that are equal modulo $2^{i_2}$ ~2^{i_2}~, 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 $A$ ~A~ and $B$ ~B~. 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 $\mathcal O(NE)$ ~\mathcal O(NE)~ algorithm, where $E$ ~E~ denotes the number of edges and $N$ ~N~ denotes the number of nodes. Note that we can deduce the upper bound on $E < 3^{10} = 59\,049$ ~E < 3^{10} = 59\,049~.

The other way is by using the following greedy algorithm. We will traverse through the elements of $A$ ~A~ from largest to smallest and we will match the current element with the smallest unmatched element from $B$ ~B~ which forms a good pair with our current element in $A$ ~A~.

If we run this algorithm on a couple of examples, we can observe the following. Suppose that the largest element of $A$ ~A~, i.e. $N-1$ ~N-1~, is matched with $b \in B$ ~b \in B~. Then, $N-1-t$ ~N-1-t~ will also be matched with $b-t$ ~b-t~ for each $t \in \{1, 2, \dots, b-M\}$ ~t \in \{1, 2, \dots, b-M\}~. After we remove those matched pairs, we are left with the same problem on smaller sets $A' = \{0, 1, \dots, N-1-(b-M)-1\}$ ~A' = \{0, 1, \dots, N-1-(b-M)-1\}~ and $B' = \{b+1, b+2, \dots, M+N-1\}$ ~B' = \{b+1, b+2, \dots, M+N-1\}~. This solution can easily be implemented in $\mathcal O(N)$ ~\mathcal O(N)~.

Proof of the former observation:

Let $a = N-1$ ~a = N-1~ and let $b$ ~b~, as before, be the smallest element of $B$ ~B~ for which $a \mathbin\& b = a$ ~a \mathbin\& b = a~. With index $i$ ~i~ we will denote the $i^\text{th}$ ~i^\text{th}~ digit of weight $2^i$ ~2^i~. If $b = M$ ~b = M~ there is nothing left to prove, so we will assume that $b > M$ ~b > M~ and introduce $k = b-M$ ~k = b-M~. Let $i$ ~i~ be the position of the smallest significant one in $b$ ~b~. Obviously it must hold that $a_j = b_j = 0$ ~a_j = b_j = 0~ for all $j < i$ ~j < i~. If $a_i = 0$ ~a_i = 0~, then $a \mathbin\& (b-1) = a$ ~a \mathbin\& (b-1) = a~ would hold and $b$ ~b~ wouldn't be the smallest element in $B$ ~B~ that can be matched with $a$ ~a~. Therefore, $a_i = b_i = 1$ ~a_i = b_i = 1~. Now it's obvious that $(a-t, b-t)$ ~(a-t, b-t)~ is a good pair for $t \in \{1, 2, \dots, 2^i\}$ ~t \in \{1, 2, \dots, 2^i\}~. If $k \le 2^i$ ~k \le 2^i~, we are done, otherwise we observe the next smallest significant one in $b$ ~b~ and go through the same procedure inductively. The only thing left to prove is that there is always a $b \in B$ ~b \in B~ which can be matched with $a$ ~a~, but we will leave this part of the proof as an exercise for the reader.

Comments

There are no comments at the moment.