Saturday 31 January 2015

STL's EASY WAY TO FIND maximum & minimum IN AN ARRAY

 *max_element(a,a+n)-*min_element(a,a+n)






ONE_ZERO SPOJ 

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


It's very important to make a visited array [1...n], so that the number which is visited once will not be visited again, if we would not make this visited it will definitely lead to TLE :P (idea credit kishlay )


solution


#include<bits/stdc++.h>

using namespace std;

string bfs(int n)
{

 pair<int,string> temp;
 queue<pair<int,string> > st;
 st.push(make_pair(1,"1"));
 int visited[n];
 for(int i=0;i<n;i++) visited[i]=0; visited[1]=1;

 while(!st.empty())
 {
  string tt1,tt2;
  temp=st.front();
  st.pop();
  if(temp.first%n!=0)
  {
    tt1=temp.second+"0";
    //cout<<tt<<" ";
    if(visited[(temp.first*10)%n]==0){
    st.push(make_pair((temp.first*10)%n,tt1));
    visited[(temp.first*10)%n]=1;}

     tt2=temp.second+"1";
    if(visited[(temp.first*10+1)%n]==0){
    st.push(make_pair((temp.first*10+1)%n,tt2));
    visited[(temp.first*10+1)%n]=1;}
  }
  else
  {
    return temp.second;
  }
 }
}

int main()
{
 int t;
 cin>>t;
 while(t--)
 {
  int n;
  cin>>n;
  string pp=bfs(n);
  cout<<pp<<endl;
 }
return 0;
}

Wednesday 28 January 2015

UNION FIND FOR CODECHEF QUESTION http://www.codechef.com/ALMA2015/problems/ALMA03/


chota bheem and gcd (https://www.codechef.com/problems/ALMA03 )

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

  3. #define MAXN 205
  4. #define MOD 1000000007
  5. int parent[MAXN],A[MAXN];
  6. void init()
  7. {
  8. for(int i=0;i<MAXN;++i)
  9. parent[i] = -1;
  10. }
  11. int find(int i)
  12. {
  13. if(parent[i]==-1)
  14. return i;
  15. else
  16. return parent[i] = find(parent[i]);
  17. }
  18. void merge(int x,int y)
  19. {
  20. x = find(x);
  21. y = find(y);
  22. if(x!=y)
  23. {
  24. if(A[x]>A[y])
  25. parent[y] = x; /// whose rank is greater will become parent (here Rank work is done by Cost itself)
  26. else
  27. parent[x] = y;
  28. }
  29. }
  30. int main()
  31. {
  32. int t,n;
  33. scanf("%d",&t);
  34. while(t--)
  35. {
  36. init();
  37. scanf("%d",&n);
  38. for(int i=0;i<n;++i
  39. { scanf("%d",A+i); }
  40. for(int i=0;i<n;++i)
  41. for(int j=i+1;j<n;++j)
  42. if(__gcd(A[i],A[j])>1)
  43. merge(i,j);

  44. long long result = 1;
  45. for(int i=0;i<n;++i)
  46. if(parent[i]==-1)
  47. {
  48. result *= A[i];
  49. result %= MOD;
  50. }
  51. printf("%lld\n",result);
  52. }
  53. }

nCr  find  karne  ka  best  example.


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


int fast_pow(long long base, long long n,long long M)
{
    if(n==0)
       return 1;
    if(n==1)
    return base;
    long long halfn=fast_pow(base,n/2,M);
    if(n%2==0)
        return ( halfn * halfn ) % M;
    else
        return ( ( ( halfn * halfn ) % M ) * base ) % M;
}

int findMMI_fermat(int n,int M)
{
    return fast_pow(n,M-2,M);
}


int main()
{
    long long fact[100001];
    fact[0]=1;
    int i=1;
    int MOD=1000000007;
    while(i<=100000)
    {
        fact[i]=(fact[i-1]*i)%MOD;
        i++;
    }
    int t;
    cin>>t;
    while(t--)
    {
        int n,r;
        //printf("Enter n: ");
        scanf(" %d",&n);
        //printf("Enter r: ");
        scanf(" %d",&r);
        long long numerator,denominator,mmi_denominator,ans;
        //I declared these variable as long long so that there is no need to use explicit typecasting
        numerator=fact[n];
        denominator=(fact[r]*fact[n-r])%MOD;
        mmi_denominator=findMMI_fermat(denominator,MOD);
        ans=(numerator*mmi_denominator)%MOD;

        printf("%lld\n",ans);
    }
    return 0;
}

( BFS  APP. 3rd)  COUNT  NUMBER  OF  CONNECTED  COMPONENTS .

 SPOJ (PRAYATNA  PR)    USING  ADJ.  LIST





#include<bits/stdc++.h>

using namespace std;
vector<int> vv[100000];

void bfs(int src,int v,int visited[],int lebel[])
{
 int i,rem;
 lebel[src]=0;
 visited[src]=1;

 queue<int> q;
 q.push(src);

 while(!q.empty())
 {
  rem=q.front();
  q.pop();
  for(i=0;i<vv[rem].size();i++)
  {
   if(visited[ vv[rem][i] ]!=1)
   {
     lebel[vv[rem][i]]=lebel[rem]+1;
     q.push(vv[rem][i]);
     visited[vv[rem][i]]=1;
   }
  }
 }
}


int main()
{
int t,hh;
cin>>t;
for(hh=1;hh<=t;hh++)
{
 int i,j,p,q,rem,v,e,flag=0,gco=1;
 cin>>v>>e;

  int lebel[v];
  int visited[v];

 for(i=0;i<v;i++)  lebel[i]=-1;

 for(i=0;i<v;i++)  visited[i]=0;  ///no vertex is visited yet


 for(i=1;i<=e;i++)
 {
     cin>>p>>q;
     vv[p].push_back(q);
     vv[q].push_back(p);
 }

 for(i=1;i<=v;i++)
 lebel[i]=-1;

 bfs(0,v,visited,lebel);

for(i=0;i<v;i++)
if(lebel[i]==-1)
{
gco++;
bfs(i,v,visited,lebel);
}

 cout<<gco<<endl;

 for(i=0;i<100000;i++)
  vv[i].clear();
}
return 0;
}


Tuesday 27 January 2015

DIJKSTRA  IN 2 D  MATRIX  USING  PRIORITY QUEUE :)

SPOJ SHOPPING


#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
int indx[]={-1,0,0,+1};
int indy[]={0,+1,-1,0};
int w,h;
string a[1000];

#define pp pair<int,pair<int,int> >

class Prioritize
{
public:
    int operator() ( const pair<int,pair<int,int> >& p1, const pair<int,pair<int,int> >& p2 )
    {
        return p1.first > p2.first;
    }
};

void dij(int x,int y,int x1,int y1)
{
  //cout<<"gaya"<<endl;
 int visited[h][w];
 int i,j,dt1,dt2,dt3;

 for(i=0;i<h;i++)
   for(j=0;j<w;j++)
     visited[i][j]=0;

 int dist[h][w];
 for(i=0;i<h;i++)
   for(j=0;j<w;j++)
     dist[i][j]=INT_MAX;

  visited[x][y]=1;
  dist[x][y]=0;

  priority_queue<pp, vector<pp > , Prioritize > Q;

  pair<int,pair<int,int> > temp;
  temp.f=0; temp.s.f=x; temp.s.s=y;

  Q.push(temp);
  while(!Q.empty())
  {
    temp=Q.top();
    Q.pop();
     //cout<<temp.f<<" "<<temp.s.f<<" "<<temp.s.s<<endl;
     for(i=0;i<4;i++)
     {
      if(temp.s.f+indx[i]>=0 && temp.s.f+indx[i]<h && temp.s.s+indy[i]>=0 && temp.s.s+indy[i]<w)
      if(visited[temp.s.f+indx[i]][temp.s.s+indy[i]]==0 && a[temp.s.f+indx[i]][temp.s.s+indy[i]]!='X')
      if(dist[temp.s.f+indx[i]][temp.s.s+indy[i]] > temp.f+a[temp.s.f+indx[i]][temp.s.s+indy[i]]-48)
       {
       // cout<<temp.f<<"+"<<a[temp.s.f+indx[i]][temp.s.s+indy[i]]-48<<endl;
        dist[temp.s.f+indx[i]][temp.s.s+indy[i]]=temp.f+a[temp.s.f+indx[i]][temp.s.s+indy[i]]-48;
        dt1=dist[temp.s.f+indx[i]][temp.s.s+indy[i]];
        dt2=temp.s.f+indx[i];
        dt3=temp.s.s+indy[i];
        visited[temp.s.f+indx[i]][temp.s.s+indy[i]]=1;
        Q.push(make_pair(dt1,make_pair(dt2,dt3)));

       }
     }
    }

   /* for(i=0;i<h;i++){
     for(j=0;j<w;j++)
      cout<<dist[i][j]<<" ";
        cout<<endl;}*/

    int mini=INT_MAX;
    for(i=0;i<4;i++)
     {
      if(x1+indx[i]>=0 && x1+indx[i]<h && y1+indy[i]>=0 && y1+indy[i]<w)
        if(dist[x1+indx[i]][y1+indy[i]]<mini)
         mini=dist[x1+indx[i]][y1+indy[i]];
     }
   cout<<mini<<endl;
  }


int main()
{
 while(1)
 {

 cin>>w>>h;
 int i,j,x2,y2,x,y;

 if(w==0 && h==0)
  break;

 for(i=0;i<h;i++)
  cin>>a[i];

 for(i=0;i<h;i++)
 for(j=0;j<w;j++)
 {
  if(a[i][j]=='S')
   {x=i; y=j;}
  if(a[i][j]=='D')
  { x2=i;y2=j;}
 }
 a[x2][y2]='X';
dij(x,y,x2,y2);
}
return 0;
}

Monday 26 January 2015

STL  SET  QUESTION   SPOJ   FRIENDS OF  FRIEND




#include<bits/stdc++.h>

using namespace std;

int main()
{
int n,i,k,m,j;
cin>>n;

set<int> s;
for(i=0;i<n;i++)
{
cin>>k;
s.insert(k);
 cin>>m;
 for(j=0;j<m;j++)
 {
  cin>>k;
  s.insert(k);
 }
}
 //for (std::set<int>::iterator it=s.begin(); it!=s.end(); ++it)
   // std::cout << ' ' << *it;
 
    cout<<s.size()-n<<endl;
return 0;
}

Friday 23 January 2015

DIJKSTRA  USING  SET  (ADJ. LIST )\\  spoj ques (The shortest path)




Here set  is doing the same job as  of minimum priority queue..
Set also arrange the in ascending order.



#include<bits/stdc++.h>
#define pp pair<int,int>

using namespace std;

void dijk(int src,int des,int nc,vector<pair<int,int> > v[])
{
 int i,j,u;
 set<pair<int,int> > Q;
 set<pair<int,int> > :: iterator itx;

   int dist[nc]; for(i=0;i<nc;i++) dist[i]=INT_MAX;

 dist[src]=0;
 Q.insert(pp(dist[src],src));

    while(!Q.empty())
    {
        itx=Q.begin();
        u = itx->second;
        Q.erase(itx);                    ///jo visited ho gaya wo poped

       if(itx->first<= dist[u])
        {
           for(j=0;j<v[u].size();j++)
           if((dist[u]+v[u][j].second)<dist[v[u][j].first])
            {
            dist[v[u][j].first]=dist[u]+v[u][j].second;
            Q.insert(pp(dist[v[u][j].first],v[u][j].first));
            }
        }
    }
cout<<dist[des]<<endl;
}

int main()
{
    ios_base::sync_with_stdio(false);
 int t;
 cin>>t;
 while(t--)
 {
  int nc,i,j,ci,cc,num,q;
   string s;
   cin>>nc;

   vector<pair<int,int> > v[nc];

   map<string,int> mp1;   ///map ka pahla wala index hota hai
   for(i=0;i<nc;i++)
   {
     cin>>s;
     mp1[s]=i;
     cin>>num;

      for(j=0;j<num;j++)
      {
          cin>>ci>>cc;
          ci--;
          v[i].push_back(make_pair(ci,cc));
      }
   }

   cin>>q;
   for(int k=0;k<q;k++)
   {
    string s1,s2;
    cin>>s1>>s2;
    dijk(mp1[s1],mp1[s2],nc,v);
   }

   for(i=0;i<nc;i++)
    v[i].clear();
   mp1.clear();
 }
return 0;
}

Thursday 22 January 2015


( BFS APP. 1) CHECKING OF  BIPARTITE  GRAPH  USING  ADJACENTARY  LIST

#include<bits/stdc++.h>

using namespace std;
vector<int> vv[20001];
//vector<int>  vec[10000];
void bfs(int src,int v,int visited[],int lebel[])
{
 int i,rem;
 lebel[src]=0;

 visited[src]=1;

 queue<int> q;
 q.push(src);

 while(!q.empty())
 {
  rem=q.front();
  q.pop();
  for(i=0;i<vv[rem].size();i++)
  {
   if(visited[ vv[rem][i] ]!=1)
   {
     lebel[vv[rem][i]]=lebel[rem]+1;
     q.push(vv[rem][i]);
     visited[vv[rem][i]]=1;
   }
  }
 }

for(i=1;i<=v;i++)
if(!visited[i])
bfs(i,v,visited,lebel);
}




int main()
{
int t,hh;
cin>>t;
for(hh=1;hh<=t;hh++)
{
 int i,j,p,q,rem,v,e,flag=0;
 cin>>v>>e;


  int lebel[v+1];
   int visited[v+1];

 for(i=1;i<=v;i++)  lebel[i]=-1;

 for(i=1;i<=v;i++)  visited[i]=0;  ///no vertex is visited yet



 if(v==1)
 {
    cout<<"Scenario #"<<hh<<":"<<endl;
    cout<<"No suspicious bugs found!"<<endl;
    continue;
 }

 for(i=1;i<=e;i++)
 {
     cin>>p>>q;
     vv[p].push_back(q);
     vv[q].push_back(p);
     }

 for(i=1;i<=v;i++)
 lebel[i]=-1;

 bfs(1,v,visited,lebel);

 for(i=1;i<=v;i++)
 {
   for(j=0;j<vv[i].size();j++)
   {
     if(lebel[vv[i][j]]%2==lebel[i]%2)
     {flag=1; break;}
   }
 }


if(flag==1){
 cout<<"Scenario #"<<hh<<":"<<endl;
 cout<<"Suspicious bugs found!"<<endl;}

else{
  cout<<"Scenario #"<<hh<<":"<<endl;
 cout<<"No suspicious bugs found!"<<endl;}

 for(i=0;i<2001;i++)
  vv[i].clear();
}
return 0;
}


(BFS APP 2) LONGEST   PATH  IN   A  TREE   BY  THE   USE    OF    ADJACENATARY     LIST.





#include<bits/stdc++.h>

using namespace std;
vector<int> vv[10001];

int lebel[10001];
int visited[10001];

void bfs(int src,int v)
{
    //cout<<v<<endl;
// cout<<"hi"<<endl;
 int i,rem;
 for(i=1;i<=v;i++) lebel[i]=-1;
 lebel[src]=0;

 for(i=1;i<=v;i++) visited[i]=0;  ///no vertex is visited yet

 visited[src]=1;

 queue<int> q;
 q.push(src);

 while(!q.empty())
 {
  rem=q.front();
  //cout<<"nikala"<<rem<<" ";
  q.pop();
  //cout<<vv[rem].size()<<" size ";
  for(i=0;i<vv[rem].size();i++)
  {

   if(visited[ vv[rem][i] ]!=1)
   {

     lebel[vv[rem][i]]=lebel[rem]+1;
    //      cout<<vv[rem][i]<<" "<<visited[ vv[rem][i] ]<<" "<<lebel[vv[rem][i]]<<endl;
     //cout<<vv[rem][i]<<" ";
     q.push(vv[rem][i]);
     visited[vv[rem][i]]=1;
   }
  }
 }

 /*cout<<"lebel" <<v<<endl;
for(int k=1;k<=v;k++)
    cout<<lebel[k]<<" ";
cout<<endl;*/

}

int main()
{
int i,j,p,q,rem,v;
cin>>v;

vector<pair<int ,int> > vec;

if(v==1)
{
    cout<<"0"<<endl;
    return 0;
}

for(i=1;i<v;i++)
{
     cin>>p>>q;
     vec.push_back(make_pair(p,q));
     vec.push_back(make_pair(q,p));
}

 for(i=1;i<=v;i++)
 {
   for(j=0;j<vec.size();j++)
   {
          if(vec[j].first==i)
          vv[i].push_back(vec[j].second);
   }
 }
//cout<<endl;
/*
 for(i=1;i<=v;i++)
 {
     for(j=0;j<vv[i].size();j++)

        cout<<vv[i][j]<<" ";
        //cout<<endl;
 }
*/
 bfs(1,v);

int max=0;
for(i=1;i<=v;i++)
{
 if(lebel[i]>max)
 {
  rem=i;
  max=lebel[i];
 }
}

bfs(rem,v);

max=0;
for(i=1;i<=v;i++)
{
 if(lebel[i]>max)
 {
  rem=i;
  max=lebel[i];
 }
}
cout<<max<<endl;

return 0;
}

BFS     WITH    LEBEL



#include<bits/stdc++.h>

using namespace std;

int graph[100][100],v;


void bfs(int src)
{
 int lebel[v+1],i,rem;
 for(i=1;i<=v;i++) lebel[i]=-1;
 lebel[src]=0;

 int visited[v+1];
 for(i=1;i<=v;i++) visited[i]=0;  ///no vertex is visited yet
 visited[src]=1;

 queue<int> q;
 q.push(src);

 while(!q.empty())
 {
  rem=q.front();
  cout<<rem<<" ";
  q.pop();
  for(i=1;i<=v;i++)
  {
   if(graph[rem][i]==1 && visited[i]==0)
   {
    lebel[i]=lebel[rem]+1;
    cout<<i<<" ";
    q.push(i);
    visited[i]=1;
   }
  }
 }
cout<<endl;

for(i=1;i<=v;i++)
cout<<lebel[i]<<" ";
}

int main()
{
int i,j;
cin>>v;

for(i=1;i<=v;i++)
 for(j=1;j<=v;j++)
 cin>>graph[i][j];

 bfs(1);
return 0;
}

Wednesday 21 January 2015

  1. //fast input/ out


  2. long long int read_int(){
    char r;
    bool start=false,neg=false;
    long long int ret=0;
    while(true){
    r=getchar();
    if((r-'0'<0 || r-'0'>9) && r!='-' && !start){
    continue;
    }
    if((r-'0'<0 || r-'0'>9) && r!='-' && start){
    break;
    }
    if(start)ret*=10;
    start=true;
    if(r=='-')neg=true;
    else ret+=r-'0';
    }
    if(!neg)
    return ret;
    else
    return -ret;

    //LL int scan_lld()    {int ip=getchar_unlocked(),flag=1;lld ret=0;for(;ip<'0'||ip>'9';ip=getchar_unlocked())if(ip=='-'){flag=-1;ip=getchar_unlocked();break;}for(;ip>='0'&&ip<='9';ip=getchar_unlocked())ret=ret*10+ip-'0';return flag*ret;}








  1. int scan_d() {int ip=getchar_unlocked(),ret=0,flag=1;for(;ip<'0'||ip>'9';ip=getchar_unlocked())if(ip=='-'){flag=-1;ip=getchar_unlocked();break;}for(;ip>='0'&&ip<='9';ip=getchar_unlocked())ret=ret*10+ip-'0';return flag*ret;}
  2. ld scan_ld() {int ip=getchar_unlocked(),flag=1;ld ret=0;for(;ip<'0'||ip>'9';ip=getchar_unlocked())if(ip=='-'){flag=-1;ip=getchar_unlocked();break;}for(;ip>='0'&&ip<='9';ip=getchar_unlocked())ret=ret*10+ip-'0';return flag*ret;}
  3. lld scan_lld() {int ip=getchar_unlocked(),flag=1;lld ret=0;for(;ip<'0'||ip>'9';ip=getchar_unlocked())if(ip=='-'){flag=-1;ip=getchar_unlocked();break;}for(;ip>='0'&&ip<='9';ip=getchar_unlocked())ret=ret*10+ip-'0';return flag*ret;}
  4. llu scan_llu() {int ip=getchar_unlocked();llu ret=0;for(;ip<'0'||ip>'9';ip=getchar_unlocked());for(;ip>='0'&&ip<='9';ip=getchar_unlocked())ret=ret*10+ip-'0';return ret;}
  5. //end of fast input
  6. //fast output
  7. //no line break
  8. void print_d(int n) {if(n<0){n=-n;putchar_unlocked('-');}int i=10;char output_buffer[10];do{output_buffer[--i]=(n%10)+'0';n/=10;}while(n);do{putchar_unlocked(output_buffer[i]);}while(++i<10);}
  9. void print_ld(ld n) {if(n<0){n=-n;putchar_unlocked('-');}int i=11;char output_buffer[11];do{output_buffer[--i]=(n%10)+'0';n/=10;}while(n);do{putchar_unlocked(output_buffer[i]);}while(++i<11);}
  10. void print_lld(lld n) {if(n<0){n=-n;putchar_unlocked('-');}int i=21;char output_buffer[21];do{output_buffer[--i]=(n%10)+'0';n/=10;}while(n);do{putchar_unlocked(output_buffer[i]);}while(++i<21);}
  11. void print_llu(llu n) {int i=21;char output_buffer[21];do{output_buffer[--i]=(n%10)+'0';n/=10;}while(n);do{putchar_unlocked(output_buffer[i]);}while(++i<21);}
power function

  1. ll power(ll a,ll b,ll mod){
  2. ll ans=1;
  3. while(b){
  4. if(b&1) ans=(ans*a)%mod;
  5. a=(a*a)%mod;
  6. b/=2;
  7. }
  8. return ans;
  9. }

Uploading and Running Lambda function in AWS

Main.go package main import ( "fmt" "encoding/json" "log" "github.com/aws/aws-lambda-g...