I used the O(n) solution in the contest.
You can see my code.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int g[1024];
int f[1024];
long long c[1024];
int main() {
freopen("park.in", "r", stdin);
freopen("park.out", "w", stdout);
int T, tc = 0;
scanf("%d", &T);
while (T -- > 0) {
int r, k, n;
long long ans = 0;
memset(f, 255, sizeof(f));
memset(c, 0, sizeof(c));
scanf("%d%d%d",&r,&k,&n);
for (int i = 0; i < n; ++i) {
scanf("%d", g+i);
}
int pos = 0;
int t = 0;
while (1) {
if (t >= r) break;
if (f[pos] == -1) {
int oldpos = pos;
long long oldans = ans;
int oldt = t ++;
int remain = k;
while (g[pos] <= remain) {
remain -= g[pos];
ans += g[pos];
if (++pos == n) pos = 0;
if (pos == oldpos) break;
}
f[oldpos] = oldt;
c[oldpos] = oldans;
} else {
int cnt = (r - t) / (t - f[pos]);
ans += (ans - c[pos]) * cnt;
t += (t - f[pos]) * cnt;
memset(f, 255, sizeof(f));
memset(c, 0, sizeof(c));
}
}
cout << "Case #" << ++tc <<": " << ans << endl;
}
return 0;
}
On Mon, May 10, 2010 at 8:40 PM, Dario <[email protected]> wrote:
> @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.
>
>
--
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.
