snorkel's blog

ICPC WF 2011 Problem
By snorkel, history, 4 years ago, In English

Hello, I'm interested in the solution of "E — Coffee Central" from the following CF GYM contest. It's actually ICPC World Finals 2011 problem.

I've searched on internet but wasn't able to find the full solution. Some briefly mentioned you should rotate the points by 45 degree, but I don't understand why should I and how then proceed.

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

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

Rotating by 45 degrees transforms the diamond-shaped Manhattan disks into axis-aligned square Chebyshev disks. Then, for a given value of $$$m$$$, the number of coffee shops that can be reached as a function of (rotated) position is the pointwise sum of $$$n$$$ axis-aligned rectangular indicator functions, which can be easily computed in $$$O(4n + (dx + dy)^2)$$$ with 2D prefix sums.

(For completeness I should mention that many of the points in the rotated grid will not correspond to integer points in the original grid. To deal with this you can either check this condition and calculate the max value while calculating the 2D prefix sums, or just loop over every valid coordinate separately later.)

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    What do you mean by disk? I can't find anything about it.

    EDIT: I got what you mean by disks, but how the points can't be integers? Isn't rotating by 45 just doing (x+y,x-y)?

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

      Every (integer, integer) point in our original $$$dx \times dy$$$ rectangle is mapped to an (integer, integer) point. But not every (integer, integer) point is in the image of this mapping. The inverse map is something like $$$(x', y') \mapsto \left(\frac{x' + y'}{2}, \frac{x' - y'}{2}\right) $$$, and it's clear that only points $$$(x', y')$$$ with $$$x' \cong y' \, (\mathrm{mod}\, 2)$$$ can be equal to $$$(x+y, x-y)$$$ for some integer point $$$(x, y)$$$.

      (I suppose the output format makes it unlikely for this to result in a wrong answer on this problem. But it is a potential 'gotcha' worth keeping in mind when using this technique on other problems.)

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

If you take all the points which are $$$<=d$$$ to a point x, y in the original grid, you will see that all reachable coordinates constitutes to a diamond. You "rotate" (more like translate the points into a new matrix that is "wider") this original matrix into 45 degrees (some coordinates in this transformed matrix will be zero, but that's okay).

Then just apply 2D-range sum with inclusion-exclusion on this transformed grid. $$$q<=20$$$ so an $$$O(n^2)$$$ approach will work.

Here is also a very helpful post that should get you some intuition. https://math.stackexchange.com/questions/732679/how-to-rotate-a-matrix-by-45-degrees

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

    Oh, Thanks. The image helped me understand the idea of rotating.

    → Reply