BITCOIN - Editorial

PROBLEM LINK:

CHEF AND CRYPTO

Author: mugdha273

Tester: agarwal_keshav

Editorialist: mugdha273

DIFFICULTY:

HARD

Prerequisites:

  • knowledge of Dynamic Programming.

  • Familarity with pre-computation.

EXPLANATION:

Well for this question, the code itself is the best explanation if you pick some elements and dry run it. Still let’s see the intuition behind the solution. But before that, take a pen-paper with you for better understanding! Now we are asked to make the distribution more uniform, which basically means change the elements in using one of the two operations, a_i+a_{i-1} or a_{i}+a_{i+1} such that the final distribution becomes non decreasing. One thing to note that after each operation, the array will not remain the same, for example, if there is an array like 8 5 9 7 4, then to make it uniform, in the first step, we’ll add 5 and 9, so the array will change to 8 14 7 4, again we’ll add 14 and 7 so the array will change to 8 21 4, again we’ll add 21 and 4 so the array will change to 8 25. This makes it quite evident you need to use dynamic programming, else time complexity will be huge.

Let’s introduce two arrays ans[] for storing elements after performing operations on them and dp[] for storing number of changes performed till any particular point, of size 1001 (Why 1001? look at the constraints). Now iterate over the loop and simply see if at any place arr[i]< ans[i - 1]. If yes then then use a variable j and decrement it till you reach the condition ans[i] + arr[j] < ans[j - 1] and perform operations each time, ans[i] += arr[j]; j–; where you add elements till you reach the required condition also, store the number of changes into dp[], dp[i] = dp[j - 1] + (i - j);

If not then simply store

                dp[i] = dp[i - 1];

                ans[i] = arr[i];

So our final answer will be, dp[n] which shows number of changes done to make the array uniform.

Time complexity: O(N^2).

SOLUTIONS:

Setter's Solution

#include <bits/stdc++.h>

#define rep(i, a, b) for (int i = a; i < b; i++)

#define f(i, n) for (int i = 0; i < n; i++)

#define repr(i, a, b) for (int i = a; i >= b; i--)

#define M 1000000007

#define all(arr) (arr).begin(), (arr).end()

#define pb push_back

#define ll long long int

#define sz 1001

using namespace std;

int arr[sz];

int ans[sz];

int dp[sz];

int main()

{

   ios_base::sync_with_stdio(false);

   cin.tie(NULL);

   // freopen("@input.txt", "r", stdin);

   // freopen("@output.txt", "w", stdout);

   int T;

   cin >> T;

   while (T--)

   {

       ll n;

       cin >> n;

       for (ll i = 1; i <= n; i++)

           cin >> arr[i];

       dp[0] = 0;

       ans[0] = 0;

       dp[1] = 0;

       ans[1] = arr[1];

       for (ll i = 2; i <= n; i++)

       {

           if (arr[i] >= ans[i - 1])

           {

               dp[i] = dp[i - 1];

               ans[i] = arr[i];

           }

           else

           {

               ll j = i;

               ans[i] = 0;

               while (j > 0 && (ans[i] + arr[j] < ans[j - 1]))

               {

                   ans[i] += arr[j];

                   j--;

               }

               ans[i] += arr[j];

               dp[i] = dp[j - 1] + (i - j);

           }

       }

       cout << dp[n] << "\n";

   }

   return 0;

}

Tester's Solution

// Keshav Agarwal, Codechef_handle = agarwal_keshav; codeforces_handle = agarwal_keshav

#include <bits/stdc++.h>

using namespace std;

#define ll long long int

#define nl cout<<"\n";

#define fix(f,n) cout<<fixed<<setprecision(n)<<f

const int mod = 1e9+7;

template<typename ...T>

void debug(T&&... args){ ((cerr << args << " "), ...);cerr<<"\n";}

ll gcd(ll a,ll b){ return a?gcd(b%a,a):b; }

ll minv(ll a,ll b){ return a<b?a:b;}

ll maxv(ll a,ll b){ return a>b?a:b;}

void swapv(ll &a,ll &b){a=a+b;b=a-b;a=a-b;}

ll power(ll a, ll b, ll m=mod){

   if(a==0 || b==1) return a;

   if(b==0) return 1;ll ans=1;

   while(b>=1){ if(b&1){b--;ans = (ans*a) % m;}a = (a*a)% m;b = b>>1;}return ans;

}

ll logv(ll x){ll ans =-1;while(x){x = x>>1;ans++;}return ans;}

ll inv(ll a,ll m){return power(a,m-2,m);}

int main() {

   ios_base::sync_with_stdio(false);

   cin.tie(NULL);  

   #ifndef ONLINE_JUDGE

       freopen("input.txt", "r", stdin);

       freopen("output.txt", "w", stdout);

       freopen("error.txt","w",stderr);

   #endif

   ll t=1;

   cin>>t;

   while(t--)

   {

      ll n;cin>>n;

      ll a[n];

      for(int i=0;i<n;i++) cin>>a[i];

      pair<ll,ll> dp[n+1];

      // dp[i] = {last_elem, min_cost}

      dp[0] = {0,0};

      ll pref[n+1] = {0};

      pref[1] = a[0];

      for(int i=0;i<n;i++){

           pref[i+1] = a[i] + pref[i];

           if(a[i] >= dp[i].first){

               dp[i+1] = {a[i],dp[i].second};

           }else{

               int start = 0;

               int end = i-1,mid = 0;

               ll tem = 0;

               ll cost = INT_MAX;

               for(mid=i;mid>=0;mid--){

                   tem += a[mid];

                   ll tem_cost = dp[mid].second + (i-mid);

                   if((tem >= dp[mid].first) && (cost > tem_cost)){

                       dp[i+1] = {tem,tem_cost};

                       cost = tem_cost;

                   }

               }

              

           }

      }

      cout<<dp[n].second;nl;

   }

   return 0;

}

Java Code

import java.util.*;

public class Main{

    public static void main(String[]args){

        Scanner at = new Scanner(System.in);

        int t = at.nextInt();

        while(t-->0){

            long n  = at.nextInt();

            int sz = 1001;

            int arr[] = new int[sz];

            int ans[] = new int[sz];

            int dp[] = new int[sz];

            for (int i = 1; i <= n; i++){

                arr[i] = at.nextInt();

            }

            dp[0] = 0;

            ans[0] = 0;

            dp[1] = 0;

            ans[1] = arr[1];

             for (int i = 2; i <= n; i++)

             {

                if (arr[i] >= ans[i - 1])

                {

                    dp[i] = dp[i - 1];

                    ans[i] = arr[i];

              }

            else

            {

                int j = i;

                ans[i] = 0;

                while (j > 0 && (ans[i] + arr[j] < ans[j - 1]))

                    {

                        ans[i] += arr[j];

                        j--;

                }

                ans[i] += arr[j];

                dp[i] = dp[j - 1] + (i - j);

            }

           

        }

        System.out.println(dp[(int)n]);

        }

    }

}
Python Code
dp = [0]*1001

ans =[0]*1001

def main():

    t = int(input())

    while(t>0):

        t-=1;

        n = int(input())

        arr = [0]*(n+1)

        l = (input()).split(" ")

        for i in range(1,n+1):

            arr[i] = int(l[i-1])

        dp[0] = 0;

        ans[0] = 0;

        dp[1] = 0;

        ans[1] = arr[1];

        for i in range(2,n+1):

            if arr[i]>=ans[i-1]:

                dp[i]=dp[i-1]

                ans[i]=arr[i]

            else:

                j=i

                ans[i]=0

                while j>0 and (ans[i]+arr[j]<ans[j-1]):

                    ans[i]+=arr[j]

                    j-=1

                ans[i]+=arr[j]

                dp[i] = dp[j - 1] + (i - j)

        print(dp[n],"\n")

main()
1 Like

IIT Roorkee’s Tech club is organising International Coding Challenge and here you can get a chance to win Rs. 1,00,000 plus the registration fee is Rs. 0
Here is link to register: Cognizance 2022
or Link: Cognizance ICC