SOPC011 Editorial

PROBLEM LINK:

Practice
Contest

Author: Aniswar Srivatsa Krishnan
Editorialist: Shriram Chandran

DIFFICULTY:

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][2];
    for(ll i=0;i<n;i++)
        dp[i][0]=dp[i][1]=-1e18;
    dp[0][0]=a[0];
    dp[0][1]=-1;
    dp[1][0]=a[0]+a[1];
    if(a[1]*a[0]>dp[1][0])
    {
        dp[1][0]=a[1]*a[0];
        dp[1][1]=-1;
    }
    else dp[1][1]=0;
    for(ll i=2;i<n;i++)
    {
        dp[i][0]=dp[i-1][0]+a[i];
        if(dp[i-2][0]+a[i]*a[i-1]>=dp[i][0])
        {
            dp[i][0]=dp[i-2][0]+a[i]*a[i-1];
            dp[i][1]=i-2;
        }
        else dp[i][1]=i-1;
    }
    vector<pair<ll,ll>> ans;
    ll i=n-1;
    while(i!=-1)
    {
        if(dp[i][1]==i-2)
            ans.push_back(make_pair(i,i+1));
        i=dp[i][1];
    }
    cout<<dp[n-1][0]<<" "<<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;
}