CMIMC 2017 Power Problem 27

Past Contests CMIMC CMIMC - 2017 Power
1

Conclude that, after the algorithm terminates,

\mathbf{E}[W(S)] \leq 2 \cdot W(C)