PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Daniel Emeka-Ilozor
Tester: Harris Leung
Editorialist: Pratiyush Mishra, Jakub Safin
DIFFICULTY:
Easy
PREREQUISITES:
None
PROBLEM:
There are objects 1, 2, \ldots, N in a line. You should perform N-1 operations; in each operation, you either remove the left neighbour of a not-yet-removed object i (with cost L_i) or its right object (with cost R_i), and push the remaining objects closer to remove the gap. You can’t perform any operation twice or remove a non-existing object, but removing both a left and a right neighbour of the same object i is allowed. Find the minimum total cost.
EXPLANATION:
It’s often the best to start by looking at the last remaining object. In this case, we can observe that this object is either the leftmost at the start or we have to remove its left neighbour once, since it’s the only move once there’s only one object remaining to its left, and similarly, it’s either rightmost or we have to remove its right neighbour once.
We can solve the problem recursively: choose the last remaining object, solve the subproblem for objects to its left and the subproblem for objects to its right, and perform operations on the last object to remove its neighbours (unless it’s at the border). Bruteforce implementation has exponential complexity, but since each subproblem is defined by a range [l,r] (1 \le l \le r \le N), we can use dynamic programming on these O(N^2) states for a straightforward O(N^3) implementation.
To go further, we need to find a more specific description of valid sequences of operations. Let’s look at the last remaining object again and denote it by m. We’re never going to use L_{m+1}, since it’d remove this object, and we’re always going to use R_m if m \lt N. Similarly, we’re going to use L_m (if m \gt 1) but not R_{m-1}. The same reasoning can be applied recursively, telling us that for each valid i, we’re going to use either R_{i-1} or L_i, but never both. That’s exactly N-1 operations.
It also turns out that no matter how we choose between R_{i-1} or L_i (independently for each valid i), it always leads to a valid sequence of operations with the following construction:
- Find an object k such that we don’t use either L_k or R_k. Such an object always exists from pigeonhole principle - there are only N-1 operations selected for N objects.
- If there’s only one object, we’re done. Otherwise, it has a neighbour (either k-1 or k+1, possibly both) that has a selected operation R_{k-1} or L_{k+1} respectively.
- We choose one neighbour, use the corresponding operation to remove k. Then we remove that operation, e.g. if k-1 had selected operations L_{k-1} and R_{k-1}, then we’re going to use L_{k-1} later.
- Push the remaining N-1 objects closer to remove the gap and repeat.
The optimal solution turns out to be surprisingly short. For each valid i, we just need to choose the cheaper operation among R_{i-1} and L_i.
P.S.: The recursive solution builds a tree over the N objects, with inorder labelling. The condition that we can’t use an operation twice says it’s a binary tree.
TIME COMPLEXITY:
O(N)