8 June 2019 by Tikai Chang

Google Kick Start 2019 Round B Q2 Energy Stones

Status: question/project completed

The original question statement is here.

There are N = 100 stones, of value $E_i$ 1 to 1E6 integer, decaying at a rate of $L_i$ (0~1e5) per round. A cooldown of $S_i$ is necessary after harvesting the value $E_i$ (1~1e5) per object before harvesting the next. Maximize the value please.

So this problem resembles a bit like knapsack, except that the stone’s value decreases linearly until it drops to zero. All the intuition we have for knapsack would be useful.

So for each individual stone the value decays as a function of time $f_i(t) = \max(E_i - L_i t, 0)$ .

Let’s start with intuitions from knapsack. Greedy suboptimal solutions…

Largest Decay rate first? If the stones has to all be picked and negative values are allowed ( $E_i - L_i t$ instead of $\max(E_i - L_i t, 0)$ ), it could be a nice way to pick! But the values stop decaying at 0…
Choose according to value? No, it could incur massive penalties afterwards.

Let’s say we do choose to pick a subset of stones that we indeed extract positive value from each one, can we say anything about it? Can we determine the order of these stones? Same question but permitting zero values.

We could sort using decay rate, energy and time still alive. And do branch and bound and backtracking depth first. Usually it is very hard to code backtracking depth-first during contests, you simply don’t have time. Plus the complexity would be (N=100) * (all nodes visited). Might be horrible, especially for the latter, smells expontial on N. The bounding would have to be very efficient.

So would a dynamical approach be possible? Well the cooldown is maximally 100 for each one, and there are 100 stones. So the table would be 10000 in the temperal dimension. So I went further along this path, maybe each temperal cell would represent a segment and the value functions would be affine per segment.. We would need another axe to index/order the chosen objects, limiting the search to remaining stones to be picked from bigger indexes than the last one chosen. The ordering would have to correspond to a real ordering in the optimal solution…

Typically, you would need to start backwards in this kind of problem: If at time t, only one stone of the remaining stones have positive value, then it must be chosen. So in some sense we see that the time at which the value decays to nothing seems to be a relevent order. But is it so in the optimal solution?

let us order the stones by the time at which the value reduces to 0. Stone 1 is the last stone to decay to dust, and 2 is second to last… To simplify, let’s just consider two stones. The time to reach 0 is denoted T1 and T2 respectively. Let’s consider t the time that we are able to choose something. Working backwards in time from t = T1, we see that the value increases with slope $L_1$ until T2, where we are presented with a possibility to choose stone 2. Choosing Stone 2 will incur a cooldown time S2 after harvesting, and if the time falls before T1, it means we can go on and eat stone 1. Idem for the possibility of eating 1 first and then 2.

We have these possibilities:

eat 1 only. Possible for all starting t <= T1
eat 2 only. Possible for all starting t <= T2
eat 2 then 1. Possible for all starting t <= T2 and t+S2 <=T1
eat 1 then 2. Possible for all starting t <= T1 and t+S1 <=T2

We kind of feel that the two latter leads to the two former… At infinitely early times (we could generalize the problem by saying the stones have been decaying since eternity, and project the time to negative values), the value that we obtain will have a slope (% to time) L1 + L2. Then at some point it could be L2, then L1 all the way down to value = 0 or inversely. Or… just L1 or L2 all the way down to value = 0. A slope of L2 means that you are choosing stone 2 and that after it’s cooldown the remaining stones no longer have value. L1+L2 means after eating 2 or 1 you still have time to eat the other.

So from t = t0 where t0 is arbitrary small, which is better 2->1 or 1->2? The two ways have these values:

f1(t0) + f2(t0 + S1) = f1(t0) + f2(t0) - S1*L2
f2(t0) + f1(t0 + S2) = f1(t0) + f2(t0) - S2*L1

So we notice that the comparison between the two options could be represented by the comparison of S/L, whoever is smaller will be the first to be chosen. This combines two intuitions:

the one with a slower decay rate can wait, much like in the emergency room the guy which is losing blood fast must first be treated. Hence the 1/L factor.
the one with a smaller penalty should be preferred. Hence the S factor.

So with this observation, we can think of a generalization. For any subset of stones chosen, active (meaning the stones have positive value at the time of the harvest) stones, swapping locally the order of two neighboring (as in the order in which they are harvested) stones indexed by a and b, would come back to swapping $-S_a \times L_b$ by $-S_b \times L_a$ in the final value. Effectively since the swap is local, all the stones chosen before a and b and those chosen after will not be affected.

So for sure, since the global optimal is also a local optimal by this swap, we deduce that the stones must be harvested in the order of increasing S/L. A tie condition for S/L means no change with respect to the swap.

The problem is now as follows: Let us denote D=S/L. Find the D-ordered sublist of all stones such that if we pick in that order, all stones are active, and yields the maximum value. We could try to bruteforce this description using dynamical programming.

Thinking of the optimal solution of knapsack, in which we have a 2D array which is capacity and next most valuable to be included. Here the scarce resource is time. If we do the same thing the time dimension will have 100x100 entries. So in the end this will be a 100x100 by 100 table. That is quite doable.

import numpy as np
from collections import namedtuple
from typing import List
Rock = namedtuple('Rock','s e l t ni')
t = int(input())
for ti in range(1, t + 1):
    n = int(input())
    S, E, L = [], [], []
    SELTN = []
    for ni in range(n):
        s, e, l = tuple(map(int, input().split()))
        S.append(s)
        E.append(e)
        L.append(l)
        if l != 0:
            t = e / l
        else:
            t = 100001#np.Inf
        seltn = Rock(s,e,l,t,ni)
        SELTN.append(seltn)


    def key(sel:namedtuple):
        s, e, l, t, n = sel
        if l != 0:
            return s / l
        else:
            return 101#np.Inf


    SELTN.sort(key=key)
    endTime = sum(S)
    score = -np.ones((n, endTime+1), dtype=int)
    time = np.arange(endTime+1)
    last = SELTN[-1]
    _ = last.e - time * last.l
    _[_<0]=0
    score[len(SELTN)-1, :] = _
    last.e - time * last.l

    # last sorted using key should be greedy
    for ni in range(2,n+1):
        building = SELTN[-ni]
        lastOne = SELTN[-ni+1]
        _ = building.e - time * building.l
        _[_ < 0] = 0
        _last = np.pad(score[-ni+1, :],((0,building.s)),mode='edge')
        _last = _last[building.s:]
        _ += _last
        _res = np.maximum(_,score[-ni+1, :])
        score[-ni, :] = _res
        pass
    # borders:

    answer = score[0,0]
    print('Case #{}: {}'.format(ti, answer))

I just realized! DO NOT USE TYPING ON THEIR PLATFORM, it will give you a compile error! Worse than runtime error! Success!

SELTN:List[Rock] = []

This will break things!

tags: GKS - competition - python