12879 - Golf Bot

[mogers]

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.

[bengro]

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!

[mogers]

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

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.eu