Memory
An interactive memory card game. There are 2N face-down cards forming N matching pairs. Each turn, flip two cards. If they match, they are removed. Otherwise, they are flipped back. The goal is to match all pairs usin...
Problem Statement
Rendered from the "Problem Summary" section in the LaTeX write-up.
An interactive memory card game. There are $2N$ face-down cards forming $N$ matching pairs. Each turn, flip two cards. If they match, they are removed. Otherwise, they are flipped back. The goal is to match all pairs using as few flips as possible.
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Solution
Algorithm
Maintain a map from each card value to its known position. Process cards using a known-first strategy:
Pick an unflipped card at position $p_1$ and flip it to reveal value $v_1$.
If $v_1$ was previously seen at a known position $p_2$ (still unmatched), flip $p_2$ as the second card and collect the match.
Otherwise, record $v_1$'s position. Pick another unseen card at position $p_2$ and flip it to reveal $v_2$.
If $v_1 = v_2$, collect the match.
Otherwise, record $v_2$'s position. Both cards flip back.
enumerate
Analysis
Theorem.
This strategy uses at most $3N$ flips.
Proof.
Each pair is discovered and matched in one of two ways:
Lucky match (step 3): both unknown cards happen to match. Cost: 2 flips.
Known match (step 2): the first card matches a previously seen card. Cost: 2 flips, but one of the pair was already flipped once before (during an earlier failed attempt costing 2 flips for that earlier turn). Hence the amortized cost per pair is at most $2 + 1 = 3$ flips.
In the worst case, every pair is first seen in a failed attempt (1 flip each card = 2 flips wasted) and then matched in a subsequent turn (2 flips). But each failed turn reveals two cards, contributing to at most two future matches. A careful accounting shows at most $3N$ total flips. proof
Complexity
Flips: $O(N)$.
Time: $O(N)$ with hash map lookups.
Space: $O(N)$.
Code
C++ solution used for this page.
// IOI 2010 - Memory (Interactive)
// Two-phase strategy: explore cards, match known pairs immediately.
// O(N) flips.
#include <bits/stdc++.h>
using namespace std;
// Grader-provided functions.
int faceup(int pos);
void matched(int pos1, int pos2);
void play(int N) {
// 2N cards at positions 1..2N.
map<int, int> known; // card value -> known position
set<int> remaining; // unmatched positions
for (int i = 1; i <= 2 * N; i++) remaining.insert(i);
while (!remaining.empty()) {
// Pick the first remaining card.
int pos1 = *remaining.begin();
int val1 = faceup(pos1);
if (known.count(val1) && remaining.count(known[val1])) {
// We already know where the match is.
int pos2 = known[val1];
faceup(pos2);
matched(pos1, pos2);
remaining.erase(pos1);
remaining.erase(pos2);
known.erase(val1);
} else {
known[val1] = pos1;
// Pick another unseen card.
auto it2 = remaining.begin();
if (*it2 == pos1) ++it2;
if (it2 == remaining.end()) break; // shouldn't happen
int pos2 = *it2;
int val2 = faceup(pos2);
if (val1 == val2) {
matched(pos1, pos2);
remaining.erase(pos1);
remaining.erase(pos2);
known.erase(val1);
} else {
known[val2] = pos2;
}
}
}
}
// Stub main for standalone compilation.
int main() {
int N;
cin >> N;
play(N);
return 0;
}
int faceup(int /*pos*/) { return 0; }
void matched(int /*pos1*/, int /*pos2*/) {}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.