Editorial for COCI '22 Contest 5 #2 Diskurs


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 look at the numbers as bitstrings of length m. For a number x, let x^c be a number that has flipped binary representation.

For example, for m = 5 and x = 13 it follows x^c = 18 because x = 01101_2 and x^c = 10010_2. Exactly x^c would be the ideal candidate for the biggest Hamming distance with x, but x^c is not necessarily a part of a.

Let us describe two possible solutions:

Solution 1

First solution is based on the fact that

\displaystyle \max_{y \in a} hamming(x, y) = m-\min_{y \in a} hamming(x^c, y)

Intuitively, we want a number as similar to x^c as possible.

Let us try to calculate the minimal Hamming distance for every number in [0, 2^m-1]. For every number that appears in a it is 0. It leads us to a BFS solution, where each number in [0, 2^m-1] is a node in our graph and the edges represent changing exactly one bit. In a graph constructed in such a fashion Hamming distance between two numbers is exactly the length of shortest path between corresponding nodes. So we start BFS algorithm with every number from a in our queue and we will get the desired minimal distances.

Solution 2

Second solution is based on dynamic programming. Let popcount(x) be the number of ones in the binary representation of x. The solution will be based on the following identity:

\displaystyle hamming(x, y) = popcount(x) + popcount(y) - 2 \cdot popcount(x \mathbin{\&} y)

Intuitively, each one in the binary representation of each number contributes 1 to Hamming distance, but then each common one decreases it by 2.

We want to calculate dp(mask) - maximum number of ones for some number in a but each one that is not in mask we penalize by 2. Formally,

\displaystyle dp(mask) = \max_{x \in a} (popcount(x) - 2 \cdot popcount(x \mathbin{\&} mask^c))

Then, the solution for some x will be given as popcount(x) + dp(x^c). The above dp can be calculated with standard dp with bitmasks methods.

Complexity of both solutions is \mathcal O(2^m \cdot m).


Comments

There are no comments at the moment.