what if there 3 front and 3 backward would have been given
Pikachu and Stones -
Dp -
Maintain the number of stones till current index. Maintain the highest stone.
Do it once up to down. Do it once down to up.
if The highest stones mismatch. choose the once till the given range with highest and the one from other.
Create a prefix max and suffix max array and notice that any valid peak would have some prefix from the prefix max array rest of the suffix from the suffix max array. So for any index j to be the peak we’ll have to add \displaystyle \sum_{i=0}^{j-1}(P_i-A_i)+\displaystyle \sum_{i=j+1}^N(S_i-A_i)+\max(P_j,S_j)-A_j and this could be easily calculate by prefix & suffix sums .
CODE
#include "bits/stdc++.h"
#define int long long
using namespace std ;
void solve(){
int ans=1e10,c=0,d=0,n ;
cin >> n ;
vector<int>a(n),p(n),s(n) ;
for(int &x:a)
cin >> x ;
p[0]=a[0] ;
for(int i=1;i<n;i++)
p[i]=max(p[i-1]+1,a[i]) ;
s[n-1]=a[n-1] ;
for(int i=n-2;~i;--i){
s[i]=max(s[i+1]+1,a[i]) ;
c+=s[i]-a[i] ;
}
c-=s[0]-a[0] ;
d+=p[0]-a[0] ;
for(int i=1;i<n-1;i++){
c-=s[i]-a[i] ;
ans=min(ans,c+d+max(p[i],s[i])-a[i]) ;
d+=p[i]-a[i] ;
}
cout << ans << '\n' ;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int TC ;
cin >>TC ;
while(TC--)
solve() ;
}
2 Likes
55 is the upper limit. You are using 50.
hoooo, my bad
Is this approach correct?
Can you suggest test case on which it will not work?
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define rep(i,n) for (ll i = 0; i < n; i++)
#define ysno(ok) if(ok){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define testloop ll t;cin>>t;while(t--)
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
testloop{
ll n;
cin>>n;
ll a[n];
ll dp2[n]; dp2[n] = -100;ll dp1[n+1]; dp1[0] = -100;
rep(i,n){cin>>a[i];dp1[i+1] = a[i]; dp2[i+1] = a[i];}
rep(i,n){
dp1[i+1] = max(dp1[i]+1,dp1[i+1]);
}
for(int i = n-1;i >=0;i--){
dp2[i] = max(dp2[i+1]+1,dp2[i]);
}
rep(i,n+1){
dp1[i] = max(dp1[i],dp2[i]);
}
ll mini = 1e18;
ll r = 0;
for(int i = 1 ; i < n-1;i++){
if(dp1[i+1] < mini){mini = dp1[i+1];r = i;}
}
ll ans = mini -a[r];
a[r] = mini;
ll x = mini;
for(int i =1;i < r ;i++){
ll y = max(a[i-1]+1,a[i]);
ans += abs(a[i] - y);
a[i] = y;
}
for(int i =n-2;i >r ;i--){
ll y = max(a[i+1]+1,a[i]);
ans += abs(a[i] - y);
a[i] = y;
}
rep(i,n){cout<<a[i]<<" ";}
cout<<endl;
cout<<ans<<endl;
}
}
Paste full code or share a link It won’t compile in my compiler.
I knew the solution but thought dinic works in O(N^3) so never implemented 
. Forgot that its a unit graph.
3 Likes
Is this working for the samples ? I’m getting 14 14
Dude 
this isn’t passing the samples either
This is not working for increasing sequence , what should i change in binary search ?
Fails for
1
6
3 3 1 7 6 10
Correct output is 10 your code gives 7
No it is give correct answer on codehef compiler
Can anyone share the approach for jiggly puff ?? I tried greedy but got wa
That code was a little messed up, ignore it.
Yeah i thought of ford fulkerson but thought it might give tle
is binary search wrong approach ?