 # DYNMCPRG-EDITORIAL

https://www.codechef.com/CLAG2020/problems/DYNMCPRG

Translator:https://www.codechef.com/users/dhussa_09

Editorialist:https://www.codechef.com/users/dhussa_09

DIFFICULTY:
EASY-MEDIUM

** PREREQUISITES:**
DYNAMIC PROGRAMMING

PROBLEM:

The chef has n arrays each array has an m number of elements. For each array given, You have to find the maximum sum of a subsequence with the constraint that no two numbers in the sequence should be adjacent to each other in the array and store it in the new array which will be of the size n. Now, you have a single new array of size n. From that find the minimum sum of a subsequence by using the maximum number of elements in an array with the constraint that no two numbers in the sequence should be adjacent to each other in the array and print it.

EXPLANATION:

Algorithm:
Loop for all elements in arr[] and maintain two sums incl and excl where incl = Max sum including the previous element and excl = Max sum excluding the previous element.
Max sum excluding the current element will be max(incl, excl) and max sum including the current element will be excl + current element (Note that only excl is considered because elements cannot be adjacent).

At the end of the loop return max of incl and excl.

Example:

arr[] = {5, 5, 10, 40, 50, 35}

incl = 5
excl = 0

For i = 1 (current element is 5)
incl = (excl + arr[i]) = 5
excl = max(5, 0) = 5

For i = 2 (current element is 10)
incl = (excl + arr[i]) = 15
excl = max(5, 5) = 5

For i = 3 (current element is 40)
incl = (excl + arr[i]) = 45
excl = max(5, 15) = 15

For i = 4 (current element is 50)
incl = (excl + arr[i]) = 65
excl = max(45, 15) = 45

For i = 5 (current element is 35)
incl = (excl + arr[i]) = 80
excl = max(65, 45) = 65

And 35 is the last element. So, answer is max(incl, excl) = 80
DO IT FOR ALL n ARRAYS WITH ELEMENTS m.
finally, you will get an array of size n.
after this, you have to find the minimum sum of a subsequence by using the maximum number of elements in an array with the constraint that no two numbers in the sequence should be adjacent to each other in the array and print it.

Its very simple use of basic maths for this condition.
As, 1<=n<=4.we have 3 condtiions.
As we have print minimum sum by taking maximum elements which eliminate adjacent element.

1]if(x == 4)
{
//eg- if new array created of size n has elements [1,8,9,2],result=3.
//print minimum sum by taking maximum elements which eliminate adjacent element.
//here they will eliminate 8 and 9.AS 8 is adjacent to 1 and 9 is adjacent to 2.
result = min(ans + ans, result);
result = min(ans + ans, result);
result = min(ans + ans, result);
}
2] else if(x == 3)
{
//eg- if new array created of size n has elements [5,4,8],result=4.
// print minimum sum by taking maximum elements which eliminate adjacent element.
result = min(result, ans + ans);
result = min(result, ans);
}
3] else if(x == 2)
{
//eg- if new array created of size n has elements [55,109],result=55.
result = min(ans, ans);
}
4] else
{
//eg- if new array created of size n has elements ,result=8.
result = ans;
}

The solution in c++14 language:

#include<bits/stdc++.h>
using namespace std;

#define ll long long

ll cal(vector &a)
{
int n = a.size();
vector dp(n, 0);
dp = a;
dp = max(a, a);
for(int i = 3; i<n; ++i)
{
dp[i] = max(dp[i-1], dp[i-2] + a[i]);
}
return dp[n - 1];

}
int main()
{

int t;cin>>t;
while(t–){
int n, m; cin>>n>>m;
vector ans; ans.push_back(0);
int x = n;
while(n–){
vector a(m + 1, 0);
for(int i=1; i<=m;++i) cin>>a[i];
if(m == 1)
{
ans.push_back(a);
continue;
}
else ans.push_back(cal(a));
}
ll result = INT_MAX;
if(x == 4)
{
// 1,4 1,3 2,4
result = min(ans + ans, result);
result = min(ans + ans, result);
result = min(ans + ans, result);
}
else if(x == 3)
{
//1,3 2
result = min(result, ans + ans);
result = min(result, ans);
}
else if(x == 2)
{
result = min(ans, ans);
}
else
{
result = ans;
}
cout<<result<<endl;
}
// cerr << "\nTime elapsed: "<< 1000 * clock() / CLOCKS_PER_SEC << “ms\n”;
return 0;
}

The last part of finding min sum from array size n is incorrect.
First of all you say that the array sum should be minimum but then you say that it should contain maximum number of elements.
To which statement should I give priority.
Let final array of size n is arr[]= { 5, 4, 5}
If minimum sum is the priority then 4 is the answer but it contains only 1 element whereas if I choose 5+5 as the answer then, this contains the maximum number of elements = 2 but does not have minimum sum. You should have confined to only one statement.
You can reframe this by saying that find the Minimum sum subsequence such that at least one of every 2 consecutive elements is picked or better give priority to the maximum number of elements.

you have not read the word alternate…
sum should be minimum by considering maximum elements…
we are considering middle element by eleminating 1sT and last