Unexpected Fourier

05 Feb, 2025

I don't encounter Fourier Transforms that often in my day-to-day life. I do not do signal or image processing, so that's to be expected. However, recently something has happened—I did not expect a simple programming problem to hide a beautiful Fourier undearneath its statement. Let's have a look at it!

Golf Bot

Do you like golf? I hate it. I hate golf so much that I decided to build the ultimate golf robot, a robot that will never miss a shot. I simply place it over the ball, choose the right direction and distance and, flawlessly, it will strike the ball across the air and into the hole. Golf will never be played again.

Unfortunately, it doesn't work as planned. So, here I am, standing in the green and preparing my first strike when I realize that the distance-selector knob built-in doesn't have all the distance options! Not everything is lost, as I have 2 shots.

Task

Given my current robot, how many holes will I be able to complete in 2 strokes or less?

Input

The first line has one integer: $N$ , the number of different distances the Golf Bot can shoot. Each of the following $N$ lines has one integer, $k_{i}$ , the distance marked in position $i$ of the knob.

Next line has one integer: $M$ , the number of holes in this course. Each of the following $M$ lines has one integer, $d_{j}$ , the distance from Golf Bot to hole $j$ .

Constraints

1 ≤ $N$ , $M$ ≤ 200000

1 ≤ $k_{i}$ , $d_{j}$ ≤ 200000

Output

You should output a single integer, the number of holes Golf Bot will be able to complete. Golf Bot cannot shoot over a hole on purpose and then shoot backwards.

Sample Output Explanation

Golf Bot can shoot 3 different distances (1, 3 and 5) and there are 6 holes in this course at distances 2, 4, 5, 7, 8 and 9. Golf Bot will be able to put the ball in 4 of these:

The 1st hole, at distance 2, can be reached by striking two times a distance of 1.

The 2nd hole, at distance 4, can be reached by striking with strength 3 and then strength 1 (or vice-versa).

The 3rd hole can be reached with just one stroke of strength 5.

The 5th hole can be reached with two strikes of strengths 3 and 5.

Holes 4 and 6 can never be reached.

The straight-forward solution

Like me, you might initially think of using a bitset to represent the distances the golf bot can shoot. Specifically, you could set $distance [i] = 1$ if the bot can shoot to distance $i$ . Then, for each hole on the course, you could iterate through the bitset to check if there exists a distance $i$ such that both $distance [i]$ and $distance [hole - i]$ are active. If the hole distance is even, you could first check if $distance [hole / 2]$ is active, as the bot could use the same distance twice. Also, if there exists any $i$ such that $distance [i] = hole$ , then it is also a solution.

This approach would net you a $O (N \cdot M)$ time complexity. When I tested it, the online judge told me it is not fast enough— $N$ and $M$ are way too big for this to be viable. While I did some optimizations, I could not reduce the $N \cdot M$ time complexity asymptotically. The hard part of this problem is figuring out the hole distances that can be reached by the sum of two strikes. How to optimize that?

If you are smarter than me, you probably noticed something important.

Hello, Fourier

This problem reduces to finding all the active $distance [j]$ and $distance [hole - j]$ pairs—basically, the holes reached by two strikes. Let's use $can_hit [i]$ instead of $hole$ , which is a bitset where $can_hit [i] = 1$ means the golf bot can hit a hole of distance $i$ . We could write the answer to a single hole as a sum:

can_hit [i] = \sum_{j = 0}^{N - 1} distance [j] * distance [i - j]

Does this look similar?

(f * g) [n] = \sum_{m = - \infty}^{\infty} f [m] g [n - m]

The $can_hit$ array is a discrete convolution of the $d i s t a n c e$ array with itself. Convolutions, while in the time domain, are computed in polynomial time, $O (n^{2})$ . However, when you transform the functions (in our case $distance$ ) into the frequency domain, convolutions can be computer in linear time, $O (n)$ ! This is half of the story—what is the cost of transforming a function into the frequency domain? The Fast Fourier Transform can do that with $O (n \log n)$ time complexity. Summing up, the complexity of doing this convolution in the frequency domain rather than the time domain drops from $O (n^{2})$ to $O (n \log n + n)$ , which is equivalent to $O (n \log n)$ . In our case, the actual time complexity is $O (MAX \log MAX)$ , where $MAX$ is the maximum possible distance, 200000.

It would be better to see the example case in action—the golf holes are at distances 2, 4, 5, 7, 8 and 9 while the bot has striking distances of 1, 3 and 5:

$distance$ array: [0, 1, 0, 1, 0, 1] (the 1st, 3rd and 5th bits are active);
Convolution of distance with distance results in: [0, 0, 1, 0, 2, 0, 3, 0, 2, 0, 1];
- The numbers in the convolutions mean the number of ways the bot can hit that using exactly two strikes. (2 = 1 + 1, 4 = 1 + 3 = 3 + 1)
The bot can hit holes at distances 2, 4, 6, 8, 10 using two strikes. In one strike, the bot can also hit the holes at distances 1, 3, 5;
Finally, we conclude that the bot can hit 4 of the 6 holes.

And that's it! The concrete steps are to apply FFT on the initial $distance$ array, then multiply that with the reverse of $distance$ (convolution works like that), then apply the inverse FFT on the result of the product and you get the $can_hit$ array.

I think I like FFT even more now.

#blog #fourier #problem #programming