A circular week

The second week of August was relatively calm, with just the early morning TopCoder SRM 696 on the agenda (problems, results, top 5 on the left). Swistakk was the only contestant to solve the hard problem correctly, but anta has earned his second SRM victory thanks to being the fastest on the medium problem. Great job!

In the previous week's summary, I have shared a very nice Code Jam problem: you are given two numbers n and r. There's a nxn grid of pillars, with a pillar of radius r centered in each point of the grid except the bottom-left corner. How many pillars are visible from the bottom-left corner?

Which seems to be a geometry problem at the first glance, turns out to be solely about number theory when it comes to the implementation. The first observation that leads us there is the fact that if we can see any point of a column, then we can see its center. To prove that, suppose the column at (x, y) obstructs some part of the view of the column at (a, b) including its center. The column at (a-x, b-y) is in a symmetric location, and thus also obstructs the view of the center of (a, b), but from the other side. As a result, the view of the entire column at (a, b) is obstructed. So instead of having to carefully track which part of a column is visible, we just need to check if its center is visible.

Now, when does the column at (x, y) obstruct the center of the column at (a, b)? It happens if x<=a, y<=b, and the distance d from the point (x, y) to the line connecting the point (0, 0) with the point (a, b) is less than or equal to r - the radius of each column. Now, consider the triangle with vertices (0, 0), (x, y) and (a, b). Its area s can be found by multiplying 0.5 by its base and height, in other words, it is equal to 0.5*sqrt(a*a+b*b)*d, so d=2*s/sqrt(a*a+b*b). On the other hand, its vertices have integer coordinates, and Pick's formula tells us that s is a half-integer: either 0, or at least 0.5. Because of this, d is either 0 or at least 1/sqrt(a*a+b*b).

When can d be equal to 0? It happens if an only if a and b are not relatively prime: in that case there's a column blocking the view directly. In all other cases, d is at least 1/sqrt(a*a+b*b). Moreover, this lower bound is tight: we can always find a point (x, y) that makes d equal to 1/sqrt(a*a+b*b). For example, let's consider the point that's closest to the segment (0, 0) - (a, b) inside its bounding box. It's not hard to see that the resulting triangle does not have any other integer points inside or on its boundary (otherwise those would be closer), and thus its area is 0.5 by Pick's formula, which yields the required value of d.

Now we can finally write down a very simple description of the columns we see: we need a and b to be relative prime, and have 1/sqrt(a*a+b*b)>r, in other words a*a+b*b<1/(r*r). The latter formula simply describes a circle with radius 1/r, so the problem boils down to counting integer points inside an intersection of a square and a quarter-circle, which is a relatively standard number theory problem.

The simple circular shape of the set of the visible columns is one of the beautiful sides of this problem, as it enables a different way of solving it: implementing a slow solution, such as the one for the small input, and then visualizing the result to get an insight. For example, plotting a grid corresponding to all visible columns with r=0.01 results in the picture above, which clearly suggests the idea of a circle with radius 1/r.

Thanks for reading, and check back soon for the next week's summary!