PROBLEM LINK:
Setter- Hasan Jaddouh
Tester- Roman Bilyi
Editorialist- Abhishek Pandey
DIFFICULTY:
EASY
PRE-REQUISITES:
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-
- See the intuition on why we should go in direction of Dp.
- 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-
- We perform a swap
- 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 
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.
