MARRAYS - Editorial

editorial
, , , ,
1

PROBLEM LINK

Practice

Contest

Author: Dmytro Berezin

Tester: Alexey Zayakin

Editorialist: Jakub Safin

DIFFICULTY

EASY-MEDIUM

PREREQUISITIES

dynamic programming

PROBLEM

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.

QUICK EXPLANATION

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).

EXPLANATION

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.

AUTHOR’S AND TESTER’S SOLUTIONS

Setter’s solution

Tester’s solution

Editorialist’s solution

6 Likes
2

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;
3

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<…>>

4

I solved this using segment trees. Nice dp approach.

5

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

2 Likes
6

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

2 Likes
7

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:

8

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

9

test cases weak, naive solution passes

4 Likes
10

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

11

Damn, this editorial is so well written!

1 Like
12

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

13

Here is a video editorial on the problem.
Cheers!

3 Likes
14

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

15

yes you did
#no_offence

16

#include
#include
#include
#include
#include
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.clear();
        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);
                ingd[i].push_back(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