Cluedo
This is an interactive problem modeled after the board game Cluedo. There are M murderers, W weapons, and L locations. The secret answer is a triple (m^*, w^*, l^*). In each query you guess a triple (m, w, l) and the...
Problem Statement
Rendered from the "Problem Summary" section in the LaTeX write-up.
This is an interactive problem modeled after the board game Cluedo. There are $M$ murderers, $W$ weapons, and $L$ locations. The secret answer is a triple $(m^*, w^*, l^*)$. In each query you guess a triple $(m, w, l)$ and the system returns:
$0$ if the guess is correct,
$1$ if the murderer $m$ is wrong,
$2$ if the weapon $w$ is wrong,
$3$ if the location $l$ is wrong.
When multiple components are wrong, the system returns exactly one of them (any one). The goal is to find the correct triple within a limited number of queries.
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Solution
Algorithm
Maintain candidate sets $\mathcal{M}$, $\mathcal{W}$, and $\mathcal{L}$ (initially all murderers, weapons, and locations respectively). In each query, guess the triple formed by the current candidate from each set. Based on the response, eliminate the wrong candidate from its set. When a set has exactly one element, that element is correct and is never eliminated.
Correctness
Lemma.
Every query with a non-zero response eliminates at least one incorrect candidate.
Proof.
If the response is $1$, then the guessed murderer $m \neq m^*$, so removing $m$ from $\mathcal{M}$ is safe. The same argument applies for responses $2$ and $3$.
Theorem.
The algorithm terminates with the correct triple in at most $M + W + L - 3$ queries.
Proof.
Each query either finds the answer (response $0$) or eliminates one candidate. Since the correct candidate in each set is never eliminated, after removing all $M - 1$ wrong murderers, $W - 1$ wrong weapons, and $L - 1$ wrong locations, the triple is uniquely determined. This totals at most $(M-1) + (W-1) + (L-1) = M + W + L - 3$ eliminations.
Complexity
Queries: at most $M + W + L - 3$.
Time: $O(M + W + L)$ amortized (using index tracking instead of erasure).
Space: $O(M + W + L)$.
Code
C++ solution used for this page.
// IOI 2010 - Cluedo (Interactive)
// Elimination strategy: guess current candidates, eliminate wrong component.
// O(M + W + L) queries.
#include <bits/stdc++.h>
using namespace std;
// Grader-provided function.
// Returns: 0 if correct, 1 if murderer wrong, 2 if weapon wrong, 3 if location wrong.
int Theory(int m, int w, int l);
void Solve() {
// Standard Cluedo sizes; adjust if grader provides different values.
const int M = 6, W = 6, L = 9;
vector<int> murderers, weapons, locations;
for (int i = 1; i <= M; i++) murderers.push_back(i);
for (int i = 1; i <= W; i++) weapons.push_back(i);
for (int i = 1; i <= L; i++) locations.push_back(i);
int mi = 0, wi = 0, li = 0;
while (true) {
int result = Theory(murderers[mi], weapons[wi], locations[li]);
if (result == 0) return; // found the answer
if (result == 1) {
murderers.erase(murderers.begin() + mi);
if (mi >= (int)murderers.size()) mi = 0;
} else if (result == 2) {
weapons.erase(weapons.begin() + wi);
if (wi >= (int)weapons.size()) wi = 0;
} else {
locations.erase(locations.begin() + li);
if (li >= (int)locations.size()) li = 0;
}
}
}
// Stub main for compilation; in contest, grader calls Solve() directly.
int main() {
Solve();
return 0;
}
// Stub for standalone compilation.
int Theory(int /*m*/, int /*w*/, int /*l*/) { return 0; }
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.