DIVIDEARR - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter:Jeevan Jyot Singh
Tester: Abhinav Sharma
Editorialist: Kanhaiya Mohan

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Dynamic Programming

PROBLEM:

Given a sequence X of length M, f(X) is defined as f(X) = \sum_{i = 1}^{M - 1} |X_{i + 1} - X_i|.

JJ has an array A of length N. He wants to divide the array A into two subsequences P and Q (possibly empty) such that the value of f(P) + f(Q) is as large as possible. (Note that each A_i must belong to either subsequence P or subsequence Q).

Help him find this maximum value of f(P) + f(Q).

EXPLANATION:

We follow 1-based array indexing for this solution.

Let dp[i][j] denote the maximum value of f(P) + f(Q) such that:

  • All the elements till index max(i, j) have been divided into subsequence P and Q
  • Subsequence P ends at the i^{th} element and subsequence Q ends at the j^{th} element.

Note that, since the elements at indices i and j lie in different subsequences, i \neq j.

The first element which has not been added to any of the subsequences yet is the element at position k = max(i,j) +1.

While adding the k^{th} element to subsequence P, two cases are possible:

  • i>0: The last element added to subsequence P was the i^{th} element of the array. Thus, on adding the k^{th} element to subsequence P, we add abs(A[k]-A[i]) to f(P). Formally, dp[k][j] = max(dp[k][j], dp[i][j] + abs(A[k]- A[i])).
  • i = 0: This means that no element was added to subsequence P yet. The first element added to subsequence P is the k^{th} element of the array.
    Thus, dp[k][j] = max(dp[k][j], dp[i][j] + 0).

Similarly, if we add the k^{th} element to subsequence Q, two cases are possible:

  • j>0: The last element added to subsequence Q was the j^{th} element of the array. Thus, on adding the k^{th} element to subsequence Q, we add abs(A[k]-A[j]) to f(Q). Formally, dp[i][k] = max(dp[i][k], dp[i][j] + abs(A[k]- A[j])).
  • j = 0: This means that no element was added to subsequence Q yet. The first element added to subsequence Q is the k^{th} element of the array.
    Thus, dp[i][k] = max(dp[i][k], dp[i][j] + 0).

The final answer would be the maximum out of all dp[i][j].

TIME COMPLEXITY:

The time complexity is O(N^2) per test case.

SOLUTION:

Setter's Solution
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define endl "\n"
#define sz(w) (int)(w.size())
using pii = pair<int, int>;
 
const long long INF = 1e18;
 
const int N = 1e6 + 5; 
 
void solve()
{
    int n; cin >> n;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; i++)
        cin >> a[i];       
    vector<vector<int>> dp(n + 1, vector<int>(n + 1));
    int ans = 0;
    for(int i = 0; i <= n; i++)
    {
        for(int j = 0; j <= n; j++)
        {
            ans = max(ans, dp[i][j]);
            int to = max(i, j) + 1;
            if(i == j or to > n) continue;
            dp[to][j] = max(dp[to][j], dp[i][j] + (i == 0 ? 0 : abs(a[to] - a[i])));
            dp[i][to] = max(dp[i][to], dp[i][j] + (j == 0 ? 0 : abs(a[to] - a[j])));
        }
    }
    cout << ans << endl;
}

int32_t main()
{
    ios::sync_with_stdio(0); 
    cin.tie(0);
    int T; cin >> T;
    while(T--)
        solve();
    return 0;
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define db double
#define el "\n"
#define ld long double
#define rep(i,n) for(int i=0;i<n;i++)
#define rev(i,n) for(int i=n;i>=0;i--)
#define rep_a(i,a,n) for(int i=a;i<n;i++)


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T=1;
    cin >> T;
    while(T--){
    
        int n;
        cin>>n;

        int a[n];
        rep(i,n){
            cin>>a[i];
        }

        vector<vector<int> > dp(n+1, vector<int>(n+1,0));
        //dp[i][j] represents maximum ans if the two sequences end at i and j
        int ans = 0;
        rep(i,n+1){
            rep_a(j,i+1,n){
                dp[i][j+1] = max(dp[i][j+1],dp[i][j]+abs(a[j]-a[j-1]));
                dp[j][j+1] = max(dp[j][j+1],dp[i][j]+(i==0?0:abs(a[j]-a[i-1])));
                ans = max(ans, max(dp[i][j+1], dp[j][j+1]));
            }
        }

        cout<<ans<<'\n';
    }
    return 0;
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;

int main() {
	int t;
	cin>>t;
	
	while(t--){
	    int n;
	    cin>>n;
	    
	    int a[n+1];
	    for(int i = 1; i<=n; i++){
	        cin>>a[i];
	    }
	    
	    int ans = 0;
	    int dp[n+1][n+1];
	    memset(dp, 0, sizeof(dp));
	    
	    for(int i = 0; i<=n; i++){
	        for(int j = 0; j<=n; j++){
	            
	            int k = max(i, j) + 1;
	            
	            if(i==j || k>n) continue;
	            
	            if(i==0) dp[k][j] = max(dp[k][j], dp[i][j]);
	            else dp[k][j] = max(dp[k][j], dp[i][j] + abs(a[k]-a[i]));
	            
	            if(j==0) dp[i][k] = max(dp[i][k], dp[i][j]);
	            else dp[i][k] = max(dp[i][k], dp[i][j] + abs(a[k]-a[j]));
	            
	            ans = max({ans, dp[k][j], dp[i][k]});
	        }
	    }
	    cout<<ans<<endl;
	}
	return 0;
}
11 Likes

It was really a wonderful problem and my first dp problem which I solved during contest. Thank you for setting it. Loved it !!

5 Likes

Really a nice Problem.
Here is my recursive solution for optimized space complexity.

Suppose p1 and p2 (where p1 \neq p2) are the last index which are included in sequence 1 and sequence 2 respectively .

Now, We want to include i th index of array a (0 <= i <= N-1).
So, we have two choices: either append in seq1 or seq2.
Including it in seq1 => p1' = i and p2' = p2
Including it in seq2 => p1' = p1 and p2' = i

So, recursive formula is
F(p1,p2,i) = max(abs(a[i]-a[p1]) + F(i,p2,i+1), abs(a[i]-a[p2]) + F(p1,i,i+1)

Now, If we closely look at the above recursive formula then one of the p1 or p2 is will always index-1, where index is the index for which we are taking decision.
Logically it says that, index-1 will be included either in seq1 or seq2.

Now, since one of the index can be driven from other two values we can safely neglect that index.

So, Let’s revise above recursive formula.

if last index (i-1) was in seq1, means p1 = i-1.
So, F(i-1,p2,i) = max(abs(a[i]-a[i-1]) + F(i, p2, i+1), abs(a[i]-a[p2]) + F(i-1,i,i+1)

Similarly, If last index (i-1) was in seq2, means p2 = i-1.
So, F(p1,i-1,i) = max(abs(a[i]-a[p1]) + F(i,i-1,i+1), abs(a[i]-a[i-1]) + F(p1,i,i+1)

Wherever we are neglecting index, we put -1 there, which shows irrelavant.
So,
F(-1,p2,i) = max(abs(a[i]-a[i-1]) + F(-1, p2, i+1), abs(a[i]-a[p2]) + F(i-1,-1,i+1)
and
F(p1,-1,i) = max(abs(a[i]-a[p1]) + F(-1,i-1,i+1), abs(a[i]-a[i-1]) + F(p1,-1,i+1)

Now, recusrion formula converted into two variables

  1. either p1 or p2
  2. i

Now, if we look at the revised recursive formula, i just acting like running variable and the decision only depends on choices of p1 and p2.

So, we can maintain two different dp, dp1 and dp2, where dp1[p1] = F(p1, -1) and dp2[p2] = F(-1, p2).

So, Here is the implementation in c++.

Since recursive formula is designed such that we must include at least one index in both the sequences. So, problem splits in two cases.

  1. All number are in one sequence.
  2. Include prefix of length l (1 <= l <= n-1) in first sequence and including l+1 th element in second sequence.
#include<bits/stdc++.h>

using namespace std;

int util(vector<int> &a, int p1, int p2, int i, vector<int> &dp1, vector<int> &dp2){
    if(i == a.size()) return 0;
    if(p1 == -1){
        if(dp2[p2] != -1) return dp2[p2];
        return dp2[p2] = max(abs(a[i]-a[i-1])+util(a,-1,p2,i+1,dp1,dp2), abs(a[i]-a[p2])+util(a,i-1,-1,i+1,dp1,dp2));
    }
    else{
        if(dp1[p1] != -1) return dp1[p1];
        return dp1[p1] = max(abs(a[i]-a[p1])+util(a,-1,i-1,i+1,dp1,dp2), abs(a[i]-a[i-1])+util(a,p1,-1,i+1,dp1,dp2));
    }
}


int main(){
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        vector<int> a(n);
        for(int i = 0; i < n; i++) cin >> a[i];
        int ans = 0;
        vector<int> dp1(n,-1), dp2(n,-1);
        for(int i = 1; i < n; i++)
            ans += abs(a[i]-a[i-1]);
        int sum = 0;
        for(int l = 0; l+2 <= n; l++){
            ans = max(ans, sum+util(a,l,-1,l+2, dp1, dp2));
            sum += abs(a[l+1]-a[l]);
        }
        cout << ans << "\n";
    }
    return 0;
}

Time Complexity : O(N^2)
Space Complexity: O(N)

9 Likes

Hey there !! I tried this problem using memoization but got WA. Here is my code :

#include<bits/stdc++.h> 
#define ll long long
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
using namespace std;
ll dp[1005][1005];
ll find_optimal_ans(vector<ll> &a, ll last_a1 = -1, ll last_b1= -1,ll a1 = 0, ll b1 = 0, ll i = 0,ll last_picked_i = 0, ll last_picked_j = 0){
    if(dp[last_picked_i][last_picked_j] != -1) return dp[last_picked_i][last_picked_j];
    if(i == a.size()) return a1 + b1;
    ll ans1 ,ans2;
    if(last_a1 == -1){
        ans1 = find_optimal_ans(a,a[i],last_b1, a1,b1, i + 1,i + 1,last_picked_j);
    }
    else ans1 = find_optimal_ans(a,a[i],last_b1, a1 + abs(last_a1 - a[i]),b1, i + 1,i + 1, last_picked_j);
    if(last_b1 == -1){
        ans2 = find_optimal_ans(a,last_a1,a[i], a1 ,b1, i + 1,last_picked_i, i + 1);
    }else ans2 = find_optimal_ans(a,last_a1,a[i], a1 ,b1+ abs(last_b1 - a[i]), i + 1,last_picked_i, i + 1);

    return dp[last_picked_i][last_picked_j] = max(ans1, ans2);
    

}
void solve()
{
    int t, n;
    cin >> t;
    while(t--){
        memset(dp, -1, sizeof dp);
        cin >> n;
        vector<ll> x(n);
        for(auto &elem : x) cin >> elem;
        cout<<find_optimal_ans(x)<<"\n";
    }
}
int main()
{
ios_base::sync_with_stdio(false);
cout.tie(NULL);
cin.tie(NULL);
solve();
return 0;
}

Can anyone pls find the mistake in this code?

I want to ask about the sample test case 2 that was given in the problem :

Sample Test case 2 :
5
1 2 3 4 5

According to them the max output is

Output :
6

The combination they have taken is this:
P=[1,4]
Q=[2,3,5]

But if we take a combination like
P=[3,1,5]
Q=[2,4]
Then the max output would have been

Output:
8

please tell me if i am wrong???

Subsequence has to be contiguous or ordered. P=[3, 1, 5] is not ordered (In given input, 1 comes before 3)

2 Likes

Nice Solution! Really well explained! :slight_smile:

3 1 5 is not contiguous, it is not a subsequence.

1 Like

Thanks bro

thanks i got it

Since each element must be inserted into one list, we could separate the two lists as:
P: contains the last element,
Q: does not contain the last element.
dp[i][j] means that, after inserting element i, maximum of f(P) + f(Q) when Q’s last element is jth element.
dp transition is:
dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + abs(A[i + 1] - A[i])). when append A[i +1] to P.
dp[i + 1][i] = max(dp[i + 1][i], dp[i][j] + abs(A[i + 1] - A[j])), for j in 0 to i - 1. when append A[i + 1] to Q, then swap P and Q.
Final answer is maximum among dp[N][j]. Time complexity is still O(N^2) but I think it is easier to understand.

Beautifully explained !! Thank you !

Could someone please provide the testcases? I am trying a different approach than the one’s discussed here and getting a lot of WA’s :sweat_smile:

input file
output file

1 Like