##
__Between the Mountains__

Link to the question : ACPC11B

###
__HINT : __

The question asks us to find the minimum difference between two mountains. This can be done with the naive solution, i.e, checking each element with every other element. The time limit allows us to do this.

###
__SOURCE CODE :__

#include<stdio.h>

int main()

{

int t;

scanf("%d",&t);

while(t--)

{

int n;

scanf("%d",&n);

int a[n],i;

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

scanf("%d",&a[i]);

int m;

scanf("%d",&m);

int b[m];

for(i=0;i<m;i++)

scanf("%d",&b[i]);

int diff=1000000,s,j;

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

{

for(j=0;j<m;j++)

{

if(a[i]>b[j])

s= a[i]-b[j];

else

s= b[j]-a[i];

if(s<diff)

diff=s;

}

}

printf("%d\n",diff);

}

return 0;

}

Is there any other method to solve this problem

ReplyDeleteThis might be done using binary search but I have not tried it yet.

Deletehow to do without brute force ?

ReplyDeleteSort the altitudes of first mountain. Now for each altitude on the second mountain, lets call it x, do a binary search on the altitudes of first mountain and find the smallest altitude greater than equal to x and the largest altitude smaller than x. Take difference of both with x and store the minimum. The minimum value for all the x will be the answer.

DeleteAnother approach can be found here :

Deletehttp://comproguide.blogspot.in/2013/12/minimum-difference-between-two-sorted.html