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.

  

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; }

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; }

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; }