MARRAYS - Editorial




Author: Dmytro Berezin

Tester: Alexey Zayakin

Editorialist: Jakub Safin




dynamic programming


You’re given N arrays A_1,\dots,A_N; the i-th array has length M_i. You’re allowed to cyclically shift any array; you may perform this operation any number of times. Compute the maximum possible value of \sum_{i=1}^{N-1} i\left|A_i\lbrack M_i\rbrack-A_{i+1}\lbrack 1\rbrack\right| after performing zero or more cyclic shifts.


Dynamic programming computing the maximum partial sums \sum_{j=2}^i (j-1)\left|A_{j-1}\lbrack M_{j-1}\rbrack -A_j\lbrack 1\rbrack\right| for each possible A_i\lbrack 1\rbrack (each cyclic shift of each array A_i).


Let’s imagine we knew the optimal cyclic shift of the array A_i. The central observation is that the optimal cyclic shifts of the previous i-1 arrays and the next N-i arrays are independent - of course, they both depend on A_i\lbrack 1\rbrack and A_i\lbrack M_i\rbrack, but not on each other.

That means we can compute the maximum sum from arrays A_{1..i} for each possible cyclic shift of A_i - if we shifted A_i from the input by s_i, so that A_i\lbrack s_i+1\rbrack becomes A_i\lbrack 1\rbrack, let’s call that maximum possible sum S_{i,s_i} - and use dynamic programming to compute all S_{i,j} from the known values of S_{i-1,j}.

The initial condition is naturally S_{1,j}=0~\forall j, since there are 0 terms in that sum. For i > 1, assume we’ve computed all values S_{i-1,j}; we can write a general expression using these values and the input arrays:

S_{i,s_i} = \mathrm{max} ( S_{i-1,j} + (i-1)\left|A_i\lbrack s_i+1\rbrack -A_{i-1}\lbrack j\rbrack\right| )\quad \forall~0 \le j < M_{i-1}\,,

where we’re using the fact that if the array A_{i-1} was shifted by j=s_{i-1}, then A_{i-1}\lbrack s_{i-1}+1\rbrack becomes its first element, so A_{i-1}\lbrack s_{i-1}\rbrack becomes its last element (we’re also using the convention A_{i-1}\lbrack 0\rbrack=A_{i-1}\lbrack M_{i-1}\rbrack).

Usually, working with absolute values directly is complicated. It’s a good idea to split the \mathrm{max}() into 2 cases based on which of the numbers A_i\lbrack s_i+1\rbrack, A_{i-1}\lbrack j\rbrack is greater, compute the separate maxima and take their maximum, but there’s a trick we can use here: |x|=\mathrm{max}(x,-x), so

\mathrm{max} ( S_{i-1,j} + (i-1)\left|A_i\lbrack s_i+1\rbrack-A_{i-1}\lbrack j\rbrack\right| ) = \mathrm{max} \left\lbrack \\ \mathrm{max} ( S_{i-1,j} + (i-1)\left(A_i\lbrack s_i+1\rbrack-A_{i-1}\lbrack j\rbrack\right) )\quad \forall~j, \\ \mathrm{max} ( S_{i-1,j} + (i-1)\left(-A_i\lbrack s_i+1\rbrack+A_{i-1}\lbrack j\rbrack\right) ) \quad \forall~j \\ \right\rbrack \,.

In other words, we can compute the maxima for both possible signs and just take their maximum afterwards - the wrong sign will always give a \le number than the right one, so it won’t affect the result.

This trick is fairly common when you’re asked to compute the maximum of a function involving absolute values, e.g. in a grid with Manhattan distances, and simplifies the code considerably. Note that it fails if you need to compute a minimum instead.

Now let’s get back to our problem. It’s not very hard to compute the maxima we need now, since we can write

\mathrm{max} ( S_{i-1,j} + (i-1)\left(A_i\lbrack s_i+1\rbrack-A_{i-1}\lbrack j\rbrack\right) ) = \mathrm{max} ( S_{i-1,j} - (i-1)A_{i-1}\lbrack j\rbrack ) + (i-1)A_i\lbrack s_i+1\rbrack \,;

the term with the maximum doesn’t depend on s_i or A_i and since we already know all S_{i-1,j}, we can compute it in O(M_{i-1}) time and call it m_1. Similarly, we get

\mathrm{max} ( S_{i-1,j} + (i-1)\left(-A_i\lbrack s_i+1\rbrack+A_{i-1}\lbrack j\rbrack\right) = \mathrm{max} ( S_{i-1,j} + (i-1)A_{i-1}\lbrack j\rbrack ) - (i-1)A_i\lbrack s_i+1\rbrack \,,

where the first term with the maximum can be computed just as easily; let’s call it m_2. The final formula is

S_{i,s_i} = \mathrm{max} ( m_1+(i-1)A_i\lbrack s_i+1\rbrack, m_2-(i-1)A_i\lbrack s_i+1\rbrack ) \,.

If we use it, we can compute S_{i,s_i} for all 0 \le s_i < M_i in O(M_i) time.

This way, we can compute all the sums S_{i,j} for increasing i; to get the answer to the problem, we need to take \mathrm{max} (S_{N,j}) over all 0 \le j < M_N.

For a test case with \sum M_i = N, this algorithm then runs in O(N) time and O(N) memory.


Setter’s solution

Tester’s solution

Editorialist’s solution


Is it possible to get a description of atleast setter’s approach? Lots of functions and stuff I dont understand, like-

vector<pair<__int128_t, int>> funcs = {{0, 0}};
		for (long long i = 0; i < n; i++) {
			decltype(funcs) pos, neg;

These are features of modern C++.

__int128_t is just a 128-bit integer

{{0, 0}} is initialisation - the vector has one element, which is the pair (0, 0)

decltype(funcs) gives the type of funcs: vector<pair<…>>

I solved this using segment trees. Nice dp approach.

Overkill, but how did you apply it here? :stuck_out_tongue:


For the segment tree approach initially start from the array m.Only for the array m we can find that the end of the array m has to be either the minimum or the maximum.

For the rest of the array i, we can say observe that in the sorted version of array i-1, each of the possible values that are in the corner between array i-1 and array i are the preferred values for a particular range of values.

For eg., if the sorted version of array i-1 is: 1 3 5 14 18 19

then we can say that some value x is the preferred value for the first 3 elements , then y is preferred for say the next element then some z for the remaining elements.

Initially assume the first element in the corner is the best for all of array i-1 and update the segment tree. Now update the segment tree using the second element of array i and so on.

Since there are only atmost n values in array i it takes O(nlogn) for updation.

Later in array i-1 we can use the original version and recover the preferred values in the segment tree.

Sorry if I confused you.

My solution


Okay. Thanks! I thought its some datatype or something. I think its time to read code along with google in side tab XD. Thanks again :slight_smile:

@ceilks Can you please explain me your approach ? It runs quite fast compared to mine dp with memoization.

test cases weak, naive solution passes


Brute Force solution also passed. Forming every possible pair of ith and comparing with every possible pair of i+1.

Damn, this editorial is so well written!

1 Like

we shifted Ai from the input by si, so that Ai[si+1] becomes Ai[1].Is it always possible?

Here is a video editorial on the problem.


@gkcs thanks for the video editorial.only after your explanation this editorial is clear to me now

yes you did

using namespace std;

typedef pair<int, int> ii;
vector<vector<long long> > store;

int n;
long long funct(vector<vector<int> > &ingd, int index, int pos) {
    //choosing pos as first ingredient of current index(dish)
    if(store[index][pos] != -1) {
        return store[index][pos];

    int sz = ingd[index+1].size();

    long long cur_max = 0; // maximum value of current ingredient 

    for(int i = 0; i < sz; ++i) {
        long long cur_sum = 0;

        int p = (pos - 1 < 0 ? (ingd[index].size()-1) : pos-1);
             // p is the corresponding last ingredient of current dish(index)
        cur_sum = funct(ingd, index+1, i);  
                  // get tastiness for next dish choosing i as its first dish

        cur_sum += (abs(ingd[index+1][i] - ingd[index][p])*(long long)(index+1));

        cur_max = max(cur_max, cur_sum); // for getting out the maximum

    store[index][pos] = cur_max; // storing tastiness as pos is kept first for index dish

    return cur_max; 
int main() {
    int t;
    cin >>  t;
    while(t--) {
        scanf("%d", &n);
        vector<vector<int> > ingd(n, vector<int>(0));
        store.resize(n, vector<long long> (0));

        // taking input
        for(int i = 0; i < n; ++i) {
            int k;
            scanf("%d", &k);
            store[i].resize(k, -1);
            while(k--) {
                int a;
                scanf("%d", &a);
        for(int i = 0; i < ingd[n-1].size(); ++i) {
            store[n-1][i] = 0;  // tastiness for last dish is zero

        long long ans = 0;
        for(int i = 0; i < ingd[0].size(); ++i) {
            //getting tastiness of all dishes if i keep i,th ingredient as first
            ans = max(ans, funct(ingd, 0, i));  

        cout << ans << "\n";

Please someone explain why i am getting TLE for my solution, i have implemented it as recursive approach