\begin{frame}
    \frametitle{\problemtitle}
    \begin{description}
        % TODO: Remove this comment when you're done writing the solutions.
        \item<+->[Problem:] Given $n$ messages, $M_i$, find two messages which have at least $2$ symbols in common.
        The total size of all messages is not more than $m=100000$.
        \item<+->[Observation:] Build a bipartite graph with on one side the messages, and on the other the symbols.
            Want to find a $4$-cycle in the graph. 
        \item<+->[Naive solution $1$:] 
            Loop over all pairs of messages, and calculate the intersection of their symbol sets in $\mathcal O ( \text{min} ( |M_i|, |M_j| ) )$, 
                using hash sets or boolean arrays after using coordinate compression.
        Time complexity, roughly: $\mathcal O( n \sum_{i=1}^{n} \left| M_i  \right| )$
        \item<+-> When $n$ is small, works well, but can be quadratic.
        \item<+->[Naive solution $2$:]
        Loop over all pairs of symbols in each message. Check if any of these pairs is the same, by using a hash map.
        Time complexity: $\mathcal O( \sum_{i=1}^{n} \left| M_i  \right|^2 )$
        Works well when the sizes of the messages are small.
       
    \end{description}
\end{frame}

\begin{frame}
    \frametitle{\problemtitle}
    \begin{description}
        \item<+->[Reminder:]  Naive $1$: $\mathcal O ( \text{min} ( |M_i|, |M_j| ) )$ over all pairs of messages.

             Naive $2$: $\mathcal O( \sum_{i=1}^{n} \left| M_i  \right|^2 )$
         \item<+->[Solution:] The time limit and constraints are generous. Combine the naive solutions in a smart way to obtain a faster algorithm in the worst case.

            Divide messages in big and small messages, based on parameter $B$. Do casework:
        \item<+-> [Big-Big] Use naive solution $1$. Works in $\mathcal O(  \sum_{i \in \text{Bigs}} \left| M_i  \right| \frac{m}{B} ) = \mathcal O(\frac{m^2}{B}) $
        \item<+-> [Small-Big] Use naive solution $1$. Because of the minimum over the two message lengths, still $\mathcal O(\frac{m^2}{B}) $
        \item<+-> [Small-Small] Use naive solution $2$, works in $\mathcal O(m B)$ (worst case is all small messages are equal in size and $<B$. )

            This handles all the cases, and total complexity is $\mathcal O(\frac{m^2}{B} + m B)$, best when $B = \Theta ( \sqrt{m} )$.
        \item<+->[Running time:] $\mathcal O(m \sqrt{m})$ with a hash map. The algorithm has a considerable constant factor.
    \end{description}
\end{frame}
\begin{frame}
    \frametitle{\problemtitle}
    \begin{description}
        \item<+->[Bonus:] You can get rid of the hash map. 
            This requires in naive solution $2$ to order the computations in a smart way, such that a global boolean array can be used, which is set and unset for each message.
            Also requires sorting and coordinate compression beforehand. Same tricks need to be used in naive solution $1$.
        \item<+->[Bonus $2$:] The algorithm can be sped up to $\mathcal O(m \sqrt{\frac{m}{w}})$, 
            where $w$ is the word size of the machine (typically $32$ or $64$). This can be done with the use of bitsets in naive algorithm $1$.
            The details are an exercise for the interested reader.
        \item<+->[Alternative solution:] A time complexity of $\mathcal O(\frac{m^2}{w})$ can also get accepted when implemented well. (This is basically doing bonus $2$ without the square-root trick).
        \item<+->[Fun fact:] Constructions similar to problem F (Faulty Connection) are used in the testdata to make dense testcases with a \text{impossible} answer. 
    \end{description}
    \solvestats
\end{frame}