Page 1 of 1

Time limit on 12879 - Golf Bot is too high

Posted: Sat Nov 29, 2014 8:05 pm
by 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.

12879 - Golf Bot

Posted: Mon Dec 01, 2014 1:52 pm
by 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!

Re: 12879 - Golf Bot

Posted: Mon Dec 01, 2014 11:16 pm
by 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