Spoj- SUBS- String It Out

Problem Link:
                       [http://www.spoj.com/problems/SUBS/]


Category: Binary Search

Strategy: We can optimize the solution by this: Let ,
                 o=(Length of Y)/(Length of X).

here we have found the highest possible number of M. The lowest will be 0. Then we have to do binary search within this range.


Code:

     

#include<bits/stdc++.h>
	#define ll int
	using namespace std;
	ll sequence(string y,string x)
	{ ll n,o,p,cnt=0;
	for(int i=0; i<y.size(); i++)
	{
	if(y[i]==x[cnt])
	{
	cnt++;}
	}
	if(cnt==x.size())
	return 1;
	else
	return 0;
	}
	string match(string x,ll mid)
	{ string s="";
	for(int i=0; i<x.size(); i++)
	for(int j=0; j<mid; j++)
	s+=x[i];
	return s;
	}
	int main()
	{
	/*ifstream infile;
	infile.open("A-large.in");
	//freopen("output_file_name.out","w",stdout);
	ofstream outfile;
	outfile.open("output_file_name.out");*/
	string x,y;
	ll n,m,o,p;
	cin>>n;
	while(n--){ x=y="";
	cin>>x>>y;
	o=y.length()/x.length();
	ll l=0,h=o;
	while(l<=h)
	{ m=(l+h)/2;
	if(sequence(y,match(x,m)))
	l=m+1;
	else
	h=m-1;
	}
	cout<<h<<endl;}
	}

Spoj ABCDEF

Problem Link: [http://www.spoj.com/problems/ABCDEF/]

Category: Binary Search

Strategy: Before Solving that, you can explore another problem- 'SUMFOUR'
                 [http://www.spoj.com/problems/SUMFOUR/]

Here we have to find out highest possible tuples, which consists of element satisfying the following equation:

               (a*b+c)/d - e = f, ( where,d!=0)
           ->  a*b +c=d*(e+f)


now, we can generate LHS and RHD values using O(n^3) loops and store them in separate array.
Then we can use binary search strategy to find out the equality between two sides and count,

Reading Material: (In Quora)
 [https://www.google.com.bd/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&cad=rja&uact=8&ved=0ahUKEwi-4Y3x4f3OAhWMRI8KHYDaAMYQFgghMAE&url=https%3A%2F%2Fwww.quora.com%2FHow-do-we-go-about-solving-the-SPOJ-com-Problem-ABCDEF&usg=AFQjCNFZwcYq5DCqN2yu0YhTeiGBWYtoTQ&sig2=748y-wSkfYhD_sldY2vB4w&bvm=bv.131783435,d.c2I]

Code:

     

#include <bits/stdc++.h>
	#define in long long int
	#define M 10000000000
	using namespace std;
	int main()
	{
	in c,o,p,n;
	vector<in>x,m1,m2,a1,a2;
	cin>>n;
	p=n;
	while(p--)
	{
	cin>>o;
	x.push_back(o);
	}
	for(in i=0; i<n;i++)
	{
	for(in j=0; j<n; j++)
	{
	for(in k=0; k<n; k++)
	{
	a2.push_back(x[i]*x[j] + x[k]);
	}
	}
	}
	for(in i=0; i<n;i++)
	{
	for(in j=0; j<n; j++)
	{
	for(in k=0; k<n; k++)
	{ if(x[k]==0) continue;
	m2.push_back(x[k]*(x[i]+x[j]));
	}
	}
	}
	sort(a2.begin(),a2.end());
	sort(m2.begin(),m2.end());
	in co=0;
	for(in i=0; i<a2.size(); i++)
	{
	in l=lower_bound(m2.begin(),m2.end(),a2[i])-m2.begin();
	in u=upper_bound(m2.begin(),m2.end(),a2[i])-m2.begin();
	co+=u-l;
	}
	cout<<co<<endl;
	}