Educational Codeforces Round 67 F. Expected Square Beauty

https://codeforces.com/contest/1187/problem/F



\documentclass[margin=2mm]{standalone}
\usepackage{amsmath,amssymb,bussproofs}

\begin{document}

%\begin{prooftree}
  \AxiomC{\(N^2\)}
  \UnaryInfC{\(E[N^2]\)}
  \AxiomC{\(\displaystyle \sum_{i} \Pr[x_i=x_{i+1}]\)}
  \UnaryInfC{\(\displaystyle \sum_{i}E[X_i]\)}
  \RightLabel{Linearity of Expecation}
  \UnaryInfC{\(\displaystyle E\left[\sum_{i}X_i\right]\)}
  \RightLabel{\(({}* -2N)\) Introduction}
  \UnaryInfC{\(\displaystyle -2NE\left[\sum_{i}X_i\right]\)}
  

  \AxiomC{\(\displaystyle \sum_{i} \Pr[x_i=x_{i+1}]\)}
  \UnaryInfC{\(\displaystyle E\left[\sum_{i}X_i^2\right] \)}

  \AxiomC{\(\displaystyle \sum_{i} \Pr[x_i=x_{i+1}=x_{i+2}] \)}
  \UnaryInfC{\(\displaystyle E\left[\sum_{i} X_i X_{i+1} \right]\)}
  
  \AxiomC{\([i+2 \le j]^{(1)}\)}
  \AxiomC{\(\displaystyle \Pr[x_i=x_{i+1}] \Pr[x_j=x_{j+1}] \)}
  \BinaryInfC{\(\displaystyle \Pr[x_i=x_{i+1} \land x_j=x_{j+1}] \)}
  \UnaryInfC{\(\displaystyle E[X_iX_j]\)}
  \RightLabel{\(\Sigma\) Introduction (1)}
  \UnaryInfC{\(\displaystyle \sum_{i+2 \le j} E[X_i X_j] \)}
  \RightLabel{Linearity of Expection}
  \UnaryInfC{\(\displaystyle E\left[\sum_{i+2 \le j} X_i X_j\right]\)}
  \BinaryInfC{\(\displaystyle E\left[\sum_{i<j}X_i X_j\right]\)}
  \RightLabel{\(({}*2)\) Introduction }
  \UnaryInfC{\(\displaystyle 2E\left[\sum_{i<j} X_i X_j\right] \)}
  \BinaryInfC{\(\displaystyle E\left[\sum_{i}X_i^2 + 2 p\sum_{i<j} X_i X_j\right] \)}
  \UnaryInfC{\(\displaystyle E\left[\left(\sum_{i}X_i\right)^2\right]\)}
  \RightLabel{Linearity of Expectation}
  \TrinaryInfC{\(\displaystyle E\left[\left(N-\sum_{i}X_i\right)^2\right] \)}
  \RightLabel{Let \(X_i\) be the indicator variable of \(x_i=x_{i+1}\). }
  \UnaryInfC{\(\displaystyle E[(N-X)^2] \)}
  \RightLabel{Let \(X\) be the number of \(i\) such that \(x_i=x_{i+1}\).}
  \UnaryInfC{answer}
  \DisplayProof
%\end{prooftree}
\end{document}