\author{Problem Author: Mark Wen}
\newcommand{\seesawheader}{Problem H: Seesaw}

\begin{frame}{\seesawheader{}}
  \begin{block}{Problem}
    \begin{itemize}
      \item There are $n$ people are located at various positions on the number line.
      Each has some weight, and people can move along the line so long as
      their relative order is preserved. What is the minimum total distance
      people have to move to make the sum of their torques (position * weight)
      equal 0?
    \end{itemize}        
  \end{block}
\end{frame}
\begin{frame}{\seesawheader{}}
  \begin{block}{Solution}
    \begin{itemize}
      \item Greedily move the person with greatest change in torque
      per unit of distance moved, call this the "torque value". Initially
      this is just the weight of each person.
      \item When a person runs into another, they effectively merge into 
      a single group that moves as one from now on. Their torque value becomes
      their combined weight divided by the number of people in the group.
      \item We need to be able to efficiently query what position
      each group of people would run into next, as well as which group currently
      has the greatest torque value.
      \item The first can be maintained with an ordered set of positions and the second
      with a priority queue on the torque values of each group. Take care when updating
      information as groups merge.
      \item With these structures we can simulate the greedy process until
      the sum of torques is balanced.
    \end{itemize}        
  \end{block}
\end{frame}
