\documentclass{beamer}
\mode<presentation>
{
\usetheme{Warsaw}
% \setbeamercovered{transparent}
}
\usepackage{amsmath,amsfonts,array,eepic,graphics}
%\newcolumntype{d}{D{.}{.}{-1}}
\usepackage{times}
%\usepackage[T1]{fontenc}
\usepackage{subfigure}
\title[RMRC 2015 Solution Sketches]
{2015 Rocky Mountain Regional \\ Programming Contest \\ \ \\ Solution Sketches}
%\author % (optional, use only with lots of authors)
%{Howard Cheng}
% - Use the \inst command only if there are several affiliations.
% - Keep it simple, no one is interested in your street address.
\date
{}
% Delete this, if you do not want the table of contents to pop up at
% the beginning of each subsection:
%\AtBeginSubsection[]
%{
% \begin{frame}<beamer>
% \frametitle{Outline}
% \tableofcontents[currentsection,currentsubsection]
% \end{frame}
%}
% If you wish to uncover everything in a step-wise fashion, uncomment
% the following command:
%\beamerdefaultoverlayspecification{<+->}



\begin{document}
\begin{frame}
\titlepage
\end{frame}
\begin{frame}
\frametitle{Credits}
\begin{itemize}
\setlength\itemsep{0.5\baselineskip}
\item Darko Aleksic
\item Howard Cheng
\item Zachary Friggstad
\item Warren MacEvoy
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{Popular Vote}
\begin{itemize}
\setlength\itemsep{0.5\baselineskip}
\item Straightforward
\item Just sum up the votes, and find the maximum and see if it is unique
  and more than half of the total.
\item Minor detail: be careful with integer division.
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Card Game}
\begin{itemize}
\setlength\itemsep{0.5\baselineskip}
\item You could represent this as a 2-SAT instance (clause = card,
  variables = face), but the instances are too big.
\item Let the different face values be nodes in a graph.
\item Add an undirected edge connecting the two faces of each card
  (multiple edges and self loops are allowed).
\item Faces that are not in the same connected component can be treated
  independently.
\item In a component, there is no issue unless there is a cycle.  A
  single cycle is okay, but not more.  Self-loops count as cycles.
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Amazing Race}
\begin{itemize}
\setlength\itemsep{0.5\baselineskip}
\item Similar to dynamic programming solution for travelling salesman.
  Complexity: $O(n^2 \cdot 2^n)$
\item For each subset of locations $S$ and each $u \in S$, we want to compute
\[ f(S,u) = \text{shortest time to visit all locations in $S$ and ending at $u$.} \]
\item The recursion is
\[ f(S,u) = \min_{v \in S\backslash \{u\}} ( f(S \backslash \{u\}, v) + \text{dist}(v,u) + t_u. \]
care needs to be taken to exclude $v$ if we cannot finish the task at $u$
by going through $v$.
\item Maximize the points obtained over all subsets $S$ and $u \in S$ such
  that $f(S, u) + \text{dist}(u,\text{dest}) \leq T$.
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Scaling Recipes}
\begin{itemize}
\setlength\itemsep{0.5\baselineskip}
\item Straightforward: just follow the ``recipe''!
\item Can be done completely with integer arithmetic to avoid rounding errors,
  but not needed here.
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Space Junk}
\begin{itemize}
\setlength\itemsep{0.5\baselineskip}
\item Two spheres touch/collide if the distance between their center
  is less than the sum of their radii.
\item Represent the position of the center of each sphere parametrically as:
  \[ p(t) = (x,y,z) + t(v_x, v_y, v_z) \]
\item Write the equation:
  \[ \| p_1(t) - p_2(t) |^2 \leq (r_1+r_2)^2 \]
  Expand everything and collect like terms in $t$ gives a quadratic inequality
  \[ a t^2 + b t + c \leq 0. \]
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Space Junk (cont.)}
\begin{itemize}
\setlength\itemsep{0.5\baselineskip}
\item Since $a \geq 0$, the problem is equivalent to finding the roots of
  the quadratic equation $at^2 + bt + c = 0$.
\item Only the smaller root matters because the two spheres do not
  touch initially.
\item Some special cases:
  \begin{itemize}
  \item no roots ($b^2-4ac < 0$)
  \item collision before current time
  \item $a = 0$
  \end{itemize}
  No collision in all of these cases.
\item Collision/no collision detection can be done in integer-only
  computations to avoid round-off errors.  Unnecessary here.
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{A Classy Problem}
\begin{itemize}
\setlength\itemsep{0.5\baselineskip}
\item To compare two class names, work backwards and compare them until there
  is a difference.
\item If one class name is shorter than the other, assume the rest of
  the shorter name is ``middle''.
\item Slightly tricky to pick the class names apart.
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Rubik's Revenge in \ldots 2D!? 3D?}
\begin{itemize}
\setlength\itemsep{0.5\baselineskip}
\item Standard state space search:
  \begin{itemize}
  \item each state is a configuration of the puzzle
  \item there is an edge from one state to another if it can be reached
    in one move
  \end{itemize}
\item Standard breadth-first search solves the problem but it is too slow:
  \begin{itemize}
  \item there are $\frac{16!}{(4!)^4} \approx 63 \times 10^6$ states.
  \end{itemize}
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Rubik's Revenge in \ldots 2D!? 3D? (cont.)}
\begin{itemize}
\setlength\itemsep{0.5\baselineskip}
\item A bidirectional search can cut down the search space significantly.
  (Roughly square root of the original search space.)
\item Search backwards from the goal for up to 6 moves (half the
  maximum number of moves).  Record the distance of each state
  reachable from the goal in 6 moves or fewer.
\item Search forward from the initial state until it reaches one of
  states discovered in the previous step.
\item The total distance is the sum of the distance from the initial
  state and the distance to the goal.
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{The Magical 3}
\begin{itemize}
\setlength\itemsep{0.5\baselineskip}
\item We want to find the smallest base $b \geq 4$ such that 
\[ n \equiv 3 \bmod b \]
\item Or in other words, $n-3$ is divisible by $b$.
\item So just find the smallest divisor $\geq 4$ of $n-3$.
\item Trial division of all $b$ up to $\sqrt{n-3}$ is sufficient.
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Matrix Keypad}
\begin{itemize}
\setlength\itemsep{0.5\baselineskip}
\item Observation: if we have two buttons pressed that are not on the same
  row or the same column, then all four corners of the ``rectangle'' formed
  are indeterminate.
\item Once we have the rectangles, we make sure that all other
  ``corners'' are connected.  Otherwise it is impossible.
\item The only time when we know for sure a button is pressed is when all the
  buttons pressed are in the same row or same column.
\end{itemize}
\end{frame}


\begin{frame}
\frametitle{I've Been Everywhere, Man}
\begin{itemize}
\setlength\itemsep{0.5\baselineskip}
\item Straightforward, can be done in number of ways.
\item Easiest to use a ``set'' data type to collect the city names and ask
  for the final size of the set.
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Bundles of Joy}
\begin{itemize}
\setlength\itemsep{0.5\baselineskip}
\item Dynamic programming.
\item For each bundle, the cheapest way to buy that collection of cakes is
  either:
  \begin{itemize}
  \item buy the bundle itself
  \item buy a collection of smaller bundles that make up the bundle
  \end{itemize}
\item Care needs to be taken when two bundles have the same cakes.

\item To determine the collection of smaller bundles involved, it is
  sufficient to do it ``brute force'' and check every other bundle.
  Complexity $O(m^2 n)$.

\item There are faster ways to determine the collection of smaller
  bundles involved, but it's not needed for this problem.  It is
  possible to solve the problem in linear time (i.e. proportional to 
  the sum of items in each bundle).


\end{itemize}
\end{frame}





\end{document}
