\begin{frame}
    \frametitle{\problemtitle}
    \begin{description}
      \item<+->[Problem:] For $i\in\{1,\ldots,n\}$, the $i$th windmill can process $p_i$~kg wheat in $1$~hour; it takes $t_i$~hours to travel to (and from).
	How fast can you process $w$~kg wheat and get it back?
      \item<+->[Easier problem:] 
	Given time $r$, can the wheat be processed in time $r$ or less?
      \item<+->[Observation:] 
	If you can reach  $i$th windmill in  time $r$ (and get back), \emph{i.e.}, if $r\geq 2t_i$, you can process
	\( p_i(r - 2t_i) \)~kg
	wheat there. 
	In total, \[ \sum_{i=1}^n \max\bigl(0, p_i(r-2t_i)\bigr)\,.\]
      \item<+->[Solution:]
	We can \emph{binary-search for the answer}.
	Travel times are positive integers, so $l=2$ is a lower bound.
	For an upper bound, processing \emph{all} wheat on the first machine takes $h=2t_1+w/p_1\leq 2\cdot 10^9$.
	Can now binary search for the correct value of $r$ with $l\leq r\leq h$.
      \item<+->[Running time:] $\mathcal O(n\log h)$.
    \end{description}
    \solvestats
\end{frame}

\begin{frame}
    \frametitle{\problemtitle}
    \begin{description}
      \item<+->[Problem:] For $i\in\{1,\ldots,n\}$, the $i$th windmill can process $p_i$~kg wheat in $1$~hour; it takes $t_i$~hours to travel to (and from).
	How fast can you process $w$~kg wheat and get it back?
      \item<+->[Greedy solution:] 
	Sort the mills such that $t_1\leq \cdots \leq t_n$.
      \item<+->[Claim:] 
	There is an optimal solution using exactly mills~$1,\ldots, i$ for some $i$, with the mills grinding for nonzero time, and either grinding or transporting during the entire makespan.
%      \item<+->[Proof:]
%	  For optimal makespan $T$, clearly we can assume that the $j$th mill is either unvisited, or is never idle during the makespan, grinding $0<(T-2t_j)\cdot p_j$~kg flour.
%	(If $T=2t_j$ we don't visit it.)
%	Assume that that an optimal solution avoids mill~$j$ but uses mill~$j+1$ with $t_j<t_{j+1}$.
%	Then we can re-rout the shipment for $j+1$ to $j$ without increasing the makespan.
      \item<+->[Implementation:] 
	Getting to/from mill~$i$ takes time $t_i$, so during that time the other mills can grind \[
	  w'=
	  \sum_{j=1}^{i-1} p_j\cdot (2t_i- 2 t_j)\text{ kg wheat.}\]
	To grind the remaining wheat (if any), all $i$ machines can work, so the makespan is
	\[
	  2t_i + (w-w')/(p_1+\cdots+ p_i)\,.
	\]
      \item<+->[Running time:]
	Naïve implementation requires $\mathcal O(n^2)$.
	The sums can be computed cumulatively to achieve
	time $\mathcal O(n\log n)$ for $n\geq 2$.
    \end{description}
    \solvestats
\end{frame}
