SRM 734, D1, 300-Pointer (TheRoundCityDiv1)

James S. Plank

Tue Aug 21 17:57:10 EDT 2018

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
Problem Given in Topcoder: May, 2018
Competitors who opened the problem: 103
Competitors who submitted a solution: 59
Number of correct solutions: 46
Accuracy (percentage correct vs those who opened): 44.7%
Average Correct Time: 35 minutes, 41 seconds.

You have to be on your game for this one. Unlike the Div2 version of this problem, where you can simply iterate over all of the potential home points, this one requires some constructive thought. In particular, you can't get too much worse than a linear algorithm on r. Maybe (r log(r)).

Let's think about it incrementally. First, there will be two homes visible on the x-axis (-1,0) and (1,0) and two homes visible on the y-axis (0,-1) and (0,1). Then, if you count the homes in the quadrant where x > 0 and y > 0, you can multiply that answer by four, add it to the four homes along the axes, and that's your answer.

So, your goal is to count the homes where x > 0 and y > 0.

Let's continue thinking incrementally -- lets loop from y = 1 to y = r-1. For each value of y, can we can determine the number of homes at points (x,y) that are visible? It's not too hard to compute the maximum value of x such that (x,y) is inside the circle. Let's call that point x_max. Can we calculate the number of visible homes using just the values y and x_max? Let's try some examples:

When y is 1, then all of the homes are visible. So the answer is x_max.
When y is 2, then any home with an even value of x is invisible. Using integer arithmetic, there are x_max/2 invisible homes, so the answer is x_max - x_max/2.
When y is 3, then any home with a value of x which is divisible by three will be invisible. So the number of invisible homes is x_max/3 (using integer arithmetic again), and the number of visible homes is x_max - x_max/3.
When y is 4, then any home with an even value of x will be invisible. We're back to x_max - x_max/2.

Let's think about it more precisely. If a home at (x,y) is invisible, then there must be a point at (x/f, y/f) for some integer f. So, for a home to be invisible, x and y cannot be relatively prime. OK -- that lets us state the problem in a different way -- given y and x_max, how many numbers from 1 to x_max are relatively prime with y? As you can see from the examples above, when y is a prime number, you can simply divide x_max by y and subtract that from x_max. If y is a power of a prime number, then you divide x_max by the prime number, and subtract it from x_max. What if y is the product of more than one prime number?

Again, look at an example. Suppose y is 6. Then, if we subtract x_max by both x_max/2 and x_max/3, then we've subtracted too many numbers -- we have subtracted the multiples of 6 twice. To fix this, we need to add back in the x_max/6 multiples of six.

The general principle going on here is called the "Inclusion-exclusion" principle. It has its own Wikipedia page. Suppose y has m unique prime factors. Then, the count of numbers between one and x_max that are relatively prime with y are:

x_max -- all of the numbers.
Minus x_max/p_i -- for every unique prime factor p_i of y.
Plus x_max/(p_ip_j) -- for every pair of unique prime factors p_i, p_j of y.
Minus x_max/(p_ip_jp_k) -- for every trio of unique prime factors p_i, p_j, p_k of y.
And so on.

So now we have a strategy:

Loop y from 1 to r-1.
Determine the maximum x index x_max of a house whose y index is y.
Determine the unique prime factors of y.
For every combination of these prime factors (including the null combination - use a power set enumeration), divide x_max by their product. If the combination had an even number of prime factors, add it to the sum, and if it had an odd number, the subtract it from the sum.
The sum is the number of visible houses whose y value is y.

Let's do an example. When r is 47, and y is 12. We know that x² + 12² ≤ 47², so x_max = 45. Now, we want to calculate how many x's there are from 1 to 45 which are relatively prime with 12. So, we find the unique prime factors of 12: 2 and 3. And then we enumerate every combination pf of the unique prime factors:

pf = { }. Their product is 1. Their cardinality is even. So they add 45 to the total.
pf = { 2 }. The product is 2. The cardinality is odd. So they subtract 45/2 = 22 from the total.
pf = { 3 }. The product is 3. The cardinality is odd. So they subtract 45/3 = 15 from the total.
pf = { 2, 3 }. The product is 6. The cardinality is even. So they add 45/6 = 7 to the total.

Thus, the total number of visible houses where y is 12 is 15. In case you are wondering, those are when x is one of { 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43 }.

Running Time

Well, I started by generating all of the prime numbers up to sqrt(r) and storing them in a vector primes. That's less than O(r) (There are 168 primes ≤ 1,000). The main loop is O(r), and with each element, you need to determine the unique prime factors. That's O(primes.size()). Then the loop to enumerate all combinations of unique prime factors is 2^{(# of unique prime factors)}. 2*3*5*7*11*13*17 = 510510, so the number of unique prime factors will be pretty small. I had a feeling that this one would run up against Topcoder's limits when r was 1,000,000. On my Mac, it was over 2 seconds unoptimized, but it passed the system test, so it must have gotten under when optimized!