Editorial for IOI '10 P5 - Memory

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.

This was intended to be another very easy task, though slightly more difficult than the one on Day 1 when aiming for a full score.

Turning each possible pair of cards face up in some sequence is guaranteed to obtain all 25 candies. There are \binom{50}{2} = \frac{50 \times 49}{2} = 1225 such pairs. Hence, doing 2450 card turns (that is, calls to faceup) suffices. This can be programmed with two nested for-loops, and it solves Subtask 1.

But it does not solve Subtask 2, where no more than 100 card turns are allowed. Note that the try-all-pairs solution does not look at what is on the cards that are turned face up. That is, it does not make use of the values returned by faceup. By using these returned values, you can gather information that can be used later to reduce the number of cards turned up.

In particular, taking this to an extreme, you can first turn all cards, in pairs, to discover and record where all the letters are, without caring about turning up equal pairs. In this first round, you might already obtain some candies by accident, but that is irrelevant. In the next round, you know where equal pairs are and you can flip them, in sequence, to obtain all remaining candies.

The first round requires 50 turns (calls to faceup), and the second round another 50 turns. Thus, altogether 100 times a card is turned, and thereby Subtask 2 is solved.

In the second round, you could skip equal pairs that were already identified in the first round. However, that will not improve the worst-case performance and it will complicate the coding.


There are no comments at the moment.