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/ae2b4d87-8788-4dcf-98e8-dd095035a933%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
