
\begin{frame}
    \frametitle{\problemtitle}
    \begin{description}
        \item<+->[Problem:] Find the fastest possible time to visit floors $f_1,\ldots,f_n$ with optimal starting configuration of the elevators.
        \item<+->[Observation 1:] Label the elevators A,B,C,D. We can assume that A starts on floor $0$. Indeed, if no elevator starts on floor $0$, we can move each elevator ahead until one does.
        \item<+->[Observation 2:] Consider a directed graph on the elevators, by drawing an edge from X to Y whenever X arrives perfectly on time at some point where Y was used most recently. Then from each used elevator, there must be a path in this graph to elevator A. Otherwise, we can move all reachable elevators ahead until a new edge emerges.
        \item<+->[Conclusion:] We can assume there is an edge from B to A, from C to at least one of A or B, and from D to at least one of A or B or C, giving $6$ graphs to consider.
        \item<+->[Solution:] Iterate all $6$ graphs and all $n^3$ possible floors where the perfect transitions take place. This determines the starting positions of all elevators, from which we can simulate the corresponding solution.
        \item<+->[Running time:] For $k$ elevators, with $\mathcal{O}(kn)$ time per simulation, the running time is $\mathcal{O}(k!n^k)$.
    \end{description}
    \solvestats
\end{frame}
