Editorial for IOI '09 Practice Task 3 - Museum

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.

To solve this problem, we start by observing that if we have three vases with heights $A$ ~A~, $B$ ~B~ and $C$ ~C~, such that either $A$ ~A~ is odd and $C$ ~C~ even, or $A$ ~A~ even and $C$ ~C~ odd, then no matter what $B$ ~B~ is these three vases will not violate the condition of the exhibition organizers. This is because $A+C$ ~A+C~ must therefore be odd, and so is not divisible by two, meaning that it is impossible for $B$ ~B~ to be the average of $A$ ~A~ and $C$ ~C~.

We therefore start by arranging the vases such that we place all the even vases first, and all the odd vases second. This gives an arrangement that looks like this:

$\displaystyle E_1\ E_2\ \dots\ E_p\ O_1\ O_2\ \dots\ O_q$

where $E_1, E_2, \dots, E_p$ ~E_1, E_2, \dots, E_p~ are the even heights in some order, and $O_1, O_2, \dots, O_q$ ~O_1, O_2, \dots, O_q~ are the odd heights in some order.

Now consider any heights $A$ ~A~, $B$ ~B~, $C$ ~C~ which violate the organizers' requirements. By the observations above, either $A$ ~A~ and $C$ ~C~ are both even (in which case $B$ ~B~ is even, since it appears between $A$ ~A~ and $C$ ~C~ and all the even values are grouped together), or $A$ ~A~ and $C$ ~C~ are both odd (in which case $B$ ~B~ is also odd). In other words, we can consider the problems of ordering the even numbers and the odd numbers separately.

Now suppose that $a_1, a_2, \dots, a_p$ ~a_1, a_2, \dots, a_p~ is a permutation of the heights $1, 2, \dots, p$ ~1, 2, \dots, p~ which satisfies the organizers' requirements (this is a smaller instance of the problem, so it can be solved by divide-and-conquer). Then simply assigning $E_i = 2a_i$ ~E_i = 2a_i~ will satisfy the requirements on the even values. Similarly, given a permutation $b_1, b_2, \dots, b_q$ ~b_1, b_2, \dots, b_q~ of the heights $1, 2, \dots, q$ ~1, 2, \dots, q~ which satisfies the requirements, we can assign $O_i = 2b_i-1$ ~O_i = 2b_i-1~.

Examining the properties of the resulting sequence gives another approach to generating the same solution. We can write all the heights in binary form, and then sort them according to the reverse of their binary form. This sorts first on the least significant bit (i.e., on whether they are odd or even), then the next least significant bit and so on. To prove that this solution is valid, note that if $B$ ~B~ is the average of $A$ ~A~ and $C$ ~C~, then at the least significant bit that $A$ ~A~ and $B$ ~B~ first differ, $A$ ~A~ and $C$ ~C~ must have the same value for that bit, placing $A$ ~A~ and $C$ ~C~ in a separate group from $B$ ~B~ when sorting on that bit.

Comments

There are no comments at the moment.