\documentclass{beamer}
%\setbeamertemplate{navigation symbols}{}

%\newtheorem{definition}[theorem]{Definition}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Q}{\mathbb{Q}}
\renewcommand{\Pr}[1]{{\mathop{\text{Pr}}\left[#1\right]}}
\newcommand{\Ex}[1]{{\mathop{\mathbb{E}}\left[#1\right]}}

\usepackage{tikz,wrapfig,graphicx}
\usepackage{xcolor}
\usepackage{kbordermatrix}
\usetikzlibrary{shapes,snakes}
\usetikzlibrary{arrows.meta,automata,positioning}

\usetheme{Madrid}

\definecolor{eliminate}{gray}{0.85}
\definecolor{eliminate2}{gray}{0.6}
\definecolor{green2}{rgb}{0, .9, 0}

%\usepackage{beamerthemesplit} % new 
\begin{document}
\title{Train Line Solution Slides} 
\author{Problem Boss: Bryce Sandlund\\
Antonio Molina (y0105w49)\\
Nick Wu (xiawuc1)\\
Derek Kisman (SnapDragon)\\
David Van Brackle (vanb)\\
Matt Fontaine (Tehqin)\\
Nalin Bhardwaj\\
Finn Lidbetter\\
Rongqi Qiu\\
Tomas Rokicki\\
Arnav Sastry (arknave)
}
\date{}

\frame{\titlepage} 

%\frame{\frametitle{Table of contents}\tableofcontents} 

%\AtBeginSection[]
%{
%\begin{frame}{Table of Contents}
%\tableofcontents[currentsection]
%\end{frame}
%}

\author{Problem Author: Bryce Sandlund}

\frame{
\frametitle{K - Train Line}
\begin{block}{Problem}
Given $n$ points on a line representing metropolitan areas, determine the maximum utility of placing at most $k$ train stations, where the utility of the stations to a given area is $p \cdot 2^{-d}$, where $p$ is the population of the area and $d$ is the distance from the closest train station to the area.
\end{block}
}

\frame{
Consider graphing utility of placing a single station given populations.
\begin{figure}
\begin{center}
	\includegraphics[scale=.4]{utility.png}
\end{center}
\caption{Graph of $f(x) = 7\cdot2^{-|x-7|} + 4\cdot2^{-|x-9|}$, the utility of placing a single station at $x$ given a population of size $7$ at position $7$ and a population of size $4$ at position $9$.}
\end{figure}
}

\frame{
Two observations can be proved formally:
\begin{enumerate}
	\item It is only ever worth it to place stations directly on populations.
	\begin{itemize}
		\item Proof: The utility function of a single area between any two populations is convex, thus the sum of the utility functions for all areas between two populations is also convex. Thus it is maximized at the boundary.
		\item Alternatively, take derivatives, or apply Jensen's inequality.
%		\item Quick trick:
%		\begin{itemize}
%			\item Utility function is sublinear $\rightarrow$ w.l.o.g. maximum is achieved between populations.
%			\item Utility function is superlinear $\rightarrow$ w.l.o.g. maximum is achieved at populations.
%		\end{itemize}
		%utility function is sublinear => maximum may lie between populations
		
		
	%	if the utility function is sublinear, the maximum may lie between populations. If it is superlinear, it is only maximized at populations. In this case the utility function is exponential, so the maximum is achieved at populations.
	\end{itemize}
	\pause
	\item Utility becomes negligible at a certain distance.
	\begin{itemize}
		\item With each increasing unit of distance, utility halves, so to achieve a utility $f$ such that $|f-f^*| < \epsilon$, where $0 < \epsilon < 1$ and $f^*$ is the correct answer, we need only consider stations distance $O(\log(1/\epsilon))$ from a given population.
		\item To achieve relative error $\leq 10^{-6}$, it can be proven we need only consider stations at distance at most $28$ from a given population.
	\end{itemize}
\end{enumerate}
}

\frame{
	\begin{block}{Solution Idea 1}
		Define:
		\begin{itemize}
		\item \texttt{DP}$(i,j)$ := maximum utility possible in the first $i$ populations placing at most $j$ stations.
		\item \texttt{Place}$(i,j)$ := maximum utility possible in the first $i$ populations placing a station at $i$ and placing at most $j$ stations.
		\end{itemize}
		Then:
		\begin{itemize}
			\item $\texttt{DP}(i,j) = \max\left(\begin{array}{l}
													\texttt{DP}(i-1,j)\\
													\max_{\ell=1}^{30} \texttt{Place}(i-\ell,j) + utility(i-\ell,i)
			\end{array}\right)$.
			\item $\texttt{Place}(i,j) = \max_{\ell=1}^{30} \texttt{DP}(i-\ell,j-1) + utility(i-\ell, i)$.
		\end{itemize}
%		\item Then $\texttt{DP}(i,j) = \max\left(\begin{array}{l}
%										\texttt{DP}(i-1,j)\\
%										\max_{\ell=1}^{30} \texttt{Place}(i-\ell,j-1) + utility(i-\ell,i)
%		\end{array}\right)$, and
%		%\max(\texttt{DP}(i-1,j), \max_{\ell=1}^{30} \texttt{Place}(i-\ell,j-1) + utility(i-\ell, i))$\\ and
%		$\texttt{Place}(i,j) = \max_{\ell=1}^{30} \texttt{DP}(i-\ell,j-1) + utility(i-\ell, i)$.\\ \textcolor{red}{Pitfall}: Forgetting \texttt{DP}$(i-1,j)$ as part of \texttt{DP}$(i,j)$ calculation.
%		\end{itemize}
\pause
\textcolor{red}{Pitfall}: Forgetting \texttt{DP}$(i-1,j)$ as part of \texttt{DP}$(i,j)$ calculation.
	\end{block}
\pause Complexity: $O(kn\log(1/\epsilon))$. \pause\textcolor{red}{TLE!} We must use the \href{http://www.serbanology.com/}{\textcolor{blue}{aliens trick}} to reduce the number of DP states.
}

\frame{
\begin{itemize}
	\item Consider $f(k)$ := maximum utility placing at most $k$ stations.
	\item Then $f(k)$ is concave: $f(k+1) - f(k) \leq f(k) - f(k-1)$.
	\item Intuitively, with each additional station added, $f(k)$ increases progressively less.
	\pause
	\begin{block}{Solution Idea 2}
	Define:
		\begin{itemize}
			\item \texttt{DP}$(i,\lambda)$ := maximum utility possible in the first $i$ populations where each station costs $\lambda$.
			\item \texttt{Place}$(i,\lambda)$ := maximum utility possible in the first $i$ populations placing a station at $i$ where each station costs $\lambda$.
		\end{itemize}
	Then:
	\begin{itemize}
		\item $\texttt{DP}(i,\lambda) = \max\left(\begin{array}{l}
		\texttt{DP}(i-1,\lambda)\\
		\max_{\ell=1}^{30} \texttt{Place}(i-\ell,\lambda) + utility(i-\ell, i))
		\end{array}\right)$.
		\item $\texttt{Place}(i,\lambda) = \max_{\ell=1}^{30} \texttt{DP}(i-\ell,\lambda) + utility(i-\ell, i)-\lambda$.
	\end{itemize}
%	\begin{itemize}
%		\item Then $\texttt{DP}(i,\lambda) = \max\left(\begin{array}{l}
%												\texttt{DP}(i-1,\lambda)\\
%												\max_{\ell=1}^{30} \texttt{Place}(i-\ell,\lambda) + utility(i-\ell, i))
%			\end{array}\right)$, and
%			$\texttt{Place}(i,\lambda) = \max_{\ell=1}^{30} \texttt{DP}(i-\ell,\lambda) + utility(i-\ell, i)+\lambda$.
%			\item Binary search to find the correct $\lambda^*$ so that about $k$ stations are placed.
%			\item Answer is $\texttt{DP}(n,\lambda^*) + \lambda^* \cdot k$. \textcolor{red}{Pitfall}: Using answer = $\texttt{DP}(n,\lambda^*) + \lambda^* \cdot count$, where $count$ is the number of stations placed.
%		\end{itemize}
	\end{block}
%\pause
%Complexity: $O(n \log(1/\epsilon) \log range)$, where $\log range$ is the total number of $\lambda$'s tried.
\end{itemize}
}

\frame{
\begin{block}{Final Algorithm}
\begin{itemize}
	\item Binary search to find the correct $\lambda^*$ so that about $k$ stations are placed.
	\item Answer is $\texttt{DP}(n,\lambda^*) + \lambda^* \cdot k$.
\end{itemize}
\pause
\textcolor{red}{Pitfall}: Using answer $= \texttt{DP}(n,\lambda^*) + \lambda^* \cdot count$, where $count$ is the number of stations placed.
\end{block}
\pause
Complexity: $O(n \log(1/\epsilon) \log range)$, where $\log range$ is the total number of $\lambda$'s tried.\linebreak\linebreak
\pause
Statistics: 70 submissions, 3 accepted.
}

\frame{
\centering
Questions? Comments? Concerns? Email Bryce Sandlund: bcsandlund@gmail.com.
}
\end{document}

