1. Space Station Cleanup

The solution is to use dynamic programming. The tricky part is that on a ring it's not clear where to start. So we consider two cases: in case 1, we clear bay 1; in case 2, we don't (and thus must clear bays n and 2). This reduces the problem to two problems on a line, in which we want to find the minimum number of Leptons to remove. This we can solve easily.

{{{Line(A):

• // B[i][0] is the cheapest way to clear A[1..i] if bay i is emptied // B[i][1] is the cheapest way to clear A[1..i] if bay i is left full B = array[1..length(A)][0..1] B[1][0] = A[1] B[1][1] = 0 for i = 2 to n:
  • B[i][0] = min(B[i-1][0], B[i-1][1]) + A[i] B[i][1] = B[i-1][0]
  return min(B[n][0], B[n][1])

}}}

And now we just call Line twice:

{{{Ring(A):

• return min(Line(A[2..n]) + A[1], Line(A[3..n-1]) + A[2] + A[n])

}}}

2. Rocket to Russia

This, too, is a job for dynamic programming. The first idea is that we can compute the optimal schedule for days 1..i for each set of of packages left over that must be sent on day i+1. Unfortunately this may require considering as many as 2^m different sets of leftover packages. But we only really care about the total weight the leftovers add to the day i+1 rocket, and this will be an integer in the range 0..5m, which is nicely linear, allowing us to use the same approach as in knapsack with small item weights. So we can solve the problem as follows:

{{{MinFuel(schedule):

• M = array[0..n][0..5m] initialized to +infinity M[0][0] = 0 for i = 1 to n do
  • let w be the total weight of the day i packages compute all sums of subsets of the day i packages for each s in the list of sums:
    • M[i][s] = min over all s' of M[i][s'] + (w-s+r)^2
  return M[n][0]

}}}

We've left out the details of how to compute all the subset sums in the middle step in the loop, but using the same technique as used for knapsack we can easily do this in w*m_i = O(m²) time, where m_i is the number of items shipped on day i. The total cost of the min operation in the innermost loop is O(m); the cost of the inner loop is O(m²); so the cost of the outer loop at the algorithm is O(nm²).