 # SOPC011 Editorial

Author: Aniswar Srivatsa Krishnan
Editorialist: Shriram Chandran

Medium

# PREREQUISITES:

Dynamic Programming, basic BFS/path traversal.

# PROBLEM:

Given an array, find the maximum sum possible by optimally clubbing few adjacent elements and replacing them by their product.

# EXPLANATION:

Let us do a simple dp and also keep a separate parent array p.

Initially, dp_1=a_1 and p_1=0.

dp_2=max(a_1+a_2,a_1*a_2). if(dp_2=a_1*a_2), p_2=0, otherwise p_2=1.

Now for the general case, the transitions are clear: if dp_{i-1}+a_i > dp_{i-2} + a_{i-1}*a_i, then dp_i = dp_{i-1}+a_i and p_i = i-1. Otherwise, dp_i = dp_{i-2} + a_{i-1}*a_i and p_i = i-2.

Now, the optimal value is obtained in dp_n.

How do we obtain the set of pairs of missiles to be fused?

This is where the p array becomes useful. Start from n, and keep traversing the p array using i=p_i. Whenever p_i = i-2, the elements a_i and a_{i-1} were fused in the optimal answer. Store all such i and output the pairs correspondingly.

Note that multiple answers are possible due to equality conditions. All the optimal correct answers are awarded AC verdict.

# SOLUTION:

Setter's Solution
``````#include<bits/stdc++.h>
#define ll long long
#define max(a,b) ((a>b)?a:b)

using namespace std;

void solve()
{
ll n;
cin>>n;
ll a[n];
for(ll i=0;i<n;i++)
cin>>a[i];
ll dp[n];
for(ll i=0;i<n;i++)
dp[i]=dp[i]=-1e18;
dp=a;
dp=-1;
dp=a+a;
if(a*a>dp)
{
dp=a*a;
dp=-1;
}
else dp=0;
for(ll i=2;i<n;i++)
{
dp[i]=dp[i-1]+a[i];
if(dp[i-2]+a[i]*a[i-1]>=dp[i])
{
dp[i]=dp[i-2]+a[i]*a[i-1];
dp[i]=i-2;
}
else dp[i]=i-1;
}
vector<pair<ll,ll>> ans;
ll i=n-1;
while(i!=-1)
{
if(dp[i]==i-2)
ans.push_back(make_pair(i,i+1));
i=dp[i];
}
cout<<dp[n-1]<<" "<<n-ans.size()<<endl;
cout<<ans.size()<<endl;
for(auto i:ans)
cout<<i.first<<" "<<i.second<<endl;
}

int main()
{
int t;
cin>>t;
while(t--)
solve();
return 0;
}
``````