Chandan Biased Game

QUESTION

Big Chandan is a dire lover of Biryani, especially Old Monk’s Biryani. Today, he went over to have some of it. To his surprise, the waiter turns out be to be a coding geek and refuses to serves him unless Chandu solves his two- arrays problem, stated as:\n\nGiven two non-increasing array of integers A,B i.e A[i] >= A[i+1] and B[i] >= B[i+1] and for all i, 0 i < n-1.\n\nThe monkiness of two numbers is given by: M (A[i],B[j]) = j – i , if j >=i and B[j] >= A[i], or 0 otherwise. \n\n\nFind the monkiness of the two arrays, that is given by: M (A,B)= max (M(A[i],B[j])) for 0 i, j< n-1.\n\nInput Format:\nThe first line contains an integer, n, denoting the size of the two arrays. The size of both the arrays will be equal. After that line, the next line contains n integers denoting the numbers in the array A, and in the next line, there will be n numbers denoting the numbers in the array B.\n\nOutput format:\nPrint the monkiness of the two arrays.

“TESTCASE_1”: “6\n6 5 4 4 4 4\n2 2 2 2 2 2\n###—###SEPERATOR—###—\n0”, “TESTCASE_2”: “9\n7 7 3 3 3 2 2 2 1\n8 8 7 7 5 5 4 3 2\n###—###SEPERATOR—###—\n5”, “TESTCASE_3”: “12\n56 49 40 32 22 20 18 16 15 7 4 2\n88 76 65 55 43 34 23 20 14 12 9 3\n###—###SEPERATOR—###—\n2”, “TESTCASE_4”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0

ANSWER

#include<bits/stdc++.h>
typedef long long int ll;
using namespace std;
ll calc(ll f[],ll e,ll s)
{
    ll lb=0,up=s-1,mid,ans=-1;
    if (e>f[0])
        return ans;
    else
    {
        while (lb<=up)
        {
            mid=(lb+up)/2;
            if (f[mid]<e)
                up=mid-1;
            else
            {
                ans=mid;
                lb=mid+1;
            }
        }
        return ans;
    }
}
int main()
{
    ll t;
//    cin>>t;
//    while (t--)
//    {
        ll n;
        cin>>n;
        ll a[n],b[n],i,ma1=INT_MIN;
        for (i=0;i<n;i++)
            cin>>a[i];
        for (i=0;i<n;i++)
            cin>>b[i];
        for (i=0;i<n;i++){
        ll k=calc(b,a[i],n);
        if (k==-1 || i>k)
            ma1=max((ll)ma1,(ll)0);
        else
            ma1=max(ma1,k-i);
        }
        cout<<ma1<<"\n";
//}
}
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.