Hi guys,

I just looked at the tutorial for this problem: https://codeforces.net/contest/1982/problem/D. I got all the steps correct (constructing a 2D prefix sum, finding the differences in the submatrices), but I was unable to see how to quickly determine a solution after this. In the tutorial, it states that it is sufficient to say that a solution exists if

where d[i] is the difference between capped and non-capped mountains in a k*k submatrix, and D is the difference of the total heights of capped and non-capped mountains; however, I cannot see why this is true. Could someone please help me by explaining a proof of this statement? Thank you very much everyone!