HackerEarth Interesting Coins problem solution

In this HackerEarth Interesting Coins problem solution, Roy has a number of coins with him that he loves playing with by arranging them in the form of N stacks numbered sequentially. Lucy now gives him a task to make his arrangement of coins even more interesting. The arrangement will be interesting if the number of coins in the stacks are in strictly increasing order.

For this task Lucy gives Roy the option to modify his arrangement by increasing or decreasing the number of coins in each of the stack by atmost C coins. Also the number of coins in a stack should not fall below 1.

Your mission, should you choose to accept it, is to report the minimum C that helps Roy complete the assigned task.

HackerEarth Interesting Coins problem solution.

#include <bits/stdc++.h>

 using namespace std;

 

#define int long long int
#define rep(i,a,b) for(int i=a;i<b;i++)
#define pb push_back
#define F first
#define S second
#define endl "n"
#define FAST ios::sync_with_stdio(0);cin.tie(0);

 

typedef vector<int> vi;
typedef set<int> si;
typedef multiset<int> msi;
typedef map<int,int> mii;
typedef unordered_set<int> usi;
typedef unordered_multiset<int> umsi;
typedef unordered_map<int,int> umii;
typedef pair<int,int> pi;
typedef deque<int,int> di;

 

int is_increasing(int arr[],int n){

   rep(i,1,n){

       if(arr[i]<=arr[i-1])    return 0;

   }

   return 1;

}

int evaluate(int n,int ar[],int k){

   int arr[n];

   rep(i,0,n)  arr[i]=ar[i];

   arr[0]=max(1LL,arr[0]-k);

   rep(i,1,n){

       if(arr[i]>arr[i-1]){

           arr[i]=max(arr[i-1]+1,arr[i]-k);

       }

       else{

           arr[i]=min(arr[i-1]+1,arr[i]+k);

       }

   }

   //rep(i,0,n)  cout<<arr[i]<<" ";

   //cout<<endl;

   if(is_increasing(arr,n))    return 1;

   else    return 0;

}

 

signed main()

{

   FAST
   int t;
   cin>>t;

   while(t--){

       int n,ans;
 
       cin>>n;

       int arr[n];

       rep(i,0,n)  cin>>arr[i];

       int lo=0,hi=1e9;

       while(lo<=hi){

           int mid=(lo+hi)/2;

           int bac=evaluate(n,arr,mid);

           if(bac==1){

               ans=mid;

               hi=mid-1;

           }

           else{

               lo=mid+1;

           }

       }

       cout<<ans<<endl;

   }

}

coding problems solutions