Codeforces Notes

855B: Marvolo Gaunt’s Ring

Offical solution uses a multiple stage DP approach

v[0][0] = p * a[0]
v[0][1] = (p + q) * a[0]
v[0][2] = (p + q + r) * a[0]

LP(i , 1, n) {
	v[i][0] = max(v[i-1][0], p *a[i]) 
	v[i][1] = max(v[i-1][1], q * a[i] + v[i][1])
	v[i][2] = max(v[i-1][2], r * a[i] + v[i][2])
}

return v[n-1][2];

855C: Helga Hufflepuff’s Cup

I got the DP states during the contest, but I got stuck calcualting ways to distribute max security nodes among children!!!

consider the node with n nodes, # of ways to distribute k top security nodes amoung them is

ways(childI, type, secN) = sum over ways(childI - 1, type, secN - sofar) * f(childI, type, j)

Note runtime/memory is OK because secN <= 10

864E: Fire

Obviously if we save 2 items in the final solutions, we can greedily save the one with less t(i) first. So we sort by t(i) first, we know the final solution must be a subsequence in this sorted array

Now we have 2 states we need to worry about, current time and value. I got stuck how to handle it!!!

Note that value range is small, we can force the parameter as part of DP state,i.e., knapsack idea

minT(i, v) = minimum time to save value v among the first i items

Alternatively, we can use maxV(i, t) too, but the value range for v is 400 , much less than the t range