How exactly would the O(N) solution work? On May 9, 9:23 pm, hamzawy <[email protected]> wrote: > 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 > 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.
