I just made the large input case for problem C by storing 'next position' and 'cash' arrays, then just iterating over them R times. This seems to be O(N+R). But I've been wondering about possible optimizations to this. I can think of an O(NlogR) solution in which I nest the 'next position' and 'cash' arrays, only adding up cash/ changing position when the correct bit of R is on (binary). I've pasted my code below (the algorithm described here is really just the solve() function and the rest is wrapping). I'd be interested in a comparison of different optimizations/algorithms over the problem space?
def doProb(fname, ofname): #do problem 3 given a file name f = open(fname, 'r'); T = int(f.readline()); output = ['Case #' + str(i) + ': '+ \ str(solve([int(j) for j in f.readline().split()], [int(j) for j in f.readline().split()])) + \ '\n' for i in range(1,T+1)]; f.close(); of = open(ofname, 'w'); of.writelines(output); of.close(); def solve(x,g): (R,k,N) = x; #unpack the input (np, cash) = getParms(k,g); cur = 0; tot = 0; while(R>0): incl = R%2; R = R//2; if(incl==1): tot += cash[cur]; cur = np[cur]; (np, cash) = nest(np, cash); return tot; def nest(np, cash): #thinking of np as a permutation, get np^2 and total cash list np2 = [0]*len(np); c2 = [0]*len(np); for i in range(len(np)): np2[i] = np[np[i]]; c2[i] = cash[i]+cash[np[i]]; return (np2, c2); def getParms(k,g): N= len(g); #special case, all passengers fit in the roller coaster: if(sum(g) <= k): np = [i for i in range(N)]; cash = [sum(g)]*N; return (np, cash); #other cases np = []; cash = []; for i in range(N): tot = g[i]; j = i; while(tot <= k): j = (j+1)%N; tot += g[j]; tot -= g[j]; np.append(j); cash.append(tot); return (np, cash); -- You received this message because you are subscribed to the Google Groups "google-codejam" group. To post to this group, send email to google-c...@googlegroups.com. To unsubscribe from this group, send email to google-code+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/google-code?hl=en.