The solution calculates three numbers for every square ~S~: the difference if we colour ~S~ all white, the difference if we colour ~S~ all black, and the difference if we recursively use the procedure from the problem statement (dividing into four sub-squares) on ~S~.

To calculate this last number, we use dynamic programming. First separate ~S~ into four sub-squares and calculate all three numbers for each of the sub-squares. From the calculated numbers for sub-squares, it is trivial to calculate the first and second numbers for ~K~. The third is calculated by considering all ways of choosing which sub-square is coloured white, which one is coloured black and which two we apply the recursive algorithm on. There are a couple of ways to do this and we will of course choose the one that minimizes the overall difference.