Consider the random graph $G(2n,1/2)$. After picking each edge uniformly and independently with probability $1/2$ suppose that we have exactly $m$ edges in total (note: $m$ is not fixed!). Prove that there is a constant $a>0$ with the following property: with probability tending to $1$ as $n\to \infty$ we can partition the vertices of $G$ into classes $V_1$ and $V_2$ of sizes $|V_1| = |V_2| = n$ in a way so that the number of edges from $V_1$ to $V_2$ is at least $m/2 + an^{3/2}$.
There is a hint (though not enough for me to see the whole picture): Consider constructing $V_1$ and $V_2$ step-by-step, starting with $V_1=V_2=\emptyset$. In each step consider two new vertices $x$ and $y$, and either add $x$ to $V_1$ and $y$ to $V_2$ or vice-versa. Show that we can always ensure that at least half of the edges between $\{x,y\}$ and the earlier vertices join $V_1$ to $V_2$, and sometimes significantly more.
Any help appreciated!