Lightoj 1433: Minimum Arc Distance

Problem link:[http://lightoj.com/volume_showproblem.php?problem=1433]
Catagory: Adhoc, Mathematics

Explanation:
          S=r*s
here,
          S= Arc length between 2 points in circle
          r= radius of circle
          s= Angle between 2 points in circle
again,
         c^2=a^2 + b ^2 - 2abcos(angle)
         here, a=b=r
         and c=distace between 2 points

so, angle=Inverse_cos((2r^2-c^2)/r^2)

Code:

#include<bits/stdc++.h>
#define ll       long long int
#define SIZE 100005
using namespace std;

double dis(ll x1, ll x2, ll y1, ll y2)
{
          double m=(x1-x2)*(x1-x2);
          double n=(y1-y2)*(y1-y2);

          return sqrt(m+n);

}


int main()
{
          ll o1,o2,a1,a2,b1,b2,l;
          cin>>l;
          ll i=1;
          while(i<=l)
          {
                    cin>>o1>>o2>>a1>>a2>>b1>>b2;
                    double r=dis(o1,a1,o2,a2);
                    double d=dis(a1,b1,a2,b2);
                    double s=acos((2*r*r-d*d)/(2*r*r));
                    cout<<"Case "<<i<<": "<<fixed<<setprecision(8)<<r*s<<"\n";
                    i++;
          }



          return 0;
}

Maximum Sub-array Sum Using Kandane's Algorithm

Problem link:
                     [https://www.interviewbit.com/problems/max-sum-contiguous-subarray/]

Statement:

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example:

Given the array [-2,1,-3,4,-1,2,1,-5,4],

the contiguous subarray [4,-1,2,1] has the largest sum = 6.

For this problem, return the maximum sum.

Catagory: Kandane's Algorithm, Divide and conquer, Bruteforce

Explanation: This problem can be solved either O(n^3),O(n^2) ,O(nlogn) or O(n). Kandane's algorithm is the O(n) solution and i find it so simple and fascinating.

Study Material: codeschool tutorial

                         [https://www.youtube.com/watch?v=ohHWQf1HDfU&feature=youtu.be]

Code:

int Solution::maxSubArray(const vector<int> &A) {

details

    int n=A.size(),s=0,a=INT_MIN,m=INT_MIN;

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

    {

        if(s+A[i]>0)

        s+=A[i];

        else

        {

        

        a=max(a,A[i]+s);

            

        s=0;

        continue;

        }

        

        a=max(a,s);

    }

   

    return a;

    

}

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;
	}