\begin{frame}
    \frametitle{\problemtitle}
    \begin{block}{Problem}
        There are $n$ variables $x_1, x_2, \dots, x_n$, initially set to $2023$.
        You are given $m$ queries that either assigns $x_i$ to $x_i^{x_j}$, or
        asks you to compare $x_i$ and $x_j$.
    \end{block}
    %% \pause
    \begin{block}{Observation}
        \begin{itemize}
            \item<+-> To make the numbers slightly less huge, take the logarithm twice. Let
            $y_i = \log\log(x_i)$.
            \item<+-> $x_i = x_i^{x_j}  \equiv  y_i = y_i + 2023^{y_j}$.
            \item<+-> Consider these numbers in base $2023$.
            Each operation, one of the digits will increase by one. But no carry will ever happen since
            there are fewer than $2023$ operations.
        \end{itemize}
    \end{block}
\end{frame}

\begin{frame}
    \frametitle{\problemtitle}
    \begin{block}{Solution}
        \begin{itemize}
            \item<+-> Represent every variable as a list containing the positions of its non-zero digits. 
            Two such numbers can be compared by lexicographically comparing their lists.
            \item<+-> When a variable gets updated, it is much easier to
            create a new variable $y' = y_i + 2023^{y_j}$.
            \item<+-> Order the variables by size at all times. When a
            new variable $y'$ is created, copy the list of $y_i$ and add $y_j$ to it.
            Sort the list of $y'$ and insert it into the order.  
            \item<+-> The ordering can be a trie, or just an array.
            This can be done in $\mathcal{O}(n^2)$ or $\mathcal{O}(n^2\log(n))$.
            \item<+-> \textbf{Challenge}: can you solve the problem faster than quadratic time?
        \end{itemize}
    \end{block}
    \solvestats
\end{frame}
