STONEG - Editorial

editorial
, , ,
1

Problem Link

Contest
Practice

Setter: Hritesh Mourya
Tester: Ishika Chowdhury
Editorialist: Hritesh Mourya

DIFFICULTY:

Easy

PREREQUISITES:

Prefix-Suffix

EXPLANATION:

Create a prefix and a suffix cost array such that
prefix[i] = cost of making piles in ascending order from 0^{th} index to i^{th}
suffix[i] = cost of making piles in descending order from i^{th} to end

Now, for peak at index i we can calculate cost as and select the minimum cost,
cost = prefix[i-1] + suffix[i+1] + max(0,max(height_prefix[i-1], height_suffix[i+1]) + 1 -a[i])

where height_prefix[i] denotes height of i^{th} pile when arranged in ascending and height_suffix[i] denotes height of i^{th} pile when arranged in descending

SOLUTION:

Setter's Solution 
#include<bits/stdc++.h>
#define ll long long int
 
using namespace std;
 
int main()
{
    ll T,n,k,i,j;
    cin>>T;
    while(T--)
    {
        cin>>n;
        ll a[n],b[n],h[n];
        for(i=0;i<n;i++){
            cin>>h[i];
            a[i]=b[i]=h[i];
        }
        ll df[n]={0},db[n]={0};
        for(i=1;i<n;i++){
            df[i] = df[i-1] + max(a[i-1]+1-a[i],(ll)0);
            a[i] = max(a[i],a[i-1]+1);
        }
        for(i=n-2;i>=0;i--){
            db[i] = db[i+1] + max(b[i+1]+1-b[i],(ll)0);
            b[i] = max(b[i],b[i+1]+1);
        }
        ll cost,ans = 1e18;
        for(i=1;i<n-1;i++)
        {
            cost = df[i-1] + db[i+1] + max((ll)0,max(a[i],b[i])-h[i]);
            ans = min(ans,cost);
        }
        cout<<ans<<endl;
    }

}

1 Like