Spoj-Aggressive cows

After a long time ,i started solving spoj problems.I came across this interesting problem

http://www.spoj.com/problems/AGGRCOW/

Here is the approach

lets have a function

f(x) which will return 1 if gap between the cow stalls can be atleast of length x( i.e. all cows can occupy the stalls which are placed x distance  from ajacent stalls)

or return 0 if the gap between the stalls cannot be of length x

iff(x) ==0 then f(y) is also 0 such that y>x . We should code a function which can check

if x is can be allowed distance between each stall.

Our task is to find the largest minimum distance between the stalls.(i.e largest value of the allowed minimum distance)

How to do that ??

Well,You can always place cows such that the minimum distance is 0, while almost always, you cannot achieve minimum distance = N-1. For each number ‘x’ between 0 and N-1, you can either place the cows with minimum distance = ‘x’ or not.
If you list whether you can place the cows with a given distance ‘x’ you have check one by one
0 – Yes
1 – Yes
2 – Yes
.
.
.
x1 – Yes
x2 – No
x2+1 – No
.
.
.
N-1 – No

Our task is to find x1

This can be done using a simple binary search!

f(0)………………………………………………………..f(N-1) will be like

1 1 1 1 1 1 1 0 0 0 0 0 0…………………………..0 0 0

we have to find the last occuring 1

let

start=0

end=n-1

mid =(start+end)/2

if f(mid)=0 then x1 occurs within start and mid

if f(mid)=1 then x1 occurs within mid+1 and end

Search accordingly using divide and conquer strategy

[gist https://gist.github.com/vishnujayvel/6329080]

searching in rotated sorted array

to search x in sorted rotated array lets modify the binary search as follows
divide the array to 2 parts
m=l+(h-1)/2
if lower part is sorted
if arr[l]<=x<arr[m]
make h=m-1 (search in sorted lower half)
else
l=m+1(search in unsorted upper half)
else (upper part is sorted)
if arr[m]<x<=arr[h]
make l=m+1 (search in sorted upper half)
else
h=m-1 (search in unsorted lower half)

	#include<iostream>
	using namespace std;
	int main(){
	int arr[]={880,982,99,10,55,66,77,78};//rotated sorted array
	int l=0;
	int h=sizeof(arr)/sizeof(int)-1;
	int mid;
	int x=78;
	int pos=-1;
	while(l<=h){
	mid=l+(h-1)/2;
	if(arr[mid]==x)
	pos=mid;
	if(arr[l]<arr[mid]){
	if(arr[l]<=x&&x<arr[mid])
	h=mid-1;
	else
	l=mid+1;
	}
	else{
	// this is implicit:if(arr[mid]<arr[h])
	if(arr[mid]<x&&x<=arr[h])
	l=mid+1;
	else
	h=mid-1;
	}
	}
	if(pos!=-1)
	cout<<pos;
	else
	cout<<"not found";
	}

view raw searchinrotatedsortedarray hosted with ❤ by GitHub

Given a rotated sorted array, find the MIN of the array.

Thanks to binary search ,this can be done in O(logn)
if you divide a rotated sorted array into arr[l]…arr[mid] and arr[mid+1].. arr[h] ,then one of the 2 subarrays will be sorted.Ignore the sorted array and keep searching in the unsorted array(in which first element will be greater than last element)

	#include<iostream>
	using namespace std;
	int main(){
	int arr[]={880,982,99,10,55,66,77,78};
	int l=0;
	int h=sizeof(arr)/sizeof(int)-1;
	int mid;
	while(arr[l]>arr[h]){
	mid=l+(h-l)/2;
	if(arr[mid]>arr[h]){
	l=mid+1;
	}
	else
	h=mid;
	}
	cout<<arr[l];
	}

view raw

mininrotatedsortedarray

hosted with ❤ by GitHub