সোমবার, ২৯ জুলাই, ২০২৪

Factory Pattern

Factory Method is a creational design pattern that provides an interface for creating objects in a superclass but allows subclasses to alter the type of objects that will be created.

এই সময়ে কোন মন্তব্য নেই:

শনিবার, ২৭ জুলাই, ২০২৪

gRPC and REST API

gRPC : 

gRPC (gRPC Remote Procedure Call) is a modern, open-source framework developed by Google for making remote procedure calls. It uses Protocol Buffers (protobuf) as its interface definition language and data serialization format, allowing for efficient communication between services.
gRPC uses HTTP/2, which allows for multiplexing, reducing the latency and improving the performance compared to traditional HTTP/1.1 used by REST APIs. It also uses Protocol Buffers (protobuf) for data serialization, which is more efficient than JSON.

Pros:

  • Performance and Efficiency: gRPC uses HTTP/2, which allows for multiplexing, reducing the latency and improving the performance compared to traditional HTTP/1.1 used by REST APIs. It also uses Protocol Buffers (protobuf) for data serialization, which is more efficient than JSON
  • Bi-directional Streaming: gRPC supports client, server, and bi-directional streaming, enabling real-time communication and more efficient handling of large data transfers.
  • Cross-platform and Multi-Language Support
  • Built-in Error Handling and Metadata: gRPC has standardized mechanisms for handling errors and sending metadata
Cons:

  • Complexity: gRPC can be more complex to set up and understand, particularly for developers who are not familiar with Protocol Buffers and HTTP/2.
  • Limited Browser Support:
  • Less Human-Readable: Protocol Buffers are binary, which makes them less human-readable compared to the JSON format commonly used with REST APIs.

Use Cases:

  • High performance and efficiency are crucial, such as in microservices communication.
  • You need real-time communication features like streaming.
  • You have a polyglot environment where multiple programming languages are used.
  • You prefer a strongly typed schema and strict contract between client and server.

এই সময়ে কোন মন্তব্য নেই:

বৃহস্পতিবার, ১২ অক্টোবর, ২০২৩

Factorization with prime Sieve

  1. vector <int> prime; char sieve[1000009]; int N=1000009; void primeSieve ( ) { sieve[0] = sieve[1] = 1; prime.push_back(2); for ( int i = 4; i <= N; i += 2 ) sieve[i] = 1; int sqrtn = sqrt ( N ); for ( int i = 3; i <= sqrtn; i += 2 ) { if ( sieve[i] == 0 ) { for ( int j = i * i; j <= N; j += 2 * i ) sieve[j] = 1; } } for ( int i = 3; i <= N; i += 2 ) if ( sieve[i] == 0 ) prime.push_back(i); }
  2. vector <int> factors; void factorize( ll n ) { ll sqrtn = sqrt ( n ); for ( ll i = 0; i < prime.size() && prime[i] <= sqrtn; i++ ) { if ( n % prime[i] == 0 ) { while ( n % prime[i] == 0 ) { n /= prime[i]; factors.push_back(prime[i]); } sqrtn = sqrt ( n ); } } if ( n != 1 ) { factors.push_back(n); } }
এই সময়ে কোন মন্তব্য নেই:

বৃহস্পতিবার, ৩ মার্চ, ২০২২

Longest Increasing Subsequence & Path Print (LIS)

class Solution {

public:

    int lengthOfLIS(vector<int>& nums) {

        int n = nums.size();

        vector<int> sub, subIndex; 

        vector<int> path(n, -1); 

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

            if (sub.empty() || sub[sub.size() - 1] < nums[i]) {

                path[i] = sub.empty() ? -1 : subIndex[sub.size() - 1];

                sub.push_back(nums[i]);

                subIndex.push_back(i);

            } else {

                int idx = lower_bound(sub.begin(), sub.end(), nums[i]) - sub.begin();

                path[i] = idx == 0 ? -1 : subIndex[idx - 1];

                sub[idx] = nums[i];

                subIndex[idx] = i;

            }

        }

        vector<int> ans;

        int t = subIndex[subIndex.size() - 1];

        while (t != -1) {

            ans.push_back(nums[t]);

            t = path[t];

        }

        reverse(ans.begin(), ans.end());

        for(int i=0;i<ans.size();i++){

            cout<<ans[i]<<" ";

        }

        cout<<endl;

        return ans.size();

    }

};

এই সময়ে কোন মন্তব্য নেই:

শনিবার, ২৯ জানুয়ারি, ২০২২

Longest non-decreasing subsequence - TC: O(nlogn)

int longestNonDecresingSubsequenceLength(vector<int> a) {

    vector<int> s;

    s.push_back(a[0]);

    int n = a.size();

    int len = 1;

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

        int idx = upper_bound(s.begin(), s.end(), a[i]) - s.begin();

        int m = s.size();

        if (m > idx) {

            s[idx] = a[i];

        } else {

            s.push_back(a[i]);

        }

    }

    return s.size();

}

এই সময়ে কোন মন্তব্য নেই:

সোমবার, ৩০ আগস্ট, ২০২১

Mobius Inversion (Mobius Precalculate)

 const ll N=1e6+5;

ll lp[N];

ll mob[N];

void mobiusPreCalc(){

    mob[1] = 1;

    for (ll i = 2; i < N; ++i) {

        if (!lp[i]) for (ll j = i; j < N; j += i)

            if (!lp[j]) lp[j] = i;

        mob[i] = [](ll x) {

            ll cnt = 0;

            while (x > 1) {

                ll k = 0, d = lp[x];

                while (x % d == 0) {

                    x /= d;

                    ++k;

                    if (k > 1) return 0;

                }

                ++cnt;

            }

            if (cnt & 1) return -1;

            return 1;

        }(i);

    }

}




এই সময়ে কোন মন্তব্য নেই:

সোমবার, ২৩ আগস্ট, ২০২১

Detect Cycle and Print Cycle in an directed Graph

Problem :

https://leetcode.com/problems/course-schedule-ii/ 


class Solution {

public:

    vector<int>vis;

    vector<int>vec[5005];

    vector<int> ans;

    bool dfsAndReturnCycle(int src)

    {

        if(vis[src] == 1) 

            return true;

        if(vis[src] == 2) 

            return false;

        vis[src] = 1; 

        for (const auto& nextNode: vec[src])

        {

if(dfsAndReturnCycle(nextNode))

                return true;

        }

        vis[src] = 2;

        ans.push_back(src);

        return false;

        

    }

    vector<int> findOrder(int numCourses, vector<vector<int>>& ar) {

        int n=ar.size();

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

            int v=ar[i][0];

            int u=ar[i][1];

            vec[u].push_back(v);

        }

        int flag=0;

        vis = vector<int>(numCourses+2,0);

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

        {

            if(vis[i]==0){

                if(dfsAndReturnCycle(i))

                {

                    return {};

                }

            }

        }

        reverse(ans.begin(),ans.end());

        return ans;

    }

};

এই সময়ে কোন মন্তব্য নেই:

শুক্রবার, ৩০ এপ্রিল, ২০২১

FREQ2 - Most Frequent Value- Using Mo's Algorithm


You are given a sequence of n integers a0, a1, ..., an-1. You are also given several queries consisting of indices i and j (0 ≤ i ≤ j ≤ n-1). For each query, determine the number of occurrences of the most frequent value among the integers ai, ..., aj.


Mo's Algorithm Related Problem:

1) DQUERY - D-query , 2) FREQ2 - Most Frequent Value , 3) D. Cut and Stick  , 4) D. Powerful array , 5) Chef and Graph Queries 6) D. Tree and Queries 7) Sherlock and Inversions


   

 


///...................SUBHASHIS MOLLICK...................///

///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///

///.............ISLAMIC UNIVERSITY,BANGLADESH.............///

///....................SESSION-(14-15)....................///

#include<bits/stdc++.h>

using namespace std;

#pragma GCC target ("avx2")

#pragma GCC optimization ("O3")

#pragma GCC optimization ("unroll-loops")

#define sf(a) scanf("%d",&a)

#define sf2(a,b) scanf("%d %d",&a,&b)

#define sf3(a,b,c) scanf("%d %d %d",&a,&b,&c)

#define pf(a) printf("%d",a)

#define pf2(a,b) printf("%d %d",a,b)

#define pf3(a,b,c) printf("%d %d %d",a,b,c)

#define sfl(a) scanf("%lld",&a)

#define sfl2(a,b) scanf("%lld %lld",&a,&b)

#define sfl3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)

#define pfl(a) printf("%lld",a)

#define pfl2(a,b) printf("%lld %lld",a,b)

#define pfl3(a,b,c) printf("%lld %lld %lld",a,b,c)

#define nl printf("\n")

#define   timesave              ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

#define ll long long

#define pb push_back

#define MPI map<int,int>mp;

#define fr(i,n) for(i=0;i<n;i++)

#define fr1(i,n) for(i=1;i<=n;i++)

#define frl(i,a,b) for(i=a;i<=b;i++)

#define tz 100005

#define clr0(a) memset(a,0,sizeof(a))

#define clr1(a) memset(a,-1,sizeof(a))

#define space " "

#define yesp cout<<"YES"<<endl;

#define nop cout<<"NO"<<endl;

/*primes in range 1 - n

1 - 100(1e2) -> 25 pimes

1 - 1000(1e3) -> 168 primes

1 - 10000(1e4) -> 1229 primes

1 - 100000(1e5) -> 9592 primes

1 - 1000000(1e6) -> 78498 primes

1 - 10000000(1e7) -> 664579 primes

large primes ->

104729 1299709 15485863 179424673 2147483647 32416190071 112272535095293 48112959837082048697

*/

//freopen("Input.txt","r",stdin);

//freopen("Output.txt","w",stdout);

//const int fx[]={+1,-1,+0,+0};

//const int fy[]={+0,+0,+1,-1};

//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move

//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move

//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move

//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move

#define flagone(f) cout<<(f?"YES":"NO")<<endl;

#define flagzero(f) cout<<(f?"NO":"YES")<<endl;

int ar[tz],cnt[tz],ans[tz],freq[tz];

struct node

{

    int lft,right,index;

};

int mx=0;

node query[tz];

int blockSize=317;

bool cmp(node fst,node scnd)

{

    if(fst.lft/blockSize == scnd.lft/blockSize)

    {

        return fst.right/blockSize < scnd.right/blockSize;

    }

    return fst.lft<scnd.lft;

}

void addValue(int pos)

{

    cnt[ar[pos]]++;

    freq[cnt[ar[pos]]]++;

    mx=max(mx,cnt[ar[pos]]);

}

void removeValue(int pos)

{

    freq[cnt[ar[pos]]]--;

    if(freq[cnt[ar[pos]]]==0)

        mx--;

    cnt[ar[pos]]--;

}

main()

{

    timesave;

    //freopen("Input.txt","r",stdin);

    //freopen("Output.txt","w",stdout);

    int n,q,a,b;

    sf2(n,q);

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

    {

        sf(ar[i]);

    }

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

    {

        sf2(a,b);

        query[i].lft=a;

        query[i].right=b;

        query[i].index=i;

    }

    sort(query,query+q,cmp);

    int leftPointer = 0,rightPointer=0;

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

    {

        int leftValue = query[i].lft;

        int rightValue = query[i].right;

        int queryIndex = query[i].index;

        while(leftPointer<leftValue)

        {

            removeValue(leftPointer);

            leftPointer++;

        }

        while(leftPointer>leftValue)

        {

            addValue(leftPointer-1);

            leftPointer--;

        }

        while(rightPointer<=rightValue)

        {

            addValue(rightPointer);

            rightPointer++;

        }

        while(rightPointer>rightValue+1)

        {

            removeValue(rightPointer-1);

            rightPointer--;

        }

        ans[query[i].index]=mx;

        //cout<<leftValue<<" "<<rightValue<<" "<<mx<<endl;

    }

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

    {

        printf("%d\n",ans[i]);

    }

}

 

এই সময়ে কোন মন্তব্য নেই:

সোমবার, ৯ নভেম্বর, ২০২০

Dhaka Regional ACM ICPC 2016 Preleminary Contest Solution

F. Counter RMQ 


#include<bits/stdc++.h>

using namespace std;

int main()

{

    int ts,cs=1;

    cin>>ts;

    while(ts--)

    {

        int n,q,ar[20005]={0},i,j,a,b,x;

        cin>>n>>q;

        for(i=1;i<=q;i++)

        {

            cin>>a>>b>>x;

            for(j=a;j<=b;j++)

            {

                ar[j]=max(ar[j],x);

            }

        }

        printf("Case %d:",cs++);

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

        {

            if(ar[i]==0)

            {

                ar[i]=20000;

            }

            cout<<" "<<ar[i];

        }

        cout<<endl;

    }

    return 0;

}



I. Gadgets of Tomishu


#include <bits/stdc++.h>

#define sf1(a) scanf("%ld",&a)

#define sf2(a,b) scanf("%ld%ld",&a,&b);

#define sf3(a,b,c) scanf("%ld%ld%ld",&a,&b,&c);

using namespace std;

main()

{

    long ts,cs=1;

    sf1(ts);

    while(ts--)

    {

        long long i,ans,ar[100010]={0};

        long long n,k,mod;

        cin>>n>>k>>mod;

        //ar[0]=k%mod;

        ar[1]=((k%mod)*(k%mod))%mod ;

        ar[2]= ((ar[1]%mod) * (k%mod));



        for(i=3;i<=n;i++)

        {

           ar[i]=((ar[i-1]%mod) * (ar[i-2]%mod))%mod;

           //cout<<ar[i]<<" "<<ar[i-1]<<" "<<ar[i-2]<<endl;

        }

        ans=ar[n];


        printf("Case %ld: %lld\n",cs++,ans);

    }

}



এই সময়ে কোন মন্তব্য নেই:

রবিবার, ২ আগস্ট, ২০২০

Distinct numbers between a query

Problem Link: https://atcoder.jp/contests/abc174/tasks/abc174_e

Input:

10 10
2 5 6 5 2 1 7 9 7 2
5 5
2 4
6 7
2 2
7 8
7 9
1 8
6 9
8 10
6 8

Output:

1
2
2
1
2
2
6
3
3
3

#include<bits/stdc++.h>
using namespace std;
const int N = (int) 5e5 + 5;
struct query
{
    int l,r,id;
} q[N];
int a[N],k=1000,l=1,r=0;

bool compare(query &a,query &b)
{
    int b_a = a.l/k;
    int b_b = b.l/k;
    if(b_a==b_b)
        return a.r<b.r;

    return b_a<b_b;
}
int cnt[N],ans[N];
int res=0;
void add(int x)
{
    cnt[a[x]]++;
    if(cnt[a[x]]==1)
        ++res;
}
void remove(int x)
{
    cnt[a[x]]--;
    if(cnt[a[x]]==0)
        --res;
}

int main()
{
    int n,Q;
    cin>>n>>Q;
    for(int i=1; i<=n; ++i)
        cin>>a[i];
    for(int i=1; i<=Q; ++i)
    {
        cin>>q[i].l>>q[i].r;
        q[i].id=i;
    }
    sort(q+1,q+Q+1,compare);
    for(int i=1; i<=Q; ++i)
    {
        while(l > q[i].l)
            add(--l);
        while(r < q[i].r)
            add(++r);
        while(l < q[i].l)
            remove(l++);
        while(r > q[i].r)
            remove(r--);
        ans[q[i].id]=res;
    }

    for(int i=1; i<=Q; ++i)
    {
        printf("%d\n", ans[i]);
    }
    return 0;
}

এই সময়ে কোন মন্তব্য নেই:

শনিবার, ১১ জুলাই, ২০২০

LCA Problem

In this problem you have to find the maximum weight between a path.
Suppose in the sample test case 2 to  6 have a path 2->1->6
In here 2->1 the weight is 1 & 1->6 the weight is 2 so the maximum weight is MAX(1,2)=2
Again 5 to 2  there have a path 5->3->1->2
In here 5->3 the weight is 8 & 3->1 the weight is 5  & 1->2 the weight is 1 so the maximum weight is  MAX(8,5,1)=8
Input:
6
1 2 1
1 3 5
3 4 3
3 5 8
1 6 2
3
2 6
5 2
4 6
0


Output:
2
8
5

Problem Link: https://www.spoj.com/problems/NTICKETS/

Code:

///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%d",&a)
#define sf2(a,b) scanf("%d %d",&a,&b)
#define sf3(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pf(a) printf("%d",a)
#define pf2(a,b) printf("%d %d",a,b)
#define pf3(a,b,c) printf("%d %d %d",a,b,c)
#define sfl(a) scanf("%lld",&a)
#define sfl2(a,b) scanf("%lld %lld",&a,&b)
#define sfl3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pfl(a) printf("%lld",a)
#define pfl2(a,b) printf("%lld %lld",a,b)
#define pfl3(a,b,c) printf("%lld %lld %lld",a,b,c)
#define nl printf("\n")
#define   timesave              ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define pb push_back
#define MPI map<int,int>mp;
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
#define tz 100000
#define clr0(a) memset(a,0,sizeof(a))
#define clr1(a) memset(a,-1,sizeof(a))
/*primes in range 1 - n
1 - 100(1e2) -> 25 pimes
1 - 1000(1e3) -> 168 primes
1 - 10000(1e4) -> 1229 primes
1 - 100000(1e5) -> 9592 primes
1 - 1000000(1e6) -> 78498 primes
1 - 10000000(1e7) -> 664579 primes
large primes ->
104729 1299709 15485863 179424673 2147483647 32416190071 112272535095293 48112959837082048697
*/
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
#define N 100000
ll weight[20][N+5];
vector<pair<int,int> >vec[N+5];
int par[N+5],dis[N+5],vis[N+5],sparse[20][N+5];
void bfs(int src)
{
    dis[src]=0;
    par[src]=-1;
    queue<int>q;
    q.push(src);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=1;
        for(int i=0;i<vec[u].size();i++)
        {
            int v=vec[u][i].first,w=vec[u][i].second;
            if(vis[v]==0)
            {
                q.push(v);
                dis[v]=dis[u]+1;
                par[v]=u;
                weight[0][v]=w;
            }
        }
    }
}
void init()
{
    for(int i=1;i<=N;i++)
    {
        sparse[0][i]=par[ i ];
        for( int j = 1; 1 << j <= N; j++ )
        {
            sparse[j][i]=-1;
        }
    }
    for(int j=1;1<<j<=N;j++ )
    {
        for(int i=1;i<=N;i++)
        {
            sparse[j][i]=sparse[j-1][sparse[j-1][i]];
            weight[j][i]=max(weight[j-1][i],weight[j-1][sparse[j-1][i]]);
        }
    }
}
int lca( int u, int v )
{
    int lg=0;
    if(dis[u]<dis[v])
    {
        swap(u,v);
    }
    if(!dis[u])
    {
        return u;
    }
    for(lg=0;1<<lg<=dis[u];lg++);
    lg--;
    for(int i=lg;i>=0;i--)
    {
        if(dis[u]-(1<<i)>=dis[ v ] )
        {
            u=sparse[i][u];
        }
    }
    if(u==v)
    {
        return u;
    }
    for(int i=lg;i>=0;i--)
    {
        if(sparse[i][u]!=-1&&sparse[i][u]!=sparse[i][v])
        {
            u=sparse[i][u];
            v= sparse[i][v];
        }
    }
    return par[u];
}

long long query( int u, int v )
{
    int LCA=lca(u,v);
    int uv,uu;
    long long maxi=0;
    for(uv=0;1<<uv<=dis[v];uv++);
    uv--;
    for(uu=0;1<<uu<=dis[u];uu++);
    uu--;
    if(!dis[u]&&!dis[v])
    {
        return maxi;
    }
    for(int i=uu;i>=0;i--)
    {
        if(dis[u]-(1<<i)>=dis[LCA])
        {
            maxi=max(maxi,weight[i][u]);
            u=sparse[i][u];
        }
    }
    for(int i=uv;i>=0;i--)
    {
        if(dis[v]-(1<<i)>=dis[ LCA ] )
        {
            maxi = max( maxi,weight[i][v]);
            v=sparse[i][v];
        }
    }
    return maxi;
}
main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        if(n==0)
            break;
        for(int i=0;i<=N;i++)
        {
            vec[i].clear();
            par[i]=-1;
            dis[i]=0;
            vis[i]=0;
            for(int j=0;j<20;j++)
            {
                weight[j][i]=0;
                //sparse[j][i]=-1;
            }
        }
        int u,v,w;
        for(int i=1;i<n;i++)
        {
            sf3(u,v,w);
            vec[u].push_back({v,w});
            vec[v].push_back({u,w});
        }
        bfs(1);
        init();
        int q;
        sf(q);
        for(int i=1;i<=q;i++)
        {
            sf2(u,v);
            printf("%lld\n",query(u,v));
        }
    }
}

এই সময়ে কোন মন্তব্য নেই:

শুক্রবার, ২৬ জুন, ২০২০

Articulation Bridge Print

///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%d",&a)
#define sf2(a,b) scanf("%d %d",&a,&b)
#define sf3(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pf(a) printf("%d",a)
#define pf2(a,b) printf("%d %d",a,b)
#define pf3(a,b,c) printf("%d %d %d",a,b,c)
#define sfl(a) scanf("%lld",&a)
#define sfl2(a,b) scanf("%lld %lld",&a,&b)
#define sfl3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pfl(a) printf("%lld",a)
#define pfl2(a,b) printf("%lld %lld",a,b)
#define pfl3(a,b,c) printf("%lld %lld %lld",a,b,c)
#define nl printf("\n")
#define   timesave              ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define pb push_back
#define MPI map<int,int>mp;
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
#define tz 100000
#define clr0(a) memset(a,0,sizeof(a))
#define clr1(a) memset(a,-1,sizeof(a))
/*primes in range 1 - n
1 - 100(1e2) -> 25 pimes
1 - 1000(1e3) -> 168 primes
1 - 10000(1e4) -> 1229 primes
1 - 100000(1e5) -> 9592 primes
1 - 1000000(1e6) -> 78498 primes
1 - 10000000(1e7) -> 664579 primes
large primes ->
104729 1299709 15485863 179424673 2147483647 32416190071 112272535095293 48112959837082048697
*/
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
vector<int>vec[100005];
vector<pair<int,int> >bridge;
int id[100005],low[1000005],vis[100005],somoy;
void dfs(int uu,int par)
{
    low[uu]=id[uu]=++somoy;
    vis[uu]=1;
    for(int ii=0;ii<vec[uu].size();ii++)
    {
        int vv=vec[uu][ii];
        if(vv==par)
        {
            continue;
        }
        if(vis[vv]==0)
        {
            dfs(vv,uu);
            low[uu]=min(low[uu],low[vv]);
            if(id[uu]<low[vv])
            {
                bridge.push_back({min(uu,vv),max(uu,vv)});
            }
        }
        else
        {
            low[uu]=min(low[uu],id[vv]);
        }
    }
}
main()
{
    timesave;
    int n,m;
    while(cin>>n>>m)
    {
        if(n==0&&m==0)
            break;
        int i,u,v;
        memset(vis,0,sizeof(vis));
        for(i=1;i<=m;i++)
        {
            cin>>u>>v;
            vec[u].push_back(v);
            vec[v].push_back(u);
        }
        somoy=0;
        for(i=1;i<=n;i++)
        {
            if(vis[i]==0)
            {
                dfs(i,-1);
            }
        }
        for(i=0;i<bridge.size();i++)
        {
            cout<<bridge[i].first<<" "<<bridge[i].second<<endl;
        }
        bridge.clear();
        for(i=1;i<=n;i++)
        {
            vec[i].clear();
        }
    }
}


/*
INPUT:
6 5
1 2
2 3
2 4
2 5
4 5

4 2
1 2
2 3


OUTPUT:
2 3
1 2

1 2
2 3
*/
এই সময়ে কোন মন্তব্য নেই:

বুধবার, ২৪ জুন, ২০২০

Articulation Point

Problem Link:
https://www.spoj.com/problems/SUBMERGE/en/

Hints: Find how many articulation point in the graph

Solution

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

const int maxn=1e4+4;
vector<int>vec[maxn];
bool visit[maxn];
int parent[maxn];
int low[maxn];
set<int>ap;
int disc[maxn];
int timee;
void ArticulationPoint(int u)
{
    int child=0;
    visit[u]=1;
    disc[u]=low[u]=++timee;
    for(int i=0; i<vec[u].size(); i++)
    {
        int v=vec[u][i];
        if(visit[v]==0)
        {
            child++;
            parent[v]=u;
            ArticulationPoint(v);
            low[u]=min(low[u],low[v]);
            if(parent[u]==-1&&child>1)
                ap.insert(u);
            if(parent[u]!=-1&&low[v]>=disc[u])
                ap.insert(u);
        }
        else if(v!=parent[u])
            low[u]=min(low[u],disc[v]);
    }
}
int main()
{
    //freopen("t.txt","r",stdin);
    int n,m,u,v;
    while(scanf("%d%d",&n,&m))
    {
        if(!n&&!m)
            break;
        memset(parent,-1,sizeof parent);
        memset(visit,0,sizeof visit);
        for(int i=0; i<n+1; i++)
            vec[i].clear();
        for(int i=0; i<m; i++)
        {
            scanf("%d%d",&u,&v);
            vec[u].push_back(v);
            vec[v].push_back(u);
        }
        for(int i=0; i<n; i++)
        {
            if(visit[i]==0)
            {
                timee=0;
                ArticulationPoint(i);
            }
        }
        printf("%d\n",ap.size());
        ap.clear();
    }
}

এই সময়ে কোন মন্তব্য নেই:

বৃহস্পতিবার, ১১ জুন, ২০২০

UVA 11709 - Trust groups

///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%d",&a)
#define sf2(a,b) scanf("%d %d",&a,&b)
#define sf3(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pf(a) printf("%d",a)
#define pf2(a,b) printf("%d %d",a,b)
#define pf3(a,b,c) printf("%d %d %d",a,b,c)
#define sfl(a) scanf("%lld",&a)
#define sfl2(a,b) scanf("%lld %lld",&a,&b)
#define sfl3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pfl(a) printf("%lld",a)
#define pfl2(a,b) printf("%lld %lld",a,b)
#define pfl3(a,b,c) printf("%lld %lld %lld",a,b,c)
#define nl printf("\n")
#define   timesave              ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define pb push_back
#define MPI map<int,int>mp;
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
#define tz 100000
#define clr0(a) memset(a,0,sizeof(a))
#define clr1(a) memset(a,-1,sizeof(a))
/*primes in range 1 - n
1 - 100(1e2) -> 25 pimes
1 - 1000(1e3) -> 168 primes
1 - 10000(1e4) -> 1229 primes
1 - 100000(1e5) -> 9592 primes
1 - 1000000(1e6) -> 78498 primes
1 - 10000000(1e7) -> 664579 primes
large primes ->
104729 1299709 15485863 179424673 2147483647 32416190071 112272535095293 48112959837082048697
*/
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
vector<int>vec[1010],ultavec[1010],dhokalam;
int vis[1010];
void dfs(int u)
{
    vis[u]=1;
    for(int ii=0; ii<vec[u].size(); ii++)
    {
        int v=vec[u][ii];
        if(vis[v]==0)
            dfs(v);
    }
    dhokalam.push_back(u);
}
void dfs1(int u)
{
    vis[u]=1;
    for(int ii=0; ii<ultavec[u].size(); ii++)
    {
        int v=ultavec[u][ii];
        if(vis[v]==0)
            dfs1(v);
    }
}
main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        if(n==0&&m==0)
            break;
        getchar();
        string s,s1;
        int i;
        map<string,int>mp;
        for(i=1;i<=n;i++)
        {
            vec[i].clear();
            ultavec[i].clear();
        }
        dhokalam.clear();
        for(i=1;i<=n;i++)
        {
            getline(cin,s);
            mp[s]=i;
        }
        for(i=1;i<=m;i++)
        {
            getline(cin,s);
            getline(cin,s1);
            int a=mp[s],b=mp[s1];
            vec[a].push_back(b);
            ultavec[b].push_back(a);
        }
        memset(vis,0,sizeof(vis));
        for(i=1; i<=n; i++)
        {
            if(vis[i]==0)
            {
                dfs(i);
            }
        }
        memset(vis,0,sizeof(vis));
        int cnt=0;
        for(i=dhokalam.size()-1; i>=0; i--)
        {
            if(vis[dhokalam[i]]==0)
            {
                cnt++;
                dfs1(dhokalam[i]);
            }
        }
        cout<<cnt<<endl;

    }

}


এই সময়ে কোন মন্তব্য নেই:

UVA 12926 - Trouble in Terrorist Town

///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%d",&a)
#define sf2(a,b) scanf("%d %d",&a,&b)
#define sf3(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pf(a) printf("%d",a)
#define pf2(a,b) printf("%d %d",a,b)
#define pf3(a,b,c) printf("%d %d %d",a,b,c)
#define sfl(a) scanf("%lld",&a)
#define sfl2(a,b) scanf("%lld %lld",&a,&b)
#define sfl3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pfl(a) printf("%lld",a)
#define pfl2(a,b) printf("%lld %lld",a,b)
#define pfl3(a,b,c) printf("%lld %lld %lld",a,b,c)
#define nl printf("\n")
#define   timesave              ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define pb push_back
#define MPI map<int,int>mp;
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
#define tz 100000
#define clr0(a) memset(a,0,sizeof(a))
#define clr1(a) memset(a,-1,sizeof(a))
/*primes in range 1 - n
1 - 100(1e2) -> 25 pimes
1 - 1000(1e3) -> 168 primes
1 - 10000(1e4) -> 1229 primes
1 - 100000(1e5) -> 9592 primes
1 - 1000000(1e6) -> 78498 primes
1 - 10000000(1e7) -> 664579 primes
large primes ->
104729 1299709 15485863 179424673 2147483647 32416190071 112272535095293 48112959837082048697
*/
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
vector<int>vec[5050],ultavec[5050],dhokalam;
int vis[5050],ar[5050][5050];
void dfs(int u)
{
    vis[u]=1;
    for(int ii=0; ii<vec[u].size(); ii++)
    {
        int v=vec[u][ii];
        if(vis[v]==0)
            dfs(v);
    }
    dhokalam.push_back(u);
}
void dfs1(int u)
{
    vis[u]=1;
    for(int ii=0; ii<ultavec[u].size(); ii++)
    {
        int v=ultavec[u][ii];
        if(vis[v]==0)
            dfs1(v);
    }
}
main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        int i,j,a,b;
        for(i=1;i<=n;i++)
        {
            vec[i].clear();
            ultavec[i].clear();
            for(j=1;j<=n;j++)
            {
                ar[i][j]=1;
                ar[j][i]=1;

            }
        }
        dhokalam.clear();
        for(i=1;i<=m;i++)
        {
            sf2(a,b);
            ar[a][b]=0;
        }
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                if(ar[i][j])
                {
                    vec[i].push_back(j);
                    ultavec[j].push_back(i);
                }
            }
        }
        memset(vis,0,sizeof(vis));
        for(i=1; i<=n; i++)
        {
            if(vis[i]==0)
            {
                dfs(i);
            }
        }
        memset(vis,0,sizeof(vis));
        int cnt=0;
        for(i=dhokalam.size()-1; i>=0; i--)
        {
            if(vis[dhokalam[i]]==0)
            {
                //cout<<dhokalam[i]<<endl;
                cnt++;
                dfs1(dhokalam[i]);
            }
        }
        int cost;
        sf(cost);
        pf(cnt*cost);
        nl;

    }

}


এই সময়ে কোন মন্তব্য নেই:

বুধবার, ১০ জুন, ২০২০

12645 - Water Supply (SCC)

Blog Link for Hints:
https://asdfcoding.wordpress.com/2014/04/24/12645-water-supply-uva/



///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%d",&a)
#define sf2(a,b) scanf("%d %d",&a,&b)
#define sf3(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pf(a) printf("%d",a)
#define pf2(a,b) printf("%d %d",a,b)
#define pf3(a,b,c) printf("%d %d %d",a,b,c)
#define sfl(a) scanf("%lld",&a)
#define sfl2(a,b) scanf("%lld %lld",&a,&b)
#define sfl3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pfl(a) printf("%lld",a)
#define pfl2(a,b) printf("%lld %lld",a,b)
#define pfl3(a,b,c) printf("%lld %lld %lld",a,b,c)
#define nl printf("\n")
#define   timesave              ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define pb push_back
#define MPI map<int,int>mp;
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
#define tz 100000
#define clr0(a) memset(a,0,sizeof(a))
#define clr1(a) memset(a,-1,sizeof(a))
/*primes in range 1 - n
1 - 100(1e2) -> 25 pimes
1 - 1000(1e3) -> 168 primes
1 - 10000(1e4) -> 1229 primes
1 - 100000(1e5) -> 9592 primes
1 - 1000000(1e6) -> 78498 primes
1 - 10000000(1e7) -> 664579 primes
large primes ->
104729 1299709 15485863 179424673 2147483647 32416190071 112272535095293 48112959837082048697
*/
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
vector<int>vec[1100],dhokalam;
int vis[1100];
void dfs(int u)
{
    vis[u]=1;
    for(int ii=0; ii<vec[u].size(); ii++)
    {
        int v=vec[u][ii];
        if(vis[v]==0)
            dfs(v);
    }
    dhokalam.push_back(u);
}
void dfs1(int u)
{
    vis[u]=1;
    for(int ii=0; ii<vec[u].size(); ii++)
    {
        int v=vec[u][ii];
        if(vis[v]==0)
            dfs1(v);
    }
}
main()
{
    int n,m;
    while(cin>>n>>m)
    {
        int i,a,b,cnt=0;
        for(i=0; i<=n; i++)
        {
            vec[i].clear();
        }
        dhokalam.clear();
        for(i=1; i<=m; i++)
        {
            cin>>a>>b;
            if(b==0)
                continue;
            vec[a].push_back(b);
        }

        memset(vis,0,sizeof(vis));
        for(i=0; i<=n; i++)
        {
            if(vis[i]==0)
            {
                dfs(i);
            }
        }
        memset(vis,0,sizeof(vis));
        for(i=dhokalam.size()-1; i>=0; i--)
        {
            if(vis[dhokalam[i]]==0)
            {
                //cout<<dhokalam[i]<<endl;
                cnt++;
                dfs1(dhokalam[i]);
            }
        }
        cout<<cnt-1<<endl;

    }

}


এই সময়ে কোন মন্তব্য নেই:

শুক্রবার, ৫ জুন, ২০২০

Light oj Problem no:1003 ( Detect Cycle or Not)

Problem Link: http://lightoj.com/volume_showproblem.php?problem=1003



///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%lld",&a)
#define sf2(a,b) scanf("lld",&a,&b)
#define sf3(a,b,c) scanf("lld%lld",&a,&b,&c)
#define pf(a) printf("%lld",a)
#define pf2(a,b) printf("lld",a,b)
#define pf3(a,b,c) printf("lld%lld",a,b,c)
#define nl printf("\n")
#define ll long long
#define pb push_back
#define MPI map<int,int>mp
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
#define M 100005
int visited[M], cycle = 0;
vector<int>vec[M];
void dfs(int u)
{
    int i;
    visited[u]=1;
    if (cycle==1)
        return;
    for (i=0; i<vec[u].size(); i++)
    {
        int v=vec[u][i];
        if (visited[v]==1)
        {
            cycle=1;
            return;
        }
        else if (visited[v]==0)
        {
            dfs(v);
        }
    }
    visited[u]=2;
}
main()
{
    int ts,cs=1;
    cin>>ts;
    while(ts--)
    {

        int m;
        cin>>m;
        int i,u,v,cnt=1;
        string s,s1;
        map<string,int>mp;
        for (i=0; i<10010; i++)
        {
            vec[i].clear();
            visited[i]=0;
        }
        for(i=1; i<=m; i++)
        {
            cin>>s>>s1;
            if(mp[s]==0)
            {
                mp[s]=cnt;
                cnt++;
            }
            u=mp[s];
            if(mp[s1]==0)
            {
                mp[s1]=cnt;
                cnt++;
            }
            v=mp[s1];
            vec[u].push_back(v);
        }
        cycle=0;
        for(i=1; i<=cnt; i++)
        {
            if(visited[i]==0)
            {
                dfs(i);
            }
        }
        if(cycle==1)
        {
            printf("Case %d: No\n",cs++);
        }
        else
            printf("Case %d: Yes\n",cs++);
    }
}

এই সময়ে কোন মন্তব্য নেই:

রবিবার, ২৪ মে, ২০২০

String Stream C++

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int ts;
    cin>>ts;
    getchar();
    while(ts--)
    {
        string s; ///char s[100];
        getline(cin,s); ///gets(s);
        stringstream ss;
        ss<<s;
        int num,ar[100]={0},ind=0;
        while(ss>>num)
        {
            ar[ind]=num;
            ind++;
        }
        for(int i=0;i<ind;i++)
        {
            cout<<ar[i]<<endl;
        }
    }
    return 0;
}

এই সময়ে ৩টি মন্তব্য:

বৃহস্পতিবার, ২৬ মার্চ, ২০২০

11475 Extend to Palindrome By Using KMP algo

#include <bits/stdc++.h>
using namespace std;
int b[300010];
void kmpPreprocess(string P, int m)
{
    int i = 0, j = -1;
    b[0] = -1;
    while (i < m)
    {
        while (j >= 0 && P[i] != P[j])
        {
            j = b[j];
        }
        i++;
        j++;
        b[i] = j;
    }
}
int main()
{
string s,ss;
while(cin>>s)
{
int x=s.size();
        ss=s;
        reverse(s.begin(),s.end());
        s=s+"~"+ss;
        int m=s.size();
        kmpPreprocess(s, m);
        for(int i=b[m-1]+1;i<x;i++)
            ss+=s[i];
        cout<<ss<<endl;
}
    return 0;
}
এই সময়ে কোন মন্তব্য নেই:

UVA 455 Periodic Strings by using Z algo

#include <bits/stdc++.h>
using namespace std;
vector<int> ans;
int z[500];
void Z_algo(string s)
{
    int n = s.length();
    z[0] = 0;
    for(int i = 1, l = 0, r = 0;i<n;i++)
    {
        if(i<=r) z[i] = min(r-i+1, z[i-l]);
        else z[i] = 0;
        while(z[i]+i<n && s[z[i]]==s[z[i]+i]) ++z[i];
        if(z[i]+i-1>r) l = i, r = z[i]+i-1;
    }
}
int main()
{
int ts,cs=1;
cin>>ts;
while(ts--)
{
if(cs>1)
cout<<endl;
cs++;
    string s;
    cin>>s;
        Z_algo(s);
        int n = s.length();
        int mx = n;
for (int i = 1; i < n; ++i)
{
if (n % i == 0 and z[i] + i == n)
{
mx = i;
break;
}
}
cout<<mx<<endl;
        memset(z,0,sizeof(z));
    }
    return 0;
}
এই সময়ে কোন মন্তব্য নেই:
এতে সদস্যতা: পোস্টগুলি (Atom)

Factory Pattern

Factory Method  is a creational design pattern that provides an interface for creating objects in a superclass but allows subclasses to alte...

  • Compute sum of digits in all numbers from 1 to n
    Sum of digits of a range(suppose 1-10 ans is 46,1-9 ans is 45) #include<stdio.h> #include<algorithm> #include<iostream...
  • LOJ 1348 - Aladdin and the Return Journey
    এখানে একটা গ্রাফ দেওয়া থাকবে এখন দুইটা অপারেশন দেবে অপারেসনে বলবে যে ১ দিলে i নাম্বার নোডে  V আপডেট হবে আর ০ দিলে i to j এর মধ্যে  টোটাল ...
  • UVA 13055 - Inception
    #include<bits/stdc++.h> using namespace std; main() {       long n,k=0;      string s2[100];       cin>>n;       while(n...