Editorial for COCI '22 Contest 5 #2 Diskurs
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:
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.
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 .