This psuedocode will do the necessary computation in O(N)
input: array group_size of size N, max_riders
outputs: array next_group of size N, array ride_size of size N // if
ride r starts with group g, then ride r+1 will start with group
next_group[g] and contain ride_size[g] riders
It keeps two pointers (start_group and end_group) and keeps the
invariant that current_riders is the sum of group_size from
start_group through (end_group-1)
end_group=0
current_riders=0
for( start_group from 0 to N-1) // figure out
while(current_riders + group_size[end_group] < max_riders) // keep
adding groups until
current_riders+=group_size[end_group]
end_group= (end_group+1) mod N
ride_size[start_group]=current_riders
next_group[start_group]=end_group;
current_riders-=group_size[start_group]
Explanation:
This will work as long as not everyone at the park can fit on the ride
at once (which can be checked beforehand in O(N)
The inner loop will only iterate O(N) times overall (this can be seen
because end_group will never wrap around to pass start_group, so will
be incremented less than 2*N times throughout the algorithm)
On May 10, 10:13 pm, Pedro Osório <[email protected]> wrote:
> So... Has anyone figured theO(N) solution out?
>
> --
> 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.
