SFRV - Editorial

PROBLEM LINK:

Div1
Div2
Practice

Setter- Hasan Jaddouh
Tester- Roman Bilyi
Editorialist- Abhishek Pandey

DIFFICULTY:

EASY

PRE-REQUISITES:

Dynamic Programming

PROBLEM:

Given an array A of N integers, you are allowed the following operation any number of times - Swap any 2 adjacent elements. However, each element can be swapped at most once. Given this, maximize \sum_{i=1}^{i=N}A_i*i.

QUICK-EXPLANATION:

Key to AC- You only have to swap adjacent elements, and hence the dynamic programming recurrence is very simple. Think in terms of if its optimal to swap A_i with its preceding element, or not.

Let Dp[i] store the answer for the sub-array from [1,i], in a 1-based indexing. The final answer will hence be stored in Dp[N].

Dp[0]=0 because there is no element (or alternatively, because i=0. Dp[1]=A[1] as there is only 1 element. We can easily see the recurrence relation as-

Dp[i]=max(Dp[i-1]+A[i]*i , Dp[i-2]+i*A[i-1] +(i-1)*A[i])

EXPLANATION:

Since this is one of the basic Dp problems, we will have the following plan for the editorial-

  1. See the intuition on why we should go in direction of Dp.
  2. How to concrete your intuition and hence derive the recurrence.

1. How to get the intuition that it is Dp-

The first sign of a Dp question is that, either greedy fails, or its solution looks as if greedy needs loooots of conditions to pass!

One approach of greedy for this question, which might have struck your mind, would be that “For each i, check both its adjacent elements and swap with the one giving more contribution to the sum.”

So lets say that you start from i=1 and go till i=N. You will fail at this case of A[]=\{105,100,110,1\}. At i=2 (1-based indexing), you will feel that its best to swap (100,110). But when you Aive at i=3, you see a more optimum move was possible, which we cannot use now! Hence, there comes a need to “backtrack” our previous wrong choices and correct them! This, is a very, very sure sign of dp!!

Some other things being, there is no 1 single rule/construction which on applying to any array, would optimize the required value. Another good sign is dependency of the value on previous choices. There are multiple such hints - but lets keep that for some later day (or editorial!). the chief and the most important one which I wanted to highlight was the need to backtrack, and that of greedy failing in all forms!

2. Concrete your intuition and derive the recurrence-

To reach the final Dp, we need to first think of the brute force! Brute force will be, checking all combination of swaps and printing the maximum value obtained using the resulting arrays. Too slow, however!

What is an optimal swapping, anyway? For ease of discussion, lets say our original answer has an initial value of S=\sum_{i=1}^{i=N}A_i*i obtained by the original array. And we will update it only if we find a higher value (this takes care of the case when no swapping is required).

Now, focus on any index i in the array. Its always helpful to first derive the general recurrence, and then worry about the corner cases - hence don’t take an extreme i like i=1 or i=N. Take an i in middle of array.

Now, at this i , in our optimal solution, there are 2 possibilities-

  1. We perform a swap
  2. We don’t perform a swap

Greatest forbidden ancient knowledge the Mr Editorialist just wrote above?

Now, think on these lines-

If I do a swap between elements of index i and index (i-1) , then what happens? What is the value of S then? Read carefully on what I have to argue-

"If, I am considering only the sub-array from range [1,i] - then, on swapping, the value of S will be as-

S=Optimal \ swapping \ of \ elements \ in \ range \ [1,i-2] + contribution \ of \ elements \ at \ index \ i \ and \ (i-1)

Trying to go a little mathematically now-

Assume I am storing the answer, i.e. optimal value of S in an array Dp[] , where Dp[i] stores the answer for sub-array in range [1,i]. Obviously, Dp[0]=0 and Dp[1]=A[1]. This is the base case, which we mentioned in the Quick Explanation.

Now, writing our formula in terms of Dp[]-

Dp[i]= Dp[i-2] + A[i] *(i-1) + A[i-1] * i

This is only if the swap is optimal, i.e. if we choose to swap. What if we do not chose to swap? Can you work it out a little?

When we do not chose to Swap

In this case, the answer is Optimal swapping for elements in range [1,i-1]+ The contribution of element at i. Meaning-

Dp[i] = dp[i - 1] + i * A[i]

Ultimately, whether we have to swap or not depends on it it increases S or not. Hence, for the subarray in range [1.i], we calculate Dp[i] by taking max of the 2 cases-

Dp[i] = max(Dp[i - 1] + i * A[i], Dp[i - 2] + i * A[i - 1] + (i - 1) * A[i])

Our final answer, i.e. maximum value of S, is stored in Dp[N]

SOLUTION

Setter
#include <iostream>
#include <algorithm>
#include <string>
#include <assert.h>
using namespace std;
 
 
 
long long readInt(long long l,long long r,char endd){
	long long x=0;
	int cnt=0;
	int fi=-1;
	bool is_neg=false;
	while(true){
		char g=getchar();
		if(g=='-'){
			assert(fi==-1);
			is_neg=true;
			continue;
		}
		if('0'<=g && g<='9'){
			x*=10;
			x+=g-'0';
			if(cnt==0){
				fi=g-'0';
			}
			cnt++;
			assert(fi!=0 || cnt==1);
			assert(fi!=0 || is_neg==false);
			
			assert(!(cnt>19 || ( cnt==19 && fi>1) ));
		} else if(g==endd){
			assert(cnt>0);
			if(is_neg){
				x= -x;
			}
			assert(l<=x && x<=r);
			return x;
		} else {
			assert(false);
		}
	}
}
string readString(int l,int r,char endd){
	string ret="";
	int cnt=0;
	while(true){
		char g=getchar();
		assert(g!=-1);
		if(g==endd){
			break;
		}
		cnt++;
		ret+=g;
	}
	assert(l<=cnt && cnt<=r);
	return ret;
}
long long readIntSp(long long l,long long r){
	return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
	return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
	return readString(l,r,'\n');
}
string readStringSp(int l,int r){
	return readString(l,r,' ');
}
 
int T;
int n;
int sm_n=0;
long long dp[100100];
long long A[100100];
 
 
int main(){
	//freopen("02.txt","r",stdin);
	//freopen("02o.txt","w",stdout);
	T=readIntLn(1,1000);
	while(T--){
		n=readIntLn(1,100000);
		sm_n += n;
		assert(sm_n<=1000000);
		for(int i=1;i<=n;i++){
			if(i==n){
				A[i]=readIntLn(1,1000000000);
			} else {
				A[i]=readIntSp(1,1000000000);
			}
		}
		dp[0]=0;
		dp[1]=A[1];
		for(int i=2;i<=n;i++){
			dp[i] = dp[i-1] + A[i] * i;
			dp[i] = max(dp[i],dp[i-2] + A[i] *(i-1) + A[i-1] * i);
		}
		cout<<dp[n]<<endl;
	}
	assert(getchar()==-1);
} 
Tester
#include "bits/stdc++.h"

using namespace std;
 
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define RFOR(i,b,a) for (int i = (b) - 1; i >= (a); i--)
#define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a,value) memset(a, value, sizeof(a))
 
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
 
typedef long long Int;
typedef vector<int> VI;
typedef pair<int, int> PII;
 
const double PI = acos(-1.0);
const int INF = 1000 * 1000 * 1000;
const Int LINF = INF * (Int) INF;
const int MAX = 100007; 
 
const int MOD = 998244353;
 
long long readInt(long long l,long long r,char endd){
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true){
        char g=getchar();
        if(g=='-'){
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g && g<='9'){
            x*=10;
            x+=g-'0';
            if(cnt==0){
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);
           
            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd){
            assert(cnt>0);
            if(is_neg){
                x= -x;
            }
            assert(l<=x && x<=r);
            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l,int r,char endd){
    string ret="";
    int cnt=0;
    while(true){
        char g=getchar();
        assert(g!=-1);
        if(g==endd){
            break;
        }
        cnt++;
        ret+=g;
    }
    assert(l<=cnt && cnt<=r);
    return ret;
}
long long readIntSp(long long l,long long r){
    return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
    return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
    return readString(l,r,'\n');
}
string readStringSp(int l,int r){
    return readString(l,r,' ');
}
void assertEof(){
    assert(getchar()==-1);
}
 
Int dp[MAX];
 
int main(int argc, char* argv[])
{
	// freopen("in.txt", "r", stdin);
	//ios::sync_with_stdio(false); cin.tie(0);
    
    int t = readIntLn(1, 1000);
    int sn = 0;
    FOR(tt,0,t)
    {
        int n = readIntLn(1, 100000);
        VI A(n);
        FOR(i,0,n)
        {
            A[i] = readInt(1, INF, (i + 1 < n ? ' ' : '\n'));
        }
        FILL(dp, 0);
        dp[0] = 0;
        FOR(i,0,n)
        {
            dp[i + 1] = max(dp[i + 1], (Int)(i + 1) * A[i] + dp[i]);
            if (i + 1 < n)
                dp[i + 2] = max(dp[i + 2], dp[i] + (Int)(i + 1) * A[i + 1] + (Int)(i + 2) * A[i]);
        }
        cout << dp[n] << endl;
    }
    assert(sn <= 1000000);
    assertEof();
 
    cerr << 1.0 * clock() / CLOCKS_PER_SEC << endl;
    
}  

Time Complexity=O(N)
Space Complexity=O(N)

CHEF VIJJU’S CORNER :smiley:

1.Explore how we handled base cases here. Instead of making base cases as Dp[1] and Dp[2] (which is a little tricky because you need to manually check if for Dp[2] we need to swap or not), we simply used trivial cases of Dp[0] and Dp[1]. Remember that proper definition of “what” is your base case can often make life easier and save some debugging!

2.If you are just starting Dynamic programming, then start with some easier problems. Sharpen your skills to get the intuition of the problem, and solidify it into the recurrence. Don’t code it just yet! Look at how your recurrence unfolds for some values of i, and use that to support or counter its correctness. Only look at solution and answer recurrence once you have spent ~1hr on it - and if you do look at the answer, don’t solve it. Keep it in your to-do list and again re-attempt after a week. Because once you do it after some time, you’d have forgotten enough details of the solution that you’d have to re-derive it - and hence you will know if you are actually learning and understanding the answer or not!

3.Prove or disprove each of the following, with a valid reason-
a. The following dp recurrence relation is correct-

 dp[i] = dp[i-1] + A[i] * i;
 if(A[i]>A[i-1])
    dp[i] = max(dp[i],dp[i-2] + A[i] *(i-1) + A[i-1] * i);

b. The following dp recurrence is slow, but correct-

ans[1] = A[1];//1 based indexing
for all i from 2 to N
    ans[i] = ans[i-1] + i*A[j]; // The sum when we are not swapping anything.
    for all j from 1 to i-1
        ans[i]=max(ans[i],ans[i-1]+A[j]*(i-j)-A[i]*(i-j) );
        //Optimal answer upto index i-1 + What if we swap indices (i,j).

c. We do not need to handle the case of “No swaps needed at all” as it is taken care of in the recurrence itself.

Related Questions
  1. Count Subarrays
  2. Chef and Frogs
  3. Subtree Removal
  4. Alternating array
32 Likes

Great explanation.
[To overcome character limits]

1 Like

Why do we not have to worry about the case when the previous element has already been swapped and can also give an even higher sum when swapped with the current element. In that case the previous element would be swapped twice and hence violate the requirement?

1 Like

No, it wouldn’t be swapped twice because we are considering both dp[i-1] and dp[i-2] to find dp[i].

https://www.codechef.com/viewsolution/25462258

Can anyone tell why the above solution gives WA? It gives correct answer if I change int arr to long long int arr. Does it mean that the input size is greater than 10^9?

Very Nice Editorial!

1 Like

Bro you have not initialised you dp[] array because of which, maybe it is taking garbage value / no value at all (I haven’t debugged it cause it seemed to be an obvious error)at some point of time.

Just add this line after you declaration of ll dp[n+1]:

-> memset(dp,0,sizeof(dp));

it’ll work fine then! :+1:

EDIT: It seems there are more errors. In addition to initialising the values of dp to 0, do the following:

1.> Change every data type to long long int, including array a[] and T and n.
2.> tie you output and make i/o faster by writing faster in your code (as per your definition) while it most probably haven’t contributed to WA it does make your program faster…

I did these two things and you code passed the test cases!

1 Like
  1. Arr[i] \leq 10^9
  2. 1 \leq i \leq 10^5

\implies i*Arr[i] \approx 10^{14}. Overflow perhaps?

For that case, what is our recurrence?

Our recurrence is -

Ans= Optimal \ Swapping \ of \ elements \ in \ range \ [1,i-2]+....

Optimal swapping is in range [1,i-2], which means all swaps happen only in subarray [1,i-2]. Alternate interpretation is that, in this optimal swaps, only elements in range [1,i-2] are considered - which guarantees that (i-1) and i arent swapped.

1 Like

Thanks for trying. Memset is not required as it dp[i] doesn’t depend on current value of dp[i] and the first 2 values of dp are initialized.

Yeah! I wanted to know why it passes all testcases when ‘int arr’ is changed to ‘ll arr’ since I am not changing anything in arr which can cause it to overflow.

See the following AC solution
https://www.codechef.com/viewsolution/25462417

Yeah! But I am not storing i*Arr[i] in Arr which can cause overflow otherwise!!

could someone give a testcase for which my solution is giving WA.
https://www.codechef.com/viewsolution/25456773

Very good question. But from what I understand, once you multiply i and a[i] you need not store the value into the array… like (10^5 * 10^9) will be 10^14) and will overflow int cannot handle it. So you must have a ll data type so that the intermediate result can be initialised to, and it must need to be either i or a[]… one of them has to be of ll type… if you’ll change int i to ll i , this should do as well.

But as in the case of changing a[] -> ll a[] … I am not clear about the exact reason , maybe someone can enlighten us!

Help Please!

why am I getting a wrong answer if I change

dp[i]=max((dp[i-1]+a[i] * i ),dp[i-2]+a[i-1] * i + a[i] * (i-1))

to

dp[i]=max((dp[i-2]+a[i] * i +a[i-1] * (i-1)),dp[i-2]+a[i-1] * i + a[i] * (i-1))

I am thinking that if I don’t swap then I could simply add a[i] * i +a[i-1] * (i-1) instead of a[i-1] * i + a[i] * (i-1) to the dp. Is this thing wrong?

You are right!! I changed int i to ll i and it worked. I think that was the problem. Either we should change int arr or int i to ll.

AC : https://www.codechef.com/viewsolution/25478454

It is wrong because you are not considering the case where the previous 2 elements have been swapped( i-1 and i-2 ). You are forcing the elements not to get swapped. This way you will get lesser score than expected

arr[i]*(i-1)

This part in line 72 overflows. If both operands of * are int, then their intermediate result is also stored in int.

Thanks! I got it.
:slight_smile:

Yeah! I got it. Thanks. Henceforth, I should be careful about datatypes.

1 Like

yes, take long long int:)