I just read Problem F editorial.
I realise that computing the sum of the numbers in the box (when nothing is set to 0) is not very difficult. (Its just some interpolation of the sum of first n natural numbers). It becomes complicated when alternate values are set to 0.
In this editorial the answer has directly been provided and the explanation for the jumps in reasoning are skipped.
I was hoping someone could provide an explanation to fill in the gaps of this editorial.
Thanks. :)
I solved it in a different way than described in the editorial.
First of all, notice that for any rectangle with even lengths, odd sum and even sum are completely symmetric. Thus, for some $$$2n \times 2m$$$ matrix we can take the answer as just $$$sum / 2$$$.
Then, if either width or height of a rectangle is odd, you could separately add one row and one column to the answer. If both of them are odd, don't forget to subtract the contribution of one cell in the border because we count it twice.
Nice. I was thinking of this solution but was too scared to implement the solution :(.
I developed a mathematical formula for the sum of the given matrix(with replaced zeros) encompassing the rectangle (1,1) to (i,j) say f(i,j)
then answer for query (a,b,c,d) is simply f(c,d) — f(b,c-1) — f(a-1,d) + f(a-1,b-1);[see geometrically]
Yes. This makes sense. Thanks.