yh11's blog

Can someone explain Atcoder 269 Problem F solution?
By yh11, history, 2 years ago, In English

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. :)

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Nice. I was thinking of this solution but was too scared to implement the solution :(.

    → Reply
»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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]

  1. Calculating f(i,j) was all math
  2. value at (i,j) is either 0 or (i−1)×M + j
  3. total contributions at i,j can be divided into those coming from (i-1)*M term and those from + j term
  4. for contributions from j we see that even indices rows given same contribution
  5. for contributions from i just do a little math
→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes. This makes sense. Thanks.

    → Reply