\begin{frame}
    \frametitle{\problemtitle}

    \begin{columns}[T]
        \begin{column}{0.7\textwidth}
            \begin{description}
        

                \item<+->[Problem:] Given $n$ models on a gaming board, 
                    represented as non-overlapping disks with diameter between $25$ and $165$ \text{mm}.
                    Check coherency.

                \item<+-> Models are \emph{coherent} if they can reach each other. Models are adjacent when $\leq 2$ inches apart.
                For $n \geq 7$, each model must have at least two neighbors, for coherency.

                \item<+->[Naive solution:] Check adjacency for all pairs of models in $\mathcal O(n^2)$. 
                \item<+-> Make a graph of $n$ nodes, and represent adjacency as undirected edges.
                \item<+-> Run your favourite algorithm for finding connected components, and check degrees, for $n \geq 7$.
                \item<+-> In total, $\mathcal O(n^2)$. This is too slow, as $n \leq 200000$.


            \end{description}
        \end{column}

        \begin{column}{0.3\textwidth}
            \centering
            \includegraphics[width=\linewidth]{sample04.pdf}
            \captionof{figure}{Example board configuration (example $4$)}
        \end{column}
    \end{columns}
\end{frame}

\begin{frame}
    \frametitle{\problemtitle}
    \begin{columns}[T]

    \begin{column}{0.5\textwidth}
    \begin{description}
        \item<+->[Idea:] Use a grid of cells of $211$ x $211$ \text{mm}.
        \item<+-> Centres of disks are placed into corresponding cell.
            This can be done with a map / dictionary, in $\mathcal O(n \log n)$ or $\mathcal O(n)$.
        \item<+->[Observation:] Disks do not influence disks in non-adjacent cells ($8$-adjacency).  (this is why 211 \text{mm} is chosen) 


        \item<+->[Algorithm:] For each disk, loop through all $8$ adjacent cells, and its own cell, and check all candidate disks for adjacency.

            DFS, BFS or DSU can be used to find the connected components.
        \item<+->[Time complexity?]
    \end{description}
    \end{column}

    \begin{column}{0.5\textwidth}
        \centering
        \includegraphics[width=\linewidth]{visgrid.pdf}
        \captionof{figure}{Secret testcase}
    \end{column}
    \end{columns}
    % TODO: Fill in the smart solution here.
    \solvestats

\end{frame}

\begin{frame}
    \frametitle{\problemtitle}
    \begin{columns}[T]

    \begin{column}{0.6\textwidth}
    \begin{description}
        \item<+->[Time complexity:] Time complexity is $\mathcal{O}(n \times 9 \times \text{Max number of disks in one cell})$
        \item<+-> Roughly $\mathcal{O}(900 \times n)$
        \item<+->[More precise:] Cells need to be $\Omega(D_\text{max})$ \text{mm} big, 
            so $\mathcal{O}(\left(\frac{D_\text{max}}{D_\text{min}}\right)^2 )$ disks of the minimum diameter fit inside one cell

        \item<+-> Many alternative solutions possible, but based on similar ideas.
        
    \end{description}
    \end{column}

    \begin{column}{0.4\textwidth}
        \centering
        \includegraphics[width=\linewidth]{worstcase.pdf}
        \captionof{figure}{Worst case triangular packing with smallest diameter.}
    \end{column}
    \end{columns}
    % TODO: Fill in the smart solution here.
    \solvestats

\end{frame}
