Z algorithm

Today we will try with a new algorithm – Z algorithm

This algo is used in pattern matching,there is another algo for pattern matching

This algorithm works in O(length of text+length of pattern) complexity

and space complexity is similar to time complexity that means O(length of text+length of pattern)

This algorithm is very easy.

</>Video Tutorial

 

</>Visualization

 

</> Blog

 

#Problemset

 

Advertisements

Lightoj 1414 Feb 29

Problem Link:


Hints:

if 2nd given month is not feb and january ,i will increment the value by 1

and if the first given month is jan or feb and date is less then 29 then i will decrement the value by 1

then for every year i will calculate the difference using a function

let y and yy are two years &&yy>=y &&passing yy and y-1 to function

int leap(int yy,int y,int x)
{
     return yy/x-y/x;
}


Then calculations

View Code
#include
using namespace std;
int month(string s)
{
string months[]={" ","January", "February", "March", "April", "May", "June", "July", "August", "September", "October", "November", "December"};
vectorv(months,months+13);
vector::iterator it=find(v.begin(),v.end(),s);
return distance(v.begin(), it);
}
int leap(int y,int yy,int x)
{
	return y/x-yy/x;
}

int main() {
		int n,d,dd,y,yy,cs=1;
		char a[24],b[24];
		cin>>n;
		while(n--)
		{//a.clear(),b.clear();
			scanf("%s %d, %d",a,&d,&y);
			scanf("%s %d, %d",b,&dd,&yy);
			int m,mm;
			m=month(a);
			mm=month(b);
			if(m>2) y++;
			if(mm<2 ||(mm==2 &&dd<29))
			yy--;
			y--;
			int dif=leap(yy,y,4)-leap(yy,y,100)+leap(yy,y,400);
			cout<<"Case "<<cs++<<": "<<dif<<endl;
		}
	return 0;
}

 

 

 

1259: Goldbach`s Conjecture

Problem Link

Hints:

store prime numbers in an vector;

then check the n-*it is prime or not

for example

6

2 4

3 3

here 2 is prime but (6-2)=4 is not prime

in the case of  3+3 here 3 is a prime and n-3=3 is also a prime number

 

 

 

View Code

#include<bits/stdc++.h>
using namespace std;
const int N=10000005;
bool status[N];
#define ll long long
vectorprime;

void sieve()
{
memset(status,0,sizeof status);
status[0]=status[1]=1;
ll k=N/2;

for(ll i=2;i<=k;i++)
{
if(!status[i])
{
prime.push_back(i);
for(ll j=2*i;j<=N;j+=i) status[j]=1; } } } int main() { sieve(); ll t,n,co=0,cs=1; //ll dp[N]; cin>>t;
while(t–)
{
cin>>n;

co=0;
ll k=n/2;
for(vector::iterator it=prime.begin();it!=prime.end() && *it<=k;it++)
{
if(status[n-*it]==0)
co++;
}
printf(“Case %lld: %lld\n”,cs++,co);
}
}

 

1067: Combinations

We all know the formula of nCr =n!/(r!*(n-r)!)

it’s a general formula,but this problem is about nCr %mod

it can be done with Modular multiplicative inverse 

formula of nCr % mod is (f(n)%mod*(((r)^(mod-2))%mod*((n-r)^(mod-2))%mod)%mod;

here we need to calculate the result using bigmod function;

References

 

View Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll dp[1000005];
const int mod = 1000003;
ll bigmod(ll a,ll b,ll mod)
{
if(b==0) return 1;
if(b&1)
{
return ((a%mod)*bigmod(a,b-1,mod))%mod;

}
else{
ll x=bigmod(a,b/2,mod);
return (x%mod*x%mod)%mod;
}

}

ll inverseEuler(ll a,ll b)
{
return bigmod(a,b-2,b);
}
int main()
{

dp[0]=dp[1]=1;

for(ll i=2;i<=1000000;i++) dp[i]=((dp[i-1]*i)%mod); ll n,k; ll cs=1,t; cin>>t;
while(t–)
{cin>>n>>k;
ll res=((dp[n]%mod)*(inverseEuler(dp[k],mod)*inverseEuler(dp[n-k],mod))%mod)%mod;
printf(“Case %lld: %lld\n”,cs++,res);
}
}

 

7001 – Bus Problem

Problem Link

Algorithm:

Kruskal

 

View Code

#include <bits/stdc++.h>
using namespace std;

#define INF 10000000

typedef unsigned long long ll;
typedef vector vi;
typedef vector< vi > vvi;
typedef pair<int, int> ii;
typedef vector vii;
typedef vector vvii;
typedef set si;
typedef map<string, int> msi;

#define all(x) x.begin(), x.end()
#define tr(container, it) for(typeof(container.begin()) it = container.begin(); it != container.end(); it++)
#define sz(a) int((a).size())
#define pb push_back
#define mp make_pair
#define spresent(c,x) ((c).find(x) != (c).end()) // for set,map
#define present(c,x) (find(all(c),x) != (c).end()) // for vector
#define uu first
#define vv second
#define fr(i,a,b) for(int i=int(a);i<=int(b);++i) #define nfr(i,a,b) for(int i= int(a);i>=int(b);–i)
#define mx 10010
struct edge{
int u,v,w;
bool operator<(const edge x) const{
return w<x.w; } }e[100010]; int pr[mx]; int find(int r) { if(pr[r]!=r) return pr[r]=find(pr[r]); else return r; } int main() { int t,n,m; cin>>t;
while(t–)
{
for(int i=0;i<=mx;i++) pr[i]=i; ll s=0; cin>>n>>m;
for(int i=0;i<m;i++) { cin>>e[i].u>>e[i].v>>e[i].w;

s+=(1ll*e[i].w);
}

sort(e,e+m);

for(int i=0;i<m;i++)
{
int u=find(e[i].u);
int v=find(e[i].v);
if(u!=v)
{
pr[v]=u;
s-=(1ll)*e[i].w;

}
}
cout<<s<<endl;

}

}

 

CSTREET

Problem Link

Algorithm:

                    Kruskal

 

View Code

#include <bits/stdc++.h>
using namespace std;

#define INF 10000000
//=======================Starts===========================
typedef unsigned long long ll;
typedef vector vi;
typedef vector< vi > vvi;
typedef pair<int, int> ii;
typedef vector vii;
typedef vector vvii;
typedef set si;
typedef map<string, int> msi;

#define all(x) x.begin(), x.end()
#define tr(container, it) for(typeof(container.begin()) it = container.begin(); it != container.end(); it++)
#define sz(a) int((a).size())
#define pb push_back
#define mp make_pair
#define spresent(c,x) ((c).find(x) != (c).end())  // for set,map
#define present(c,x) (find(all(c),x) != (c).end())  // for vector
#define uu first
#define vv second
#define fr(i,a,b) for(int i=int(a);i<=int(b);++i) #define nfr(i,a,b) for(int i= int(a);i>=int(b);–i)

//=======================Ends===========================
#define mx 10010
struct edge{
ll u,v,w;

};
bool cmp(edge &a,edge &b)
{
return a.w<b.w;

}
ll pr[mx];
void makeset(ll n)
{
for(ll i=0;i<=n;i++)
pr[i]=i;
}
ll find(ll r)
{
if(pr[r]!=r)
return pr[r]=find(pr[r]);
else return r;

}

vector<edge>e;
ll mst(ll n)
{
ll s=0,c=0;
sort(e.begin(),e.end(),cmp);
makeset(n);
for(ll i=0;i<e.size();i++) { ll u=find(e[i].u); ll v=find(e[i].v); if(u!=v) { pr[v]=u; c++; s+=e[i].w; } if(c==n-1) return s; } return -1; } int main() { ll t,p,n,m; cin>>t;
while(t–)
{
cin>>p>>n>>m;

while(m–){
ll u,v,w;
cin>>u>>v>>w;
edge get;
get.u=u;
get.v=v;
get.w=w;
e.pb(get);
}

ll s=mst(n);
cout<<s*p<<endl;
}

}