@Mikhail: True, I didn't think about the O(N^2) part in the beginning. That means that there's no real advantage in using this over some O(N^2) solution. My original thinking was that lg R < 30 << 1000 so this might beat the O(N^2) approach.
On May 10, 2:32 pm, Dario <[email protected]> wrote: > 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 > 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.
