Removal Game

This problem asks you the optimal strategy for a game where you remove numbers from a list, where the "penalty" for removing a number is the GCD of the surrounding numbers.

This seems like a simple DP problem at face value, but most standard techniques fail due to n=100:

Simulate every ordering: O(n!)...too big.

Simulate every set of possible remaining numbers: O(n*2^n)...too big.

Simulate dividing the list and recursing on sublists: O(n^3). This is a standard divide and conquer. The issue is, the problems are not independent.

So the standard technique for divide and conquer DP is:

1. iterate over each division point
2. simulate "removing" the point
3. recurse on each newly created sublist
4. Take the optimal division

The subproblems in DP need to be independent, though. Here, however, that is NOT the case, since once we've removed the dividing element, the removal of any element at the EDGE of one of the sub-lists depends on the value of the element on the end of the OTHER sub problem. Then your total answer depends on the relative ordering of the removals from the subproblems, and you get back up to some exponential runtime again.

Further, we have the problem of the list being cyclic. This is easily solvable, however, by just allowing the start and end of a subproblem to wrap around. Namely, if start > end, then it goes around the end of the array. The runtime would still be the same, and you just have to fiddle with mods.

The solution to this problem, admittedly, is hard to arrive at on ones own. However, is very easy to understand once learned.

Consider the typical divide and conquer before. We process the element we're on BEFORE recursing. In tree parlance, this is a pre-order traversal. If, however, we do a POST order traversal, how would that look?

1. iterate over each division point
2. recurse on each "sublist" while leaving the division point in place
3. simulate "removing" the point
4. take the optimal division

Now, when we look at each sublist and try to remove an end-point, instead of being dependent on the other sublists, we're only dependent on the division point which is STILL IN PLACE! From an intuitive standpoint, we're doing DP, but the points we select are the ones we remove LAST (just like post-order traversal).

Having that, a natural algorithm follows:

1. Iterate over all pairs of LAST two elements to be removed
2. recurse on the two sublists formed
   1. iterate over each LAST element to be removed from a sublist
   2. recurse on the sublist formed
   • be sure to deal with the edge cases by appropriately looking at the to-be-removed-but-currently-selected elements which our caller chose as division points

the ultimate relation is

dp[i,j] = best solution for i->j (including wraparound) = min:

• gcd(i-1,j+1) + dp[i+1,j] (remove first element last)
• gcd(i-1,j+1) + dp[i,j-1] (remove last element last)
• gcd(i-1,j+1) + dp[i,x-1] + dp[x+1,j] (remove element X last)

Then, to simulate the last removal, which involves two numbers, we iterate over all pairs i,j and return:

min(gcd(i,j) + dp[i+1,j-1] + dp[j+1,i-1])

DP tbale is n^2 large, and each recurrence takes n time, yielding O(n^3) runtime which is fast enough.