PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: wuhudsm
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Medium
PREREQUISITES:
Dynamic Programming
PROBLEM:
There are N slimes in a row. The i-th one has parameters (A_i, B_i).
In one operation, you can choose two adjacent slimes, say with parameters (a, b) and (x, y), and merge them into a single slime with parameter (a+y, b-x-y).
You would like to merge all N slimes into a single slime. Find the maximum possible sum of parameters of this final slime.
EXPLANATION:
We merge adjacent slimes, so at any point of time, each slime present in the array represents the result of merging (in some order) a consecutive segment of original slimes.
Of course, the ranges corresponding to existing slimes also form a partition of the order of original slimes.
This suggests that we should maintain some information about each range of slimes, i.e. f(L, R) denotes some information about merging slimes L, L+1, \ldots, R somehow.
Our task is to figure out what information to keep so that the final answer can be obtained by merging such information.
To compute the answer for a subarray, we’ll have to eventually merge the answers for two subarrays, which corresponds to merging two slimes.
Let’s analyze that = suppose we have only two slimes, with parameters (A_1, B_1) and (A_2, B_2).
Since we also care about the sum of parameters, let’s include that information too: the slimes are now (A_1, B_1, A_1 + B_1) and (A_2, B_2, A_2 + B_2).
They can be merged into either (A_1 + B_2, B_1 - A_2 - B_2, A_1 + B_1 - A_2) or (A_2 + B_1, B_2 - A_1 - B_1, A_2 + B_2 - A_1).
For convenience let S_i = A_i + B_i, so the two options we have are (A_1 + B_2, B_1 - S_2, S_1 - A_2) and (A_2 + B_1, B_2 - S_1, S_2 - A_2).
Note that each element of the resultant tuple is a sum/difference of one component of the first tuple and one component of the second.
Our aim is to maximize the third component, so it’s ideal to either maximize S_1 and minimize A_2, or maximize S_2 and minimize A_1. These can be done independently of each other, since the slimes correspond to results of disjoint subarrays.
Maximizing S_i is already something we want to do, so let’s look at minimizing A_i.
The new first component is A_i + B_j for i \ne j. To minimize this, we need to minimize both A_i and B_j, since once again, they’re independent anyway.
Minimizing A_i is already our goal, so we turn to minimizing the B-component.
Here, we want to minimize B_i - S_j. This corresponds to minimizing B_i and maximizing S_j - both of which we already want to do!
With the above idea in mind, we can define the following states:
Let dp[i][j][k] denote the optimal value of the k-th component obtained by merging slimes i, i+1, \ldots, j into a single slime, where for k = 1 and k = 2 we want to minimize the value, and for k = 3 we want to maximize it.
Computing this is now not too hard.
For i = j, the values at states dp[i][i][k] can be set by just looking at the initial slimes.
For i \lt j, the merged slime must come as a result of merging some prefix and the remaining suffix of the segment.
So, for each i \leq x \lt j, combine the results of dp[i][x][k_1] and dp[x+1][j][k_2] appropriately.
This runs in \mathcal{O}(N^3) time, since there are \mathcal{O}(N^2) states and \mathcal{O}(N) transitions from each - which is fast enough for the given constraints.
It’s possible to avoid writing a large amount of casework with some smart implementation choices.
First, note that we want to minimize some coordinates while maximizing others.
Since only addition/subtraction happen here, we can just negate the coordinates that need to be minimized, so that everything now needs to be maximized.
Once this is done, observe that dp[i][j][k] will always be either dp[i][x][k] + dp[x+1][j][k+1] or dp[i][x][k+1] + dp[x+1][j][k] because of how the cyclic relations between coordinates work out in transitions.
This allows for pretty much all casework to be skipped - see the implementation below.
TIME COMPLEXITY:
\mathcal{O}(N^3) per testcase.
CODE:
Editorialist's code (C++)
// #include <bits/allocator.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int t; cin >> t;
while (t--) {
int n; cin >> n;
vector<array<ll, 2>> a(n);
for (auto &[x, y] : a)
cin >> x >> y;
const ll inf = 1e18;
vector dp(n, vector(n, array<ll, 3>{-inf, -inf, -inf}));
for (int i = 0; i < n; ++i)
dp[i][i] = {-a[i][0], -a[i][1], a[i][0] + a[i][1]};
for (int len = 2; len <= n; ++len) for (int i = 0; i+len <= n; ++i) {
int j = i + len - 1;
for (int x = i; x < j; ++x) {
for (int k = 0; k < 3; ++k) {
dp[i][j][k] = max(dp[i][j][k], dp[i][x][k] + dp[x+1][j][(k+1)%3]);
dp[i][j][k] = max(dp[i][j][k], dp[i][x][(k+1)%3] + dp[x+1][j][k]);
}
}
}
cout << dp[0][n-1][2] << '\n';
}
}