J  Gathering Sharks

Let’s renumerate the sharks such that shark \(i\) is the shark initially in the group numbered \(i\). We calculate a new array \(pos\), where \(pos[i]\) is the location of shark \(i\).

Executing a command is like merging two adjacent elements. Suppose the elements at indices \(x\) and \(y\) (\(x \lt y\)) are merged. Its merged result will have a position of \(pos[x]\) and an index of \(y\). Notice that, after the merge, its relative order with the rest of the elements remains the same, so its exact new index doesn’t matter. We can see this operation as the element at index \(x\) erasing the element at index \(y\), with a cost of \(|pos[x] - pos[y]|\).

We can solve this problem using dynamic programming. Let \(dp[l][r]\) (\(l \le r\)) be the minimum time required to have all sharks from \(l + 1\) to \(r\) get erased by shark \(l\). The base case is \(dp[l][r] = 0\) if \(l = r\).

Let’s figure out the transitions. For some pair \((l, r)\) (\(l \le r\)), let’s consider only the sharks from \(l\) to \(r\). Consider the sharks among them that are directly erased by shark \(l\). Let \(p\) be the last such shark to be erased. Then it must hold that:

• Every shark from \(l + 1\) to \(p - 1\) must be erased by sharks between \(l\) and \(p - 1\).
• Every shark from \(p + 1\) to \(r\) must be erased by sharks between \(p\) and \(r\).

That means, if we fix some value of \(p\), the minimum total time is equal to \(dp[l][p-1] + dp[p][r] + |pos[l] - pos[p]|\).

For each \(l \le r\), we brute force every single possible value of \(p\) (\(l + 1 \le p \le r\)) to get the minimum time.

Time complexity: \(O(n^3)\)