Hi guys,
I just looked at the tutorial for this problem: https://codeforces.me/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!
Let $$$x = gcd(d_1,d_2,\dots,d_q)$$$. Since all $$$d_i$$$ are divisible by $$$x$$$, the sum $$$c_1\cdot d_1+c_2\cdot d_2+\dots+c_q\cdot d_q$$$ is also divisible by $$$x$$$, so if $$$D\bmod x$$$ must be 0.
To prove it's always possible to form $$$D$$$ as a sum of $$$d_i$$$, we use Bézout's identity, which says that for every pair $$$(a,b)$$$ , there are numbers $$$x, y$$$ so that $$$ax+by=gcd(a,b)$$$ (proof). If we have $$$a$$$, $$$b$$$ and $$$c$$$, we can form $$$gcd(a,b)$$$ and therefore we can also form $$$gcd(gcd(a,b),c)=gcd(a,b,c)$$$, and so on, so we can form the gcd of all the integers.
This means we can do the operation a number of times to change $$$D$$$ by $$$x$$$. Since $$$x|D$$$, it's always possible to change it to 0 after repeating this.