\usetikzlibrary{shadows}

\newcommand*\keystroke[1]{% Based on https://tex.stackexchange.com/a/5227
    \raisebox{0.25ex}{%
        \tikz[baseline=(key.base)]
        \node[
          draw,
          fill=black!10,
          drop shadow={shadow xshift=0.25ex,shadow yshift=-0.25ex,fill=black,opacity=0.75},
          rectangle,
          rounded corners=2pt,
          inner sep=1pt,
          line width=0.5pt,
          font=\scriptsize
        ](key) {\,$#1$\strut\,};%
    }%
}

\begin{frame}
    \frametitle{\problemtitle}
    \begin{description}
        \item<+->[Problem:] Given a number $n$ of $d\leq1000$ digits. Between any two digits, insert a \keystroke{+} or a \keystroke{-} with $45\%$ chance each. What is the expected value of the resulting expression?
        \item<+->[Observation:] Since \keystroke{+} and \keystroke{-} are equally likely, anything after the first \keystroke{+} or \keystroke{-} has expected~value~$0$.
        \item<+->[Solution:] The first term has $k$ digits ($1\leq k\leq d-1$) with probability $0.1^{k-1}\cdot0.9$, and $d$ digits with probability $0.1^{d-1}$. Multiplying by $0.1$ just moves the decimal, so if, for example, $n=1234$, the answer is $0.9\cdot(1+1.2+1.23)+1.234=4.321$.
        \item<+->[Running time:] $\mathcal{O}(d^2)$ naively, but can be optimized to $\mathcal{O}(d)$, though this was not necessary.
        \item<+->[Alternative:] The $k$th digit is multiplied by $0.1^{k-1}\cdot(1+0.9(d-k+1))$. It turns out, summing over only the first $20$ digits suffice to have enough precision.
    \end{description}
    \solvestats
\end{frame}
