This is my code. I think it's O(N), please tell me if I am wrong.
T = gets.to_i
T.times do |i|
r, k, n = gets.split.map{|l| l.to_i}
g = gets.split.map{|l| l.to_i}
gi = g.clone
gt = gi.clone
gs = [] << gi.clone
sa = []
s = 0
ri = 1
while ri <= r
ss = 0
gi.each do |j|
if k >= ss + j
ss += j
gt << gt.shift
else
break
end
end
sa << ss
s += ss
gi = gt.clone
if gs.include?(gi)
gind = gs.find_index(gi)
sloop = 0
gind.upto(gs.length-1) {|gival| sloop += sa[gival]}
rr = (r - gind)/(ri - gind) - 1
ri += (ri - gind)*rr
sloop *= rr
s += sloop
gs.clear
sa.clear
else
gs << gi.clone
end
ri += 1
end
puts "Case ##{i+1}: #{s}"
end
On Mon, May 10, 2010 at 18:17, Liu Cheng <[email protected]> wrote:
> 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]<google-code%[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]<google-code%[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]<google-code%[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]<google-code%[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]<google-code%[email protected]>
> .
> For more options, visit this group at
> http://groups.google.com/group/google-code?hl=en.
>
>
--
Thanks & Regards,
Dhruva Sagar.
--
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.
