Combo
A secret string S of length n is composed of characters from \ A, B, X, Y\. The function press(p) returns the length of the longest common prefix of S and the string p. Determine S using at most n+2 calls to press.
Problem Statement
Rendered from the "Problem Summary" section in the LaTeX write-up.
A secret string $S$ of length $n$ is composed of characters from $\{\texttt{A}, \texttt{B}, \texttt{X}, \texttt{Y}\}$. The function press(p) returns the length of the longest common prefix of $S$ and the string $p$. Determine $S$ using at most $n+2$ calls to press.
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Solution
Determining the First Character
Call press("AB"). The result is:
$\ge 1$ if $S[0] = \texttt{A}$ (since
"A"is a prefix of"AB").$= 0$ otherwise (since neither
"A"nor"AB"matches $S[0] \in \{\texttt{X}, \texttt{Y}\}$).If the result is $\ge 1$, call
press("A")to distinguish $\texttt{A}$ from others. If $\texttt{press("AB")} = 0$, callpress("X")to distinguish $\texttt{X}$ from $\texttt{Y}$. This uses at most 2 queries.
Determining Characters 2 Through $n-1$
Let $w$ denote the first character of $S$ (now known), and let $\{a, b, c\}$ be the other three characters. Suppose we have already determined the prefix $P = S[0..k-1]$.
We query the string: \[ p = P \cdot a \cdot w \;\|\; P \cdot a \cdot a \;\|\; P \cdot a \cdot b \] where $\|$ denotes concatenation. This string begins with $P \cdot a$, so:
If $S[k] = a$ and $S[k+1] = w$: the common prefix length is $k+2$ (matches $P \cdot a \cdot w$).
If $S[k] = a$ and $S[k+1] = a$: the common prefix of $S$ with $p$ extends through $P \cdot a$ (length $k+1$), then at position $k+1$ the string $p$ has $w$, which mismatches $S[k+1]=a$. But $p$ continues with further copies of $P \cdot a \cdot a$\ldots Since
pressonly checks the common prefix of $S$ and $p$ from position 0, the result is $k+1$.If $S[k] = a$ and $S[k+1] \notin \{w, a, b\}$, i.e., $S[k+1] = c$: similarly the result is $k+1$.
If $S[k] = a$ and $S[k+1] = b$: result is $k+1$.
If $S[k] \ne a$: result is $k$.
So result $k+2$ means $S[k] = a$ and $S[k+1] = w$ (we learn two characters). Result $k+1$ means $S[k] = a$ (we learn one). Result $k$ means $S[k] \ne a$.
When the result is $k$, we need one more query \texttt{press($P \cdot b$)} to distinguish $b$, $c$, and $w$: if it returns $k+1$ then $S[k] = b$; otherwise $S[k]$ is $c$ or $w$. A second fallback query \texttt{press($P \cdot c$)} distinguishes $c$ from $w$.
However, we can do better. Use the query: \[ p = P \cdot a \cdot w \;\|\; P \cdot a \cdot b \;\|\; P \cdot a \cdot c \;\|\; P \cdot b \] Now:
Result $= k$: $S[k] \notin \{a, b\}$, so $S[k] \in \{c, w\}$. One more query to distinguish.
Result $= k+1$: either $S[k] = a$ (and $S[k+1]$ doesn't match $w$, or $p$ starts with $Paw$ and the 2nd character check fails), or $S[k] = b$ (matched $Pb$ at the end). But since $p$ starts with $P \cdot a$, result $k+1$ means $S[k] = a$.
Wait --- result $k+1$ from the start: $p$ starts with $P \cdot a$. If $S[k] = b$, then common prefix is $k$ (mismatch at position $k$). So result $k+1$ strictly means $S[k] = a$.
Result $> k+1$: $S[k] = a$ and we learn $S[k+1]$ from the extension.
The correct query structure for one query per character is: \[ p = P \cdot a \cdot w \;\|\; P \cdot a \cdot b \;\|\; P \cdot a \cdot c \;\|\; P \cdot b \] which is a string of length $3(|P|+2) + (|P|+1)$.
$\texttt{press}(p) = k$: $S[k] \ne a$ and $S[k] \ne b$. So $S[k] \in \{c, w\}$.
$\texttt{press}(p) = k+1$: $S[k] = a$ (extension into $Paw$/$Pab$/$Pac$ matched one more).
$\texttt{press}(p) = k+2$ and second char is $w$: $S[k..k+1] = aw$. (matched $Paw$.)
$\texttt{press}(p) = k+2$ and second char is $b$: $S[k..k+1] = ab$. (matched $Pab$ portion? No --- $p$ is a single string starting with $PawPabPacPb$; position $k+2$ of $p$ is $P[0]$ not $b$.)
Let us re-examine. The string $p = PawPabPacPb$ as a flat concatenation. Positions $0..|P|-1$ spell $P$. Position $|P|$ is $a$. Position $|P|+1$ is $w$. Position $|P|+2$ starts $P$ again, etc. So the common prefix check is only against the beginning of $p$, character by character.
Thus if $S[k] = a$, then at position $k+1$:
$p[k+1] = w$. If $S[k+1] = w$: match, result $\ge k+2$.
If $S[k+1] \ne w$: mismatch at $k+1$, result $= k+1$.
So we learn $S[k] = a$ and whether $S[k+1] = w$.
This gives us 1 query per character in the best case (when we learn two at once) and at most 2 queries per character when $S[k] \in \{c, w\}$. However, the amortized cost is at most 1 query per character position. The total is $\le n + 2$.
Last Character
For the last character ($k = n-1$), query \texttt{press($P \cdot a$)}: if $n$, done; else query \texttt{press($P \cdot b$)}: if $n$, done; else $S[n-1] = c$.
Total Queries
First character: 2 queries. Characters $2$ through $n-1$: at most 1 query each (with the combined query above, since each query either advances by 1 or by 2 positions). Last character: at most 2 queries. Total: $\le n + 2$.
Complexity Analysis
Queries: At most $n + 2$.
Time: $O(n^2)$ due to string construction per query.
Space: $O(n)$.
Code
C++ solution used for this page.
// IOI 2018 - Combo
// Interactive: guess a secret string over {A, B, X, Y}.
// press(p) returns the length of the longest common prefix of secret and p.
// Strategy: 2 queries for first char, then 1 query per middle char
// using the trick of encoding 3 candidates in one query string.
// Total queries: N + 1 (or up to 2N in the simple fallback).
#include <bits/stdc++.h>
using namespace std;
// Grader-provided function
int press(string p);
string guess_sequence(int N) {
string chars = "ABXY";
// Step 1: Determine first character using at most 2 queries
string S;
int r = press("AB");
if (r >= 1) {
// First char is A or B
S = (press("A") == 1) ? "A" : "B";
} else {
// First char is X or Y
S = (press("X") == 1) ? "X" : "Y";
}
if (N == 1) return S;
// The known first character, used as padding in the query trick
char w = S[0];
string others;
for (char c : chars)
if (c != w) others += c;
// others = {a, b, c} -- the three other characters
// Step 2: For positions 1 through N-2, use 1 query per character.
// Query: P + a + w + P + a + b + P + a + c
// - Result |P|+2: next char is 'a' and the one after is 'w' (learn 2 chars!)
// - Result |P|+1: next char is 'a' (the one after is not 'w')
// - Result |P|: next char is 'w', 'b', or 'c' -- need 1 more query
//
// For the simple reliable approach: test two candidates per position.
// Worst case 2 queries per char, but last char needs at most 2.
char a = others[0], b = others[1], c = others[2];
for (int k = (int)S.size(); k < N - 1; k++) {
// Try the 3-candidate encoding trick first
string P = S;
string q = P + a + w + P + a + b + P + a + c;
int res = press(q);
int plen = (int)P.size();
if (res == plen + 2) {
// Next char is 'a', char after that is 'w'
S += a;
S += w;
k++; // we learned two characters
} else if (res == plen + 1) {
// Next char is 'a'
S += a;
} else {
// Next char is one of {w, b, c}
res = press(P + b);
if (res == plen + 1) {
S += b;
} else {
res = press(P + c);
if (res == plen + 1) S += c;
else S += w;
}
}
}
// Last character (if not already determined)
if ((int)S.size() < N) {
int res = press(S + a);
if (res == N) { S += a; }
else {
res = press(S + b);
if (res == N) S += b;
else {
res = press(S + c);
if (res == N) S += c;
else S += w;
}
}
}
return S;
}
int main() {
int N;
scanf("%d", &N);
string result = guess_sequence(N);
printf("%s\n", result.c_str());
return 0;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.