An IMO Problem for Competitive Programmers

Revision en2, by rng_58, 2015-07-20 15:46:49

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.

Tags imo

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English rng_58 2015-07-20 15:46:49 4 Tiny change: ' $mask <<= 1$;</fon' -> ' $mask >>= 1$;</fon'
en1 English rng_58 2015-07-20 14:14:25 1326 Initial revision (published)