Solutoin of LightOJ 1224 - DNA Prefix

See the problem 1224 - DNA Prefix 

/* Bismillahir Rahmanir Rahim Solution using "Trie" */ #include<bits/stdc++.h> using namespace std; long long k, i=0, x, cur, last, ss, sss, ans, mx; string s; struct node{ int next[4]; long long cnt; }ar[2500109]; void new_trie(int cur){ ar[cur].next[0]=-1; ar[cur].next[1]=-1; ar[cur].next[2]=-1; ar[cur].next[3]=-1; ar[cur].cnt=1; } int insrt(){ ss=s.size(), cur=0; for(k=0; k<ss; k++){ if(s[k]=='A') x=0; else if(s[k]=='C')x=1; else if(s[k]=='G')x=2; else if(s[k]=='T')x=3; if(ar[cur].next[x]==-1){ ar[cur].next[x]=last; new_trie(last++); cur=ar[cur].next[x]; } else{ cur=ar[cur].next[x]; ar[cur].cnt++; mx=(k+1)*ar[cur].cnt; ans=max(mx, ans); } } sss=max(ss, sss); } int main(){ long long t, n, cs=1; cin>>t; while(t--){ ans=0, mx=0, last=1, sss=0; new_trie(0); cin>>n; while(n--){ cin>>s; i++; insrt(); } cout<<"Case "<<cs++<<": "<<max(ans, sss)<<endl; } return 0; }

Solution of LightOJ 1129 - Consistency Checker

View the problem 1129 - Consistency Checker

 

// Solution using "Trie"

#include<bits/stdc++.h>
using namespace std;
long long n, m, t, cs=1, i, j, last=1, xx, cur, k, x, fl;
string s;

struct trie{
    bool endmark;
    int next[11];
}r[100009];

void new_trie(int cur){
    for(int zz=0; zz<10; zz++) r[cur].next[zz]=-1;
    r[cur].endmark=false;
}

void insrt(){
    cur=0, k=s.size();
    for(int z=0; z<k; z++){
        x=(int)s[z]-48;
        if(r[cur].next[x]==-1){
            r[cur].next[x]=last;
            new_trie(last++);
            cur=r[cur].next[x];
        }
        else{
            cur=r[cur].next[x];
            if(r[cur].endmark==true)fl=1;
            if(z==k-1) fl=1;
        }
        if(fl==1)break;
    }
    r[cur].endmark=true;
}

int main(){
    cin>>t;
    while(t--){
        cin>>n;
        fl=0, last=1;
        new_trie(0);
        for(i=0; i<n; i++){
            cin>>s;
            insrt();
        }
        cout<<"Case "<<cs++<<": ";
        if(fl==1) cout<<"NO"<<endl;
        else cout<<"YES"<<endl;
    }
    return 0;
}
 

Solution of POJ 2001-Shortest Prefixes

See the problem  POJ 2001-Shortest Prefixes

    // Solution using "Trie"

    #include<iostream>
    #include<vector>
    #include<string>
    using namespace std;
    vector<string>vt;
    vector<string>::iterator it;

    long long i, k, sz, cur, last, x;
    string s;

    struct node{
        int next[26+1];
        int cnt;
    }ar[20109];

    void new_trie(int cur){
        for(int j=0; j<26; j++)ar[cur].next[j]=-1;
        ar[cur].cnt=1;
    }

    void insrt(){
        cur=0, sz=s.size();
        for(i=0; i<sz; i++){
            x=s[i]-'a';
            if(ar[cur].next[x]==-1){
                ar[cur].next[x]=last;
                new_trie(last++);
                cur=ar[cur].next[x];
            }
            else{
                cur=ar[cur].next[x];
                ar[cur].cnt++;
            }
        }
    }

    void fnd(){
        sz=s.size(), cur=0;
        for(i=0; i<sz; i++){
            x=s[i]-'a';
            cout<<s[i];
            cur=ar[cur].next[x];
            if(ar[cur].cnt==1) i=sz;
        }
    }

    int main()
    {
        new_trie(0);
        last=1;
        while(getline(cin, s)){
            if(s.size()==0) break;
            vt.push_back(s);
            insrt();
        }
        for(it=vt.begin(); it<vt.end(); it++){
            s=*it;
            cout<<s<<" ";
            fnd();
            cout<<endl;
        }
        return 0;
    }

Solution of UVa 11488-Hyper Prefix Sets

See the problem UVa-11488

 

>>>This problem has been solved using "Trie". So if you don't known with "Trie", you should not try to understand this solution.<<<

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll cur, last, ss, sss, ans, mx;
string s;

struct node{
    int next[2];
    long long cnt;
}ar[10000009];

void new_trie(int cur){
    ar[cur].next[0]=-1;
    ar[cur].next[1]=-1;
    ar[cur].cnt=1;
}

int insrt(){
    ss=s.size(), cur=0;
    for(int k=0; k<ss; k++){
        int x=(int)s[k]-48;
        if(ar[cur].next[x]==-1){
            ar[cur].next[x]=last;
            new_trie(last++);
            cur=ar[cur].next[x];
        }
        else{
            cur=ar[cur].next[x];
            ar[cur].cnt++;
            mx=(k+1)*ar[cur].cnt;
            ans=max(mx, ans);
        }
    }
    sss=max(ss, sss);
}

int main(){
    long long t, n;
    cin>>t;
    while(t--){
        ans=0, mx=0, last=1, sss=0;
        new_trie(0);
        cin>>n;
        while(n--){
            cin>>s;
            insrt();
        }
        cout<<max(ans, sss)<<endl;
    }
    return 0;
}

Solution of UVa 11362-Phone List

See the problem  UVa-11362

#include<bits/stdc++.h> using namespace std; long long n, t, i, last=1, cur, k, x, fl; string s; struct node{ bool endmark; int next[11]; }r[100009]; void new_trie(int cur){ for(int zz=0; zz<10; zz++){ r[cur].next[zz]=-1; } r[cur].endmark=false; } void insrt(){ cur=0, k=s.size(); for(int z=0; z<k; z++){ x=(int)s[z]-48; if(r[cur].next[x]==-1){ r[cur].next[x]=last; new_trie(last++); cur=r[cur].next[x]; } else{ cur=r[cur].next[x]; if(r[cur].endmark==true)fl=1; if(z==k-1) fl=1; } if(fl==1) break; } r[cur].endmark=true; } int main(){ cin>>t; while(t--){ cin>>n; fl=0, last=1; new_trie(0); for(i=0; i<n; i++){ cin>>s; insrt(); } if(fl==1) cout<<"NO"<<endl; else cout<<"YES"<<endl; } return 0; }

Solution of Uva 11504-Virtual Friend

See the problem UVa-11503

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

int ar[100009];
int par(int z){                // creating disjoint set
    if(ar[z]==z) return z;
    else return par(ar[z]);
}

int main()
{
    int t, i, n;
    string x, y;
    cin>>t;                    // test case
    while(t--){
        map<string, int>mp;    // for checking inserted person is new or old
        map<string, int>mpp;//indexing against person cope with the array position
        cin>>n;
        int l=0, arr[100009]={0};
        while(n--){
            cin>>x>>y;
            mp[x]++;
            mp[y]++;
            int ans=0;
            if(mp[x]==1&&mp[y]==1){   // when both person are new
                l++;
                mpp[x]=ar[l]=l;
                l++;
                mpp[y]=ar[l]=l;
                ans=arr[l]=2;
                ar[par(mpp[x])]=par(mpp[y]);
            }
            else if(mp[x]==1||mp[y]==1){     // when one person is new
                if(mp[x]==1){
                    l++;
                    mpp[x]=ar[l]=l;
                    ans=arr[par(mpp[y])] += 1;
                    ar[par(mpp[x])]=par(mpp[y]);
                }
                else{
                    l++;
                    mpp[y]=ar[l]=l;
                    ans=arr[par(mpp[y])] = (1+arr[par(mpp[x])]);
                    ar[par(mpp[x])]=par(mpp[y]);
                }
            }
            else{                             // when no one is new
             if((par(mpp[x])==mpp[y])||(par(mpp[y])==mpp[x])||(par(mpp[x])==par(mpp[y]))){
                    // if equal any person with another parent or both parents
                    ans=arr[par(mpp[x])];
                }
                else{
                    ans=arr[par(mpp[y])] += arr[par(mpp[x])];
                    ar[par(mpp[x])]=par(mpp[y]);
                }
            }
            cout<<ans<<endl;
        }
    }
    return 0;
}

Solution of UVa 10685-Nature

View the problem UVa 10685

#include<bits/stdc++.h>
using namespace std;
int ar[5005];

int par(int z){
    if(ar[z]==z) return z;
    else return par(ar[z]);
}

int  main()
{
    int i, n, m;
    string s, ss, sss;
    while(scanf("%d%d", &n, &m)){
        if(n==0&&m==0) break;
        map<string, int>mp;
        map<int, int>mpp;
        int ans=0;
        for(i=1; i<=n; i++){
            cin>>s;
            mp[s]=i;
            ar[i]=i;
        }
        for(i=0; i<m; i++){
            cin>>ss>>sss;
            ar[par(mp[ss])]=par(mp[sss]);
        }
        for(i=1; i<=n; i++){
            ar[i]=par(i);
            mpp[ar[i]]++;
            ans=max(ans, mpp[ar[i]]);
        }
        cout<<ans<<endl;
        scanf("\n");
    }
    return 0;
}

Selection Sort

সিলেকশন সর্ট-এ একটা (1 to n) লুপের মাধ্যমেই সর্ট কর যায় । এর জন্য, লুপের
1. প্রথম ধাপে, সবগুলা (1 to n) element এর ভেতর সবথেকে ছোট element-কে প্রথম element-এর সাথে interchange করতে হবে ।   [প্রথম element fixed]
2. দ্বিতীয় ধাপে, প্রথম element বাদে সবগুলা (2 to n) element এর ভেতর সবথেকে ছোট element-কে দ্বিতীয় element-এর সাথে interchange করতে হবে । [প্রথম দুইটা element fixed]
3. তৃতীয় ধাপে, প্রথম দুইটা element বাদে সবগুলা (3 to n) element এর ভেতর সবথেকে ছোট element-কে তৃতীয় element-এর সাথে interchange করতে হবে ।   [প্রথম তিনটা element fixed]
এভাবে (n-1)-তম element পর্যান্ত চলতে থাকবে । [n-তম element auto সর্টেড হয়ে যাবে]
এখন code দেখলে খুব সহজে বোঝা যাবে ……

Solution of UVa 10252-Common Permutation

See the problem 10252-Common Problem

1. #include<bits/stdc++.h>
2. using namespace std;
3. int main()
4. {
5.     string s, ss;
6.     int i, j, n, m;
7.     while(getline(cin, s)){
8.        getline(cin, ss);
9.        int ar[1000]={0}, arr[10000]={0};
10.         n=s.size();
11.         m=ss.size();
12.         for(i=0; i<n; i++) ar[(int)s[i]]++;
13.        for(i=0; i<m; i++) arr[i]=(int)ss[i];
14.        sort(arr, arr+m);
15.        for(i=0; i<m; i++){
16.            if(ar[arr[i]]){cout<<(char)arr[i]; ar[arr[i]]--;}
17.        }
18.        cout<<endl;
19.        s.clear(), ss.clear();
20.    }
21.    return 0;