At the end of the class, participants were assigned to solve the following problem and
dm me the solution if they had found it. If you are reading this now, give it a try!
Task: Computer has a hidden string $s$ of length $n$, where $s_i
\in \{A,B,X,Y\}$. Although you don't know the string $s$, you know its
length $n$. You also know that the first character of $s$ never reappears
in it. You can use the utility function $\texttt{ask}(p)$, where $p$ is a
string, $p_i \in \{A,B,X,Y\}$, $|p| \le 4n$. It returns the the length of
the longest prefix of $s$ that is also a substring of $p$. Your target is
to find $s$ using $\texttt{ask}$ as few times as possible. Subtasks:
(5 points) $n = 3$.
(95 points) Let $q$ be the number of calls to $\texttt{ask}$.
If $q \le n+2$, your score is 95.
If $n+2 < q \le n+10$, your score is 95 - 3(q-n-2).