## Editorial for IOI '10 P5 - Memory

**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 candies. There are such pairs. Hence, doing 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 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 turns (calls to **faceup**), and the second round another turns. Thus, altogether 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.

## Comments