[gcj] Re: Round 3, Problem A. Binary search really necessary for O(n) solution?
Hi, I tried to run your solution through (using PyPy 2.3.1) A-large-practice, and received the WA judgment on your output using that code. Is it meant to produce AC code through A-large-practice.in? Lee Wei On Sunday, June 22, 2014 12:09:54 AM UTC+8, Eibe wrote: I just read the analysis for problem A of round 3 and it is mentioned that binary search is necessary for an O(n) solution. I don't think it is but maybe something with my thinking is wrong (I don't have a strict proof of correctness of the following): Let ts be a list, where ts[i] is the numbers of transistors in device i. Start with the following partition left, middle, right = [], ts, [] Now repeatedly move either the leftmost element of middle into left or the rightmost element of middle into right in a way that increases max(sum(left), sum(right)) in the least possible way. That is if sum(left) + middle[0] sum(right) + middle[-1] move the leftmost otherwise the rightmost element (middle[-1] denotes the rightmost element of middle). I am a little sloppy here, but as we increase max(sum(left), sum(right)) by a minimal amount it feels that we will visit an optimal partition of ts eventually. In python code: T = int(raw_input()) for case in range(1, T+1): N, p, q, r, s = map(int, raw_input().split()) ts = [(i*p+q)%r+s for i in range(N)] c0, c1, c2 = 0, sum(ts), 0 a, b = 0, N solveig = sum(ts) while a b: if c0 + ts[a] = c2 + ts[b-1]: c0 += ts[a] c1 -= ts[a] a += 1 else: c2 += ts[b-1] c1 -= ts[b-1] b -= 1 solveig = min(solveig, max(c0, c1, c2)) res = 1 - solveig / sum(ts) print Case #%i: %.10f %(case, res) -- You received this message because you are subscribed to the Google Groups Google Code Jam group. To unsubscribe from this group and stop receiving emails from it, send an email to google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/869face2-2cb2-43c2-ab5c-b2555f010dad%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [gcj] Re: Round 3, Problem A. Binary search really necessary for O(n) solution?
I guess you'd probably want res = 1 - (solveig + 0.0) / sum(ts) as the penultimate line. Sent from my iPad On 22 Jun 2014, at 09:48, evandrix evand...@gmail.com wrote: Hi, I tried to run your solution through (using PyPy 2.3.1) A-large-practice, and received the WA judgment on your output using that code. Is it meant to produce AC code through A-large-practice.in? Lee Wei On Sunday, June 22, 2014 12:09:54 AM UTC+8, Eibe wrote: I just read the analysis for problem A of round 3 and it is mentioned that binary search is necessary for an O(n) solution. I don't think it is but maybe something with my thinking is wrong (I don't have a strict proof of correctness of the following): Let ts be a list, where ts[i] is the numbers of transistors in device i. Start with the following partition left, middle, right = [], ts, [] Now repeatedly move either the leftmost element of middle into left or the rightmost element of middle into right in a way that increases max(sum(left), sum(right)) in the least possible way. That is if sum(left) + middle[0] sum(right) + middle[-1] move the leftmost otherwise the rightmost element (middle[-1] denotes the rightmost element of middle). I am a little sloppy here, but as we increase max(sum(left), sum(right)) by a minimal amount it feels that we will visit an optimal partition of ts eventually. In python code: T = int(raw_input()) for case in range(1, T+1): N, p, q, r, s = map(int, raw_input().split()) ts = [(i*p+q)%r+s for i in range(N)] c0, c1, c2 = 0, sum(ts), 0 a, b = 0, N solveig = sum(ts) while a b: if c0 + ts[a] = c2 + ts[b-1]: c0 += ts[a] c1 -= ts[a] a += 1 else: c2 += ts[b-1] c1 -= ts[b-1] b -= 1 solveig = min(solveig, max(c0, c1, c2)) res = 1 - solveig / sum(ts) print Case #%i: %.10f %(case, res) -- You received this message because you are subscribed to the Google Groups Google Code Jam group. To unsubscribe from this group and stop receiving emails from it, send an email to google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/869face2-2cb2-43c2-ab5c-b2555f010dad%40googlegroups.com. For more options, visit https://groups.google.com/d/optout. -- You received this message because you are subscribed to the Google Groups Google Code Jam group. To unsubscribe from this group and stop receiving emails from it, send an email to google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/7DF07896-3EF7-4BF5-9DD4-AA4FE20688F8%40pebody.org. For more options, visit https://groups.google.com/d/optout.
[gcj] Re: Round 3, Problem A. Binary search really necessary for O(n) solution?
oops, a copy and paste mistake I made. I forgot the first line of the code: from __future__ import division -- You received this message because you are subscribed to the Google Groups Google Code Jam group. To unsubscribe from this group and stop receiving emails from it, send an email to google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/dfa29c8d-22e0-4429-b63f-40a49794ee59%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [gcj] Re: Round 3, Problem A. Binary search really necessary for O(n) solution?
Yes, this solution works. Sadly, I came up with this solution after the contest. The solution that I crafted during the contest was the binary-search method, but I had a little bug in deciding whether a given value would not work. My method worked for all of the examples in the small test, and all of the examples but 1 in my large test. It actually works for all of the examples in the version of the large data set that can be downloaded now. Very frustrating. -- You received this message because you are subscribed to the Google Groups Google Code Jam group. To unsubscribe from this group and stop receiving emails from it, send an email to google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/CAECKw-ONix-1xkLKkKAd1YMZmQ036TLQ2eL%2BPSHVGAbY7CUBNQ%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
