Why not to solve it in O(N) (such that N is the number of the group)?? On May 9, 5:42 pm, Dario <[email protected]> wrote: > 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group > athttp://groups.google.com/group/google-code?hl=en.
-- You received this message because you are subscribed to the Google Groups "google-codejam" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/google-code?hl=en.
