Recently IMO 2015 has ended. Problem 6 was the hardest one and solved by only 11 contestants, but for competitive programmers this task wasn't that hard. If you are interested in it, I think it's worth trying even if you haven't solved any IMO problems.

The problem statement is here.

I wrote some hints in white characters.

Hint 1: How is it related to competitive programming?

Hint 2: Doesn't it look like bitmask DP?

Hint 3: Run the following program.

*mask* = 0;

for( *i* =1;; *i*++){

*mask*» = 1;

*mask*| = (1«(*a* _{ i} - 1)); // here the newly set bit must be 0 before this operation

}

Hint 4: The number of '1' bits in *mask* is non-decreasing while the program is running.

So, the number of '1' bits will be constant at some moment: call it *b*.

Then, the sum of (*a* _{ j} - *b*) is the difference of sum of positions of set bits in *mask* when *i* = *m* and *i* = *n*.