Hi all,

I was one of the judges of SWERC 2014. The problem set was just added to the archive.

The sample java solution to 12879 - Golf Bot gets accepted in 1.5s, so having a limit of 15s is too high.

I suspect that some optimized brute force approaches can get accepted this way. So, I suggest this limit to be cut to at most 4 seconds.

## 12879 - Golf Bot

**Moderator:** Board moderators

### Time limit on 12879 - Golf Bot is too high

Miguel Oliveira

### 12879 - Golf Bot

Problem statement

http://uva.onlinejudge.org/index.php?op ... oblem=4744

I think I found a "correct" approach for this problem, yet it's too inefficient (my code: https://gist.github.com/bengro/a092ed976a4b1f50494b).

I generate the sum of each pair of shot lengths (which is close to n^2). The input size suggests, that there is a linear/nlogn way of doing that?

Once I have all the possible lengths, I simply look them up for the rounds.

Any pointers of where I'm going wrong are appreciated! Thanks!

http://uva.onlinejudge.org/index.php?op ... oblem=4744

I think I found a "correct" approach for this problem, yet it's too inefficient (my code: https://gist.github.com/bengro/a092ed976a4b1f50494b).

I generate the sum of each pair of shot lengths (which is close to n^2). The input size suggests, that there is a linear/nlogn way of doing that?

Once I have all the possible lengths, I simply look them up for the rounds.

Any pointers of where I'm going wrong are appreciated! Thanks!

### Re: 12879 - Golf Bot

There is a O(d log d) solution to this problem.

Hint 1: restate the problem having vectors Shot

Hint 1: restate the problem having vectors Shot

*= 1 if there is a shot at distance i, 0 otherwise. Also have a vector Hole**as 1 if there is a hole at distance i*

Hint 2: see how we can multiply polynomials very quickly using FFT

Spoiler: see judges solutions at www.swerc.euHint 2: see how we can multiply polynomials very quickly using FFT

Spoiler: see judges solutions at www.swerc.eu

Miguel Oliveira