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 at
http://groups.google.com/group/google-code?hl=en.
