Monday, October 23, 2017

Clear Idea of Lazy Propagation (Segment Tree)

Segment Tree শেখার জন্য শাফায়েত ভাইয়ের এই টিউটোরিয়াল বেশ সহজ।

If you know already Segment Tree and Lazy Propagation it will be helpful for you. In the following picture the updating system is described.
  

Thursday, October 19, 2017

Implementation of Segment Tree

/* Creating a segment tree. Then with the query()
we can easily find the sum of any segment of the tree.
*/

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

#define fi(a, b) for(int i=a; i<=b; i++)
#define fd(a, b) for(int i=a; i>=b; i--)

int n, m, ar[mx], tree[mx*3], ii, jj;

void segmentt(int node, int st, int en){
    if(st==en){
        tree[node]=ar[st];
        return ;
    }
    int left=node*2;
    int right=node*2+1;
    int mid=(st+en)/2;
    segmentt(left, st, mid);
    segmentt(right, mid+1, en);
    tree[node]=tree[left]+tree[right];
}

int query(int node, int st, int en){
    if(ii<=st && jj>=en) return tree[node];  // relevant segment
    else if(ii>en || jj<st) return 0;        // out of the segment
    else{                                    // needs to divide again
        int left=2*node, right=node*2+1, mid=(st+en)/2;
        return (query(left, st, mid) + query(right, mid+1, en));
    }
}

int main(){
    cin>>n;
    fi(1, n)
        cin>>ar[i];
    segmentt(1, 1, n);
    cin>>m;
    fi(1, m){
        cin>>ii>>jj;
        cout<<query(1, 1, n)<<endl;
    }
    return 0;
}

Print Longest Common Substring

/* You are given two string. Find the Largest
Common Substring (not Subsequence).
First, insert all the suffix (suffix of "suffix" are "x",
"ix"......"suffix") of the first string in the "Trie",
then check with the all the second-string-suffix's.
*/

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

int cnt=1, ans=0, st=0;
string s, ss;

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

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

void insert(){  // Inserting the first string
    int sz=s.size(), cur=0, x;
    for(int i=0; i<sz; i++){
        x=s[i]-'a';
        if(ar[cur].next[x]==-1){
            ar[cur].next[x]=cnt;
            new_trie(cnt++);
        }
        cur=ar[cur].next[x];
    }
}

void find(int stt){  // Checking with the second string
    int sz=s.size(), cur=0, x, c=0;
    for(int i=0; i<sz; i++){
        x=s[i]-'a';
        if(ar[cur].next[x]==-1)
            break;
        cur=ar[cur].next[x];
        c++;
    }
    if(c>ans){  // when larger counter(c) is found
        st=stt;
        ans=c;
    }
}

int main(){
    int sz;
    new_trie(0);
    cin>>ss;   // First String
    sz=ss.size();
    for(int i=1; i<=sz; i++){
        s="";
        for(int ii=sz-i; ii<sz; ii++)
            s+=ss[ii];
        insert();
    }

    cin>>ss;  // Second String
    sz=ss.size();
    for(int i=1; i<=sz; i++){
        s="";
        for(int ii=sz-i; ii<sz; ii++)
            s=s+ss[ii];
        find(sz-i);
    }
    for(int i=st, cc=1; cc<=ans; i++, cc++)
        cout<<ss[i];
    return 0;
}

Friday, April 28, 2017

Solution of DevSkill DCP-316: Names

See the problem: DCP-316: Names

/*  Bismillahir Rahmanir Rahim 
    Its just a string multiplication.
*/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a, i, j, n, t, z, sz, ar[1000001];
string s;

void multiply(int i){  // string multiplication
    int carry=0, j;
    for(j=10000; j>10000-z; j--){
        int temp=ar[j]*i+carry;
        ar[j]=temp%10;
        carry=temp/10;
    }
    while(carry){
        ar[j--]=carry%10;
        carry=carry/10;
        z++;
    }
}

int main(){

    cin>>t;
    while(t--){
        cin>>n>>s;
        sz=s.size();
        ar[10000]=1;
        n=n-sz, z=1;
        for(i=1; i<=n; i++){
            multiply(26);
        }
        for(i=10001-z; i<=10000; i++) cout<<ar[i];
        cout<<endl;
    }
    return 0;
}

Calculating Average Using OOP (C++)

# include<iostream>
#include<conio.h>
using namespace std;

class array{
    float *f_a;
    public:
    array(int);
    ~array();
    void getdata(int);
    float average(int);
};

array::array(int k){
    f_a=new float[k];
    if(!f_a){
        cout<<"Allocation failure."<<endl;
    }
}

array::~array(){
    delete[]f_a;
}

void array::getdata(int l){
    cout<<"Enter "<<l<<" elements: ";
    for(int i=0; i<l;i++){
        cin>>f_a[i];
    }
}

float array::average(int m){
    float sum;
    for(int j=0;j<m;j++){
        sum+=f_a[j];
    }
    return(sum/m);
}

int main(){
    int n;
    cout<<"Number of elements: ";
    cin>>n;
    array f(n);
    f.getdata(n);
    cout<<"The average is: "<<f.average(n)<<endl;
    return 0;
}

Solution of Dev Skill DCP-237: What a problem!

See the problem:  DCP-237: What a problem!

/*  Bismillahir Rahmanir Rahim
    Its better to try yourself than follow others code.
    My solution Idea: 
    To store the array use one dimensional array 
    Now print according to their system. 
 */
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll i, j, n, k, cs=1, m, t, x, sz,  ar[1000006];

int main(){
     cin>>t;
     while(t--){
        cin>>n;
        k=1;
        for(i=1; i<=n; i++){
            for(j=1; j<=n; j++) cin>>ar[k++];
        } 
        cout<<"Case #"<<cs++<<": ";
        m=n+1;
        x=n*n-(n-1);
        if(n==1) cout<<ar[1];
        else{
            cout<<ar[x];
            for(i=1; ; i++){
                x++;
                cout<<" "<<ar[x];
                for(j=1; j<=i; j++){
                    x=x-m;
                    cout<<" "<<ar[x];
                }
                if(x==1||x==n*n) break;
                i++;
                x=x-n;
                cout<<" "<<ar[x];
                for(j=1; j<=i; j++){
                    x=x+m;
                    cout<<" "<<ar[x];
                }
                if(x==1||x==n*n) break;
            }
            if(x==1){
                for(i=2; ; i++){
                    x++;
                    cout<<" "<<ar[x];
                    if(x==n) break;
                    for(j=i; j<n; j++){
                        x=x+m;
                        cout<<" "<<ar[x];
                    }
                    if(x==n) break;
                    x=x-n;
                    cout<<" "<<ar[x];
                    if(x==n) break;
                    i++;
                    for(j=i; j<n; j++){
                        x=x-m;
                        cout<<" "<<ar[x];
                    }
                    if(x==n) break;
                }
            }
            else{
                for(i=2; i<n; i++){
                    if(x==n) break;
                    x=x-n;
                    cout<<" "<<ar[x];
                    for(j=i; j<n; j++){
                        x=x-m;
                        cout<<" "<<ar[x];
                    }
                    if(x==n) break;
                    x++;
                    cout<<" "<<ar[x];
                    if(x==n) break;
                    i++;
                    for(j=i; j<n; j++){
                        x=x+m;
                        cout<<" "<<ar[x];
                    }
                    if(x==n) break;
                }
            }
        }
        cout<<endl;
     }
    return 0;
}

Monday, April 24, 2017

Selection Sort - Implementation with C++

/*  Bismillahir Rahmanir Rahim
    Implementation of Selection-Sort using C++
*/
#include<bits/stdc++.h>
using namespace std;

int main(){
    int ar[1000], i, j, n, temp, loc, mn;
    cin>>n; // Enter the number of element
    for(i=0; i<n; i++) cin>>ar[i]; // all elements
    for(i=0; i<n-1; i++){
        mn=ar[i]; // let, its the minimum
        loc=i;    // location of minimum
        for(j=i+1; j<n; j++){
            if(ar[j]<mn){
                mn=ar[j]; // minimum updated
                loc=j;    // location of minimum
            }
        }
        temp=ar[i];
        ar[i]=ar[loc];
        ar[loc]=temp;
    }
    for(i=0; i<n; i++) cout<<ar[i]<<" ";
    cout<<endl;
    return 0;
}

Bubble Sort - Implementation with C++

/*  Bismillahir Rahmanir Rahim
    Implementation of Bubble-Sort using C++
*/
#include<bits/stdc++.h>
using namespace std;

int main(){
    int a[50],n,i,j,temp;
    cin>>n; // Enter the number of element
    for(i=0; i<n; i++) cin>>a[i]; // Enter all elements
    for(i=1; i<n; i++){
        for(j=0; j<(n-i); j++){
            if(a[j]>a[j+1]){
                temp=a[j];
                a[j]=a[j+1];
                a[j+1]=temp;
            }
        }
    }
    for(i=0; i<n; i++) cout<<a[i]<<" ";
    cout<<endl;
    return 0;
}