Editorial for COCI '11 Contest 1 #3 X3

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.

The first useful observation is that individual binary digits of the friendship value are mutually independent, so they can be considered separately. If the $i^\text{th}$ $i^{th}$ digit of a result is equal to $1$ $1$ , a value of $2^i$ $2^{i}$ is added to the friendship value, otherwise $0$ $0$ is added.

A digit of the result is equal to $1$ $1$ only if the corresponding digits in extraterrestrial names differ. Since we are computing the total friendship value, we can count the number of appearances of $2^i$ $2^{i}$ (digit $1$ $1$ in position $i$ $i$ ) for each $i$ $i$ .

Let us denote by $K_i$ $K_{i}$ the number of extraterrestrials who have the digit $1$ $1$ in position $i$ $i$ in binary name notation. Then we add

$\displaystyle (K_i \times (N-K_i)) \times 2^i$ $(K_{i} \times (N - K_{i})) \times 2^{i}$

to the sum of friendships, since that is exactly the number of pairs with differing digits in position $i$ $i$ , multiplied by the weight of that digit position.

Comments

There are no comments at the moment.