Binary Search – Live with passion

Fair Work Load [Top Coder]

Asif NaeemFebruary 25, 2016

This problem was used for: (@ Top coder) Single Round Match 169 Round 1 – Division I, Level Two Single Round Match 169 Round 1 – Division II, Level Three Problem Link

class FairWorkload{
	public:
	int getMostWork(vector<int> folder,int worker)
	{
		int n = folder.size();
		int lw = *max_element(folder.begin(),folder.end());
		int hi = accumulate(folder.begin(),folder.end(),0);
		int mid_load;
		int req_workers=1;
		int cur_load;
		if(worker==1)
		return hi;
		while(lw<hi)
		{
			mid_load = (lw+hi)/2;
			cur_load=0;
			req_workers=1;
			for(int i=0;i<n;i++)
			{
				if(cur_load+folder[i]<=mid_load)
				{
					cur_load += folder[i];
				}
				else
				{
					cur_load=folder[i];
					req_workers += 1;
				}
			}
			if(req_workers<=worker)
			hi = mid_load;
			else if(req_workers>worker)
			lw=mid_load+1;
		}
		return hi;
	}
};

class FairWorkload{

public:

int getMostWork(vector<int> folder,int worker)

{

int n = folder.size();

int lw = *max_element(folder.begin(),folder.end());

int hi = accumulate(folder.begin(),folder.end(),0);

int mid_load;

int req_workers=1;

int cur_load;

if(worker==1)

return hi;

while(lw<hi)

{

mid_load = (lw+hi)/2;

cur_load=0;

req_workers=1;

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

{

if(cur_load+folder[i]<=mid_load)

{

cur_load += folder[i];

}

else

{

cur_load=folder[i];

req_workers += 1;

}

if(req_workers<=worker)

hi = mid_load;

else if(req_workers>worker)

lw=mid_load+1;

}

return hi;

}

};

Total solution to run and test as a single program.

#include <iostream>
#include <cstdio>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

vector<int> folder;

class FairWorkload{
	public:
	int getMostWork(vector<int> folder,int worker)
	{
		int n = folder.size();
		int lw = *max_element(folder.begin(),folder.end());
		int hi = accumulate(folder.begin(),folder.end(),0);
		int mid_load;
		int req_workers=1;
		int cur_load;
		if(worker==1)
		return hi;
		while(lw<hi)
		{
			mid_load = (lw+hi)/2;
			cur_load=0;
			req_workers=1;
			for(int i=0;i<n;i++)
			{
				if(cur_load+folder[i]<=mid_load)
				{
					cur_load += folder[i];
				}
				else
				{
					cur_load=folder[i];
					req_workers += 1;
				}
			}
			if(req_workers<=worker)
			hi = mid_load;
			else if(req_workers>worker)
			lw=mid_load+1;
		}
		return hi;
	}
};
int main()
{
	int a,workers,n;
	while(1)
	{
		cout<<"enter no of file cabinets: ";
		cin>>n;
		folder.clear();
		for(int i=0;i<n;i++)
		{
			cin>>a;
			folder.push_back(a);

		}
		cin>>workers;
		FairWorkload fair;
		cout<<fair.getMostWork(folder,workers)<<"\n";
	}
	return 0;
}

#include <iostream>

#include <cstdio>

#include <vector>

#include <numeric>

#include <algorithm>

using namespace std;

vector<int> folder;

class FairWorkload{

public:

int getMostWork(vector<int> folder,int worker)

{

int n = folder.size();

int lw = *max_element(folder.begin(),folder.end());

int hi = accumulate(folder.begin(),folder.end(),0);

int mid_load;

int req_workers=1;

int cur_load;

if(worker==1)

return hi;

while(lw<hi)

{

mid_load = (lw+hi)/2;

cur_load=0;

req_workers=1;

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

{

if(cur_load+folder[i]<=mid_load)

{

cur_load += folder[i];

}

else

{

cur_load=folder[i];

req_workers += 1;

}

if(req_workers<=worker)

hi = mid_load;

else if(req_workers>worker)

lw=mid_load+1;

}

return hi;

}

};

int main()

{

int a,workers,n;

while(1)

{

cout<<"enter no of file cabinets: ";

cin>>n;

folder.clear();

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

{

cin>>a;

folder.push_back(a);

}

cin>>workers;

FairWorkload fair;

cout<<fair.getMostWork(folder,workers)<<"\n";

}

return 0;

}

880

Asif NaeemFebruary 25, 2016

#include <iostream>
#include <cstdio>
#define ul unsigned long long
#define INT_MX 2147483641

using namespace std;


ul binsearch(ul n,ul lw,ul hi)
{
	ul mid;
	ul tmp,tmp1,tmp2;
	while(lw<hi)
	{
		mid=(lw+hi)/2;
		tmp = (mid*(mid+1))/2;
		if(tmp<=n)
			lw=mid+1;
		else if(tmp>n)
			hi=mid;
	}
	return hi;
}
int main()
{
	ul n;
	ul diff,hi,lw;
	ul neumenator,denominator;
	while(cin>>n)
	{
		hi = binsearch(n,0,INT_MX);
		diff = n-(hi*(hi-1))/2;
		if(diff==0)
		{
			printf("%llu/%llu\n",1,hi-1);
		}
		else
		{
			printf("%llu/%llu\n",hi-(diff-1),diff);
		}
	}
	return 0;
}

#include <iostream>

#include <cstdio>

#define ul unsigned long long

#define INT_MX 2147483641

using namespace std;

ul binsearch(ul n,ul lw,ul hi)

{

ul mid;

ul tmp,tmp1,tmp2;

while(lw<hi)

{

mid=(lw+hi)/2;

tmp = (mid*(mid+1))/2;

if(tmp<=n)

lw=mid+1;

else if(tmp>n)

hi=mid;

}

return hi;

}

int main()

{

ul n;

ul diff,hi,lw;

ul neumenator,denominator;

while(cin>>n)

{

hi = binsearch(n,0,INT_MX);

diff = n-(hi*(hi-1))/2;

if(diff==0)

{

printf("%llu/%llu\n",1,hi-1);

}

else

{

printf("%llu/%llu\n",hi-(diff-1),diff);

}

return 0;

}

10611

Asif NaeemFebruary 24, 2016

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int arr[50005];

int binSearch(int num,int lw,int hi)
{
	int mid;
	while(lw<hi)
	{
		mid = (hi+lw)/2;

		if(num<arr[mid])
			hi = mid;
		else if(num>=arr[mid])
			lw = mid+1;

	}
	return hi;
}

int main()
{
	int N,Q,a;
	int len,qry,idx;
	while(scanf("%d",&N)!=EOF)
	{
		scanf("%d",&arr[0]);
		len = 1;
		for(int i=1;i<N;i++)
		{
			scanf("%d",&a);
			if(a!=arr[len-1])
			{
				arr[len]=a;
				len +=1;
			}
		}
		scanf("%d",&Q);
		for(int i=0;i<Q;i++)
		{
			scanf("%d",&qry);
			if(qry<arr[0])
			{
				printf("X %d\n",arr[0]);
			}
			else if(qry==arr[0])
			{
				printf("X");
				if(len>1)
				printf(" %d\n",arr[1]);
				else
				printf("X\n");
			}
			else if(qry==arr[len-1])
                        {
                                printf("%d X\n",arr[len-2]);
                        }
			else if(qry>arr[len-1])
			{
				printf("%d X\n",arr[len-1]);
			}
			else
			{
				idx = binSearch(qry,0,len-1);
				if(arr[idx-1]==qry)
				{
					if(idx>=2)
					printf("%d %d\n",arr[idx-2],arr[idx]);
					else
					printf("X %d\n",arr[idx]);
				}
				else if(arr[idx-1]!=qry)
					printf("%d %d\n",arr[idx-1],arr[idx]);
			}
		}

	}
	return 0;
}

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

int arr[50005];

int binSearch(int num,int lw,int hi)

{

int mid;

while(lw<hi)

{

mid = (hi+lw)/2;

if(num<arr[mid])

hi = mid;

else if(num>=arr[mid])

lw = mid+1;

}

return hi;

}

int main()

{

int N,Q,a;

int len,qry,idx;

while(scanf("%d",&N)!=EOF)

{

scanf("%d",&arr[0]);

len = 1;

for(int i=1;i<N;i++)

{

scanf("%d",&a);

if(a!=arr[len-1])

{

arr[len]=a;

len +=1;

}

scanf("%d",&Q);

for(int i=0;i<Q;i++)

{

scanf("%d",&qry);

if(qry<arr[0])

{

printf("X %d\n",arr[0]);

}

else if(qry==arr[0])

{

printf("X");

if(len>1)

printf(" %d\n",arr[1]);

else

printf("X\n");

}

else if(qry==arr[len-1])

{

printf("%d X\n",arr[len-2]);

}

else if(qry>arr[len-1])

{

printf("%d X\n",arr[len-1]);

}

else

{

idx = binSearch(qry,0,len-1);

if(arr[idx-1]==qry)

{

if(idx>=2)

printf("%d %d\n",arr[idx-2],arr[idx]);

else

printf("X %d\n",arr[idx]);

}

else if(arr[idx-1]!=qry)

printf("%d %d\n",arr[idx-1],arr[idx]);

}

return 0;

}

10487

Asif NaeemOctober 17, 2015

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <iostream>
//#include <cstdlib>

#define ll long long

using namespace std;

int a[1010];
vector<int> sum;

int binarySearch(int num,int lw,int hi)
{
	if(hi-lw==1)
	{
		int diff1 = abs(num-sum[lw]);
		int diff2 = abs(num-sum[hi]);
		if(diff1<diff2)
		return sum[lw];
		else
		return sum[hi];
	}
	int mid=(lw+hi)>>1;
	if(num<=sum[mid])
	return binarySearch(num,lw,mid);
	else
	return binarySearch(num,mid,hi);
	return 0;
}
int main()
{
	int n,qry,ans,num;
	int kase=1;
	while(scanf("%d",&n),n)
	{
		for(int i=0;i<n;i++)
		{
			scanf("%d",&a[i]);
		}
		sum.clear();
		for(int i=0;i<n;i++)
		{
			for(int j=i+1;j<n;j++)
				sum.push_back(a[i]+a[j]);
		}
		sort(sum.begin(),sum.end());
		int len=sum.size();
		bool flag=false;
		scanf("%d",&qry);
		while(qry--)
		{
			scanf("%d",&num);
			ans = binarySearch(num,0,len-1);
			if(!flag)
			printf("Case %d:\n",kase++);
			flag=true;
			printf("Closest sum to %d is %d.\n",num,ans);
		}
	}
	return 0;
}

#include <cstdio>

#include <cstring>

#include <vector>

#include <algorithm>

#include <iostream>

//#include <cstdlib>

#define ll long long

using namespace std;

int a[1010];

vector<int> sum;

int binarySearch(int num,int lw,int hi)

{

if(hi-lw==1)

{

int diff1 = abs(num-sum[lw]);

int diff2 = abs(num-sum[hi]);

if(diff1<diff2)

return sum[lw];

else

return sum[hi];

}

int mid=(lw+hi)>>1;

if(num<=sum[mid])

return binarySearch(num,lw,mid);

else

return binarySearch(num,mid,hi);

return 0;

}

int main()

{

int n,qry,ans,num;

int kase=1;

while(scanf("%d",&n),n)

{

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

{

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

}

sum.clear();

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

{

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

sum.push_back(a[i]+a[j]);

}

sort(sum.begin(),sum.end());

int len=sum.size();

bool flag=false;

scanf("%d",&qry);

while(qry--)

{

scanf("%d",&num);

ans = binarySearch(num,0,len-1);

if(!flag)

printf("Case %d:\n",kase++);

flag=true;

printf("Closest sum to %d is %d.\n",num,ans);

}

return 0;

}

714

Asif NaeemDecember 16, 2014

Using binary search to find the minimum value,

#include <iostream>
#include <string.h>
#include <vector>

#define ll long long

using namespace std;

ll b[505];
vector<int> res[505];

int main()
{
	int t;
	int books,writer;

	cin>>t;

	while(t--)
	{
		cin>>books>>writer;
		ll total=0,minwrk=0,mid=0;
		for(int i=0;i<books;i++)
		{
			cin>>b[i];
			total+=b[i];
			if(minwrk<b[i])
			minwrk = b[i];
		}

		//bin search
		while(minwrk<total)
		{
			int required=1;
			ll sum=0;
			mid= (total+minwrk)/2;

			for(int i=0;i<books;i++)
			{
				if(sum+b[i]>mid)
				{
					required++;
					sum=0;
				}
				sum+=b[i];
			}
			if(required>writer)
			minwrk=mid+1;
			else
			total=mid;
		}

		ll sum =0;
		int j=writer-1;
		for(int i=books-1;i>=0;i--)
		{
			if((sum+b[i])>total || j>i)
			{
				j--;
				sum=0;
			}
			sum+=b[i];
			res[j].push_back(b[i]);
		}

		for(int i=0;i<writer;i++)
		{
			for(int l=res[i].size()-1;l>=0;l--)
			{
				if(l!=res[i].size()-1)
					cout<<" "<<res[i][l];
				else
					cout<<res[i][l];
			}
			res[i].clear();
			if(i!=writer-1)
			cout<<" / ";
		}
		cout<<"\n";
	}

	return 0;
}

#include <iostream>

#include <string.h>

#include <vector>

#define ll long long

using namespace std;

ll b[505];

vector<int> res[505];

int main()

{

int t;

int books,writer;

cin>>t;

while(t--)

{

cin>>books>>writer;

ll total=0,minwrk=0,mid=0;

for(int i=0;i<books;i++)

{

cin>>b[i];

total+=b[i];

if(minwrk<b[i])

minwrk = b[i];

}

//bin search

while(minwrk<total)

{

int required=1;

ll sum=0;

mid= (total+minwrk)/2;

for(int i=0;i<books;i++)

{

if(sum+b[i]>mid)

{

required++;

sum=0;

}

sum+=b[i];

}

if(required>writer)

minwrk=mid+1;

else

total=mid;

}

ll sum =0;

int j=writer-1;

for(int i=books-1;i>=0;i--)

{

if((sum+b[i])>total || j>i)

{

j--;

sum=0;

}

sum+=b[i];

res[j].push_back(b[i]);

}

for(int i=0;i<writer;i++)

{

for(int l=res[i].size()-1;l>=0;l--)

{

if(l!=res[i].size()-1)

cout<<" "<<res[i][l];

else

cout<<res[i][l];

}

res[i].clear();

if(i!=writer-1)

cout<<" / ";

}

cout<<"\n";

}

return 0;

}

Category: Binary Search

Fair Work Load [Top Coder]

880

10611

10487

714

Archives

Categories