## Editorial for COCI '22 Contest 5 #2 Diskurs

**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 . For a number , let be a number that has *flipped*
binary representation.

For example, for and it follows because and . Exactly would
be the ideal candidate for the biggest *Hamming distance* with , but is not necessarily a part of .

Let us describe two possible solutions:

#### Solution 1

First solution is based on the fact that

Intuitively, we want a number as similar to as possible.

Let us try to calculate the minimal *Hamming distance* for every number in . For every number
that appears in it is . It leads us to a BFS solution, where each number in 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 in our queue and we will get the desired
minimal distances.

#### Solution 2

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

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

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

Then, the solution for some will be given as . The above can be calculated with standard dp with bitmasks methods.

Complexity of both solutions is .

## Comments