IOI 2010 - Memory

// 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*/) {}

\documentclass[11pt,a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage[margin=1in]{geometry}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{listings}
\usepackage{xcolor}
\usepackage{hyperref}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}

\lstset{
  language=C++,
  basicstyle=\ttfamily\small,
  keywordstyle=\color{blue}\bfseries,
  commentstyle=\color{green!60!black},
  stringstyle=\color{red!70!black},
  numbers=left,
  numberstyle=\tiny\color{gray},
  breaklines=true,
  frame=single,
  tabsize=4,
  showstringspaces=false
}

\title{IOI 2010 -- Memory}
\author{Solution}
\date{}

\begin{document}
\maketitle

\section{Problem Summary}
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.

\section{Solution}

\subsection{Algorithm}
Maintain a map from each card value to its known position. Process cards using a \emph{known-first} strategy:

\begin{enumerate}
    \item Pick an unflipped card at position $p_1$ and flip it to reveal value $v_1$.
    \item 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.
    \item Otherwise, record $v_1$'s position. Pick another unseen card at position $p_2$ and flip it to reveal $v_2$.
    \begin{itemize}
        \item If $v_1 = v_2$, collect the match.
        \item Otherwise, record $v_2$'s position. Both cards flip back.
    \end{itemize}
\end{enumerate}

\subsection{Analysis}

\begin{theorem}
This strategy uses at most $3N$ flips.
\end{theorem}
\begin{proof}
Each pair is discovered and matched in one of two ways:
\begin{itemize}
    \item \emph{Lucky match} (step 3): both unknown cards happen to match. Cost: 2 flips.
    \item \emph{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.
\end{itemize}
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.
\end{proof}

\subsection{Complexity}
\begin{itemize}
    \item \textbf{Flips:} $O(N)$.
    \item \textbf{Time:} $O(N)$ with hash map lookups.
    \item \textbf{Space:} $O(N)$.
\end{itemize}

\section{Implementation}

\begin{lstlisting}
#include <bits/stdc++.h>
using namespace std;

// Grader functions
int faceup(int pos);            // flip card, return value
void matched(int pos1, int pos2); // declare a match

void play(int N) {
    unordered_map<int, int> known; // value -> position of a seen card
    set<int> remaining;
    for (int i = 1; i <= 2 * N; i++) remaining.insert(i);

    while (!remaining.empty()) {
        int pos1 = *remaining.begin();
        int val1 = faceup(pos1);

        if (known.count(val1) && remaining.count(known[val1])) {
            // Match with a previously seen card
            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 it = remaining.begin();
            if (*it == pos1) ++it;
            if (it == remaining.end()) break;
            int pos2 = *it;
            int val2 = faceup(pos2);

            if (val1 == val2) {
                matched(pos1, pos2);
                remaining.erase(pos1);
                remaining.erase(pos2);
                known.erase(val1);
            } else {
                known[val2] = pos2;
            }
        }
    }
}
\end{lstlisting}

\end{document}