GCJ – Manage Your Energy

Manage Your Energy, Round 1A 2013

def solve_case(case):
    """Take the input data (structured in case) and perform any necessary
    calculations to obtain the desired output, formatted as the appropriate
    string.
    """
    E, R, N, values = case

    R = min(R, E) #Can't ever regain more than E units of energy

    #For each activity, find the nearest (in the future) more valuable activity
    near = np.zeros(N, dtype=int) - 1

    stack = []
    for i in range(N)[::-1]:
        while (len(stack) > 0) and (values[stack[-1]] <= 0):
            near[i] = stack[-1]
        stack.append(i)

    #Now iterate through each activity.
    current = E
    spent = np.zeros(N, dtype=int)
    for i in range(N):
        #If there's no better activity, spend all our energy
        if near[i] == -1:
            spent[i] = current
            current = 0
        else:
        #Otherwise, spend as much as we can while still having E energy for the next best
            avail = current + (near[i] - i) * R
            if avail > E:
                s = min(avail - E, current)
                current -= s
                spent[i] = s
        current += R

    return (spent * values).sum()
Advertisements

One thought on “GCJ – Manage Your Energy

  1. Pingback: Google Code Jam – Summary | Reflections of Dusk

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s