IOI 2009 - Day 0 - Museum
Next we have the "Museum" question.
Constructing a solution for N=2x
So have have N vases of integer heights {1,2,3, ... ,N-1,N}. We must arrange them in a sequence such that for any three vases A, B and C where the height of B is the average of the heights of A and C, vase B must not be positioned anywhere between A and C in the sequence.
Suppose we have a correct solution Z for N=x. Let's try to construct a solution Z' for N=2x.
The left x vases shall have heights 2×y-1 where y comes from Z. The right y vases shall have heights 2×y where y comes from Z.
The left vases all have odd heights, and the right vases all have even heights. So for any three vases A', B' and C' where one of A' and C' is on the left and the other is on the right, the height of B' will never equal the average height of A' and C' because the average of an odd number and an even number is not an integer.
For any three vases A', B' and C' where A' and C' are on the same side and B' is on the other, it doesn't matter whether B' is the average of A' and C' because it's clearly not between them.
This leaves us with only the case where all of A', B' and C' come from the same side as each other.
On the left
Assume that A', B' and C' are three vases on the left such that:
B' = (A' + C') / 2
and B' is between A' and C'. A', B' and C' correspond to three distinct vases A, B and C in our known good solution such that
A' = 2×A-1,
B' = 2×B-1 and
C' = 2×C-1
Substituting,
2×B-1 = (2×A - 1 + 2×C - 1) / 2
∴ 2×B-1 = (2×A + 2×C - 2) / 2
∴ 2×B-1 = (2×A + 2×C) / 2 - 1
∴ 2×B = (2×A + 2×C) / 2
∴ B = (A + C) / 2
But this cannot be because we know that Z is a correct solution and thus B ≠ (A + C) / 2. So we have a contradiction and our assumption must be false. So:
B' ≠ (A' + C') / 2
So if Z is correct then the left part of Z' is correct.
On the right
This works out almost exactly the same as the left. If Z is correct then the right part of Z' is correct.
Using this, we can construct a valid solution for any N=2x by starting with a trivial solution for N=1:
N=1: [1]
N=2: [1,2]
N=4: [1,3,2,4]
N=8: [1,5,3,7,2,6,4,8]
N=16: [1,9,5,13,3,11,7,15,2,10,6,14,4,12,8,16]
etc...
Solution for arbitrary N
This is easy. Just solve for the next larger power of 2 and then remove the tallest vases. Since we don't change the relative heights or ordering of the vases, removing vases doesn't affect the validity of the solution.
Solving without storing the entire list
If you observe the sequence in binary you will notice that it looks familiar. It will look even more familiar if we count from 0 to N-1 instead of 1 to N. It turns out we can just count from 0 to N-1 and reverse the binary bits in our counter to generate the numbers in the sequence. It's easy just to add and subtract one to convert back to the 1 to N values.
Output only???
Um, yeah. The question is output only, so they only want the output, not the program. Coming up with a clever, efficient solution turns out to be sort of pointless. You could have written an extremely slow, memory hungry algorithm and it wouldn't have mattered. Oh well.
I think all this is correct. It certainly seems to give correct answers.
Constructing a solution for N=2x
So have have N vases of integer heights {1,2,3, ... ,N-1,N}. We must arrange them in a sequence such that for any three vases A, B and C where the height of B is the average of the heights of A and C, vase B must not be positioned anywhere between A and C in the sequence.
Suppose we have a correct solution Z for N=x. Let's try to construct a solution Z' for N=2x.
The left x vases shall have heights 2×y-1 where y comes from Z. The right y vases shall have heights 2×y where y comes from Z.
The left vases all have odd heights, and the right vases all have even heights. So for any three vases A', B' and C' where one of A' and C' is on the left and the other is on the right, the height of B' will never equal the average height of A' and C' because the average of an odd number and an even number is not an integer.
For any three vases A', B' and C' where A' and C' are on the same side and B' is on the other, it doesn't matter whether B' is the average of A' and C' because it's clearly not between them.
This leaves us with only the case where all of A', B' and C' come from the same side as each other.
On the left
Assume that A', B' and C' are three vases on the left such that:
B' = (A' + C') / 2
and B' is between A' and C'. A', B' and C' correspond to three distinct vases A, B and C in our known good solution such that
A' = 2×A-1,
B' = 2×B-1 and
C' = 2×C-1
Substituting,
2×B-1 = (2×A - 1 + 2×C - 1) / 2
∴ 2×B-1 = (2×A + 2×C - 2) / 2
∴ 2×B-1 = (2×A + 2×C) / 2 - 1
∴ 2×B = (2×A + 2×C) / 2
∴ B = (A + C) / 2
But this cannot be because we know that Z is a correct solution and thus B ≠ (A + C) / 2. So we have a contradiction and our assumption must be false. So:
B' ≠ (A' + C') / 2
So if Z is correct then the left part of Z' is correct.
On the right
This works out almost exactly the same as the left. If Z is correct then the right part of Z' is correct.
Using this, we can construct a valid solution for any N=2x by starting with a trivial solution for N=1:
N=1: [1]
N=2: [1,2]
N=4: [1,3,2,4]
N=8: [1,5,3,7,2,6,4,8]
N=16: [1,9,5,13,3,11,7,15,2,10,6,14,4,12,8,16]
etc...
Solution for arbitrary N
This is easy. Just solve for the next larger power of 2 and then remove the tallest vases. Since we don't change the relative heights or ordering of the vases, removing vases doesn't affect the validity of the solution.
Solving without storing the entire list
If you observe the sequence in binary you will notice that it looks familiar. It will look even more familiar if we count from 0 to N-1 instead of 1 to N. It turns out we can just count from 0 to N-1 and reverse the binary bits in our counter to generate the numbers in the sequence. It's easy just to add and subtract one to convert back to the 1 to N values.
Output only???
Um, yeah. The question is output only, so they only want the output, not the program. Coming up with a clever, efficient solution turns out to be sort of pointless. You could have written an extremely slow, memory hungry algorithm and it wouldn't have mattered. Oh well.
I think all this is correct. It certainly seems to give correct answers.