Hi, Ah, now it works on A-large-practice. Though it takes quite a while longer for python, vs. pypy.
Well spotted, on the int vs. float division fix. So, maybe that is to say that the proposed strategy might be correct too instead of a binary search as the editorial suggests, assuming the test cases are well-crafted. Thanks On Sunday, June 22, 2014 5:54:28 PM UTC+8, Luke Pebody wrote: > 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 <[email protected]> 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 [email protected]. > > > To post to this group, send email to [email protected]. > > > 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 [email protected]. To post to this group, send email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/40543a25-8d47-4869-a06b-d54cf6478ca1%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
