In this HackerEarth The Old Monk problem solution 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:
Given 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.
The 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.
Find 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.
HackerEarth The Old Monk problem solution.
tc = int(raw_input())
while tc>0:
tc = tc - 1
curMax = 0
n = int(raw_input())
x = map(int, raw_input().split())
y = map(int, raw_input().split())
for i in xrange(n):
low, high, pos = 0, n - 1, -1
while low<=high:
mid = (low + high) / 2
if y[mid] >= x[i]:
pos = mid
low = mid + 1
else:
high = mid - 1
curMax = max (curMax, pos - i)
print curMax
Second solution
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
assert(1 <= t && t <= 50);
while(t--)
{
int n,i;
scanf("%d",&n);
assert(1 <= n && n <= 100000);
vector < long long > a(n),b(n);
for(i=0;i<n;i++)
{
scanf("%lld",&a[i]);
if(i)
assert(a[i] <= a[i-1]);
assert(1 <= a[i] && a[i] <= (long long)1e12);
}
for(i=0;i<n;i++)
{
scanf("%lld",&b[i]);
if(i)
assert(b[i] <= b[i-1]);
assert(1 <= b[i] && b[i] <= (long long)1e12);
}
int ans = 0;
for(i=0;i<n;i++)
{
int l = 0 , h = n-1 , m;
int p = -1;
while(l <= h)
{
m = (l+h)/2;
if(b[m] >= a[i])
{
p = m;
l = m + 1;
}
else
{
h = m - 1;
}
}
ans = max(ans,p - i);
}
printf("%d\n",ans);
}
return 0;
}
0 Comments