/* 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;
}
|
Showing posts with label Solutions. Show all posts
Showing posts with label Solutions. Show all posts
Thursday, October 19, 2017
Implementation of Segment Tree
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;
}
|
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;
}
|
Quick Sort - Implementation with C++
/* Bismillahir Rahmanir Rahim
Implementation of Quick-Sort using C++
*/
#include<bits/stdc++.h>
using namespace std;
int ar[1000];
int partition (int low, int high){
int pivot=ar[high];
int i=(low-1);
for(int j=low; j<high; j++){
if(ar[j]<=pivot){
i++;
swap(ar[i],ar[j]);
}
}
swap(ar[i+1], ar[high]);
return (i+1);
}
void quickSort(int low, int high){
if(low<high){
int pi=partition(low, high);
quickSort(low, pi-1);
quickSort(pi+1, high);
}
}
int main(){
int n,i;
cin>>n;
for(i=0;i<n;i++) cin>>ar[i];
quickSort(0, n-1);
for(i=0; i<n; i++) cout<<ar[i]<<" ";
cout<<endl;
return 0;
}
|
Merge Sort - Implementation with C++
/* Bismillahir Rahmanir Rahim
Implementation of Merge Sort using C++
*/
#include<bits/stdc++.h>
using namespace std;
int ar[1000];
int marg_partition(int st, int mid , int ed){
int arr[1000], left, right, j=0, i;
left=st;
right=mid+1;
while(left<=mid && right<=ed){
if(ar[left]<ar[right]){
arr[j++]=ar[left];
left++;
}
else{
arr[j++]=ar[right];
right++;
}
}
if(left>mid){
for(i=right;i<=ed;i++)
arr[j++]=ar[i];
}
else {
for(i=left;i<=mid;i++)
arr[j++]=ar[i];
}
for(i=0;i<j;i++) ar[i+st]=arr[i];
return 0;
}
int marg_sort(int st,int ed){
if(st<ed){
int mid=(st+ed)/2;
marg_sort(st,mid);
marg_sort(mid+1,ed);
marg_partition(st,mid,ed);
}
}
int main(){
int i,j,n,k;
cin>>n;
for(i=0;i<n;i++) cin>>ar[i];
marg_sort(0,n-1);
for(i=0;i<n;i++) cout<<ar[i]<<" ";
cout<<endl;
return 0;
}
|
Insertion Sort - C++ Implementation
Try to understand the following procedure.
77 33 44 11 88 22 66 55
33 77 . . . . . . . . . . . . . . . . . .
33 44 77 . . . . . . . . . . . . . . .
11 33 44 77 . . . . . . . . . . . .
11 33 44 77 88 . . . . . . . . .
11 22 33 44 77 88 . . . . . .
11 22 33 44 66 77 88 . . .
11 22 33 44 55 66 77 88
The following Code represent the concept.
77 33 44 11 88 22 66 55
33 77 . . . . . . . . . . . . . . . . . .
33 44 77 . . . . . . . . . . . . . . .
11 33 44 77 . . . . . . . . . . . .
11 33 44 77 88 . . . . . . . . .
11 22 33 44 77 88 . . . . . .
11 22 33 44 66 77 88 . . .
11 22 33 44 55 66 77 88
The following Code represent the concept.
/* Bismillahir Rahmanir Rahim
Implementation of Insertion Sort using C++
*/
#include<bits/stdc++.h>
using namespace std;
int main(){
int ar[100000], n, i, j, key;
cin>>n; // number of elements
for(i=0; i<n; i++) cin>>ar[i]; // input elements one by one
for(i=1; i<n; i++){ // starting from 2nd element
key=ar[i];
j=i-1;
while(j>=0 && key<ar[j]){ //comparing key with all previous
ar[j+1]=ar[j];
j--;
}
ar[j+1]=key;
}
for(i=0;i<n;i++) cout<<ar[i]<<" ";
return 0;
}
|
Friday, April 7, 2017
Random Value Generator in C++
/* Bismillahir Rahmanir Rahim
Random Value Generating
Input any integer(n).
*/
#include <iostream>
#include <cstdlib>
using namespace std;
int main() {
int n;
while(cin>>n){// for understanding the output clearly
cout<<"Random value (any integer) = "<<rand()<<endl;
cout<<"Random value (from 0 to 9) = "<<rand()%10<<endl;
cout<<"Random value (from 1 to 100) = "<<rand()%100+1<<endl;
cout<<"Random value (from 3 to 8) = "<<rand()%6+3<<endl;
}
return 0;
}
|
Thursday, March 23, 2017
BigMod and BigsumMod
/* Bismillahir Rahmanir Rahim
BigMod of Series:
(1 + b + b^2 + b^3 + b^4 +......+ b^(p-1) )%mod
*/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll b, p, m;
ll bigmod(ll b, ll p, ll m){ // its the BigMod
if(p==0) return 1;
ll x=bigmod(b, p/2, m);
x=(x*x)%m;
if(p%2==1) x=(x*b)%m;
return x;
}
ll bigsummod(ll b, ll p, ll m){ // mod in every line
if(p==2) return (1+b)%m; // when 2 term (1+b)
else if(p==3) return (1+b+b*b)%m;
else if(p%2==1) return (1+b*bigsummod(b, p-1, m))%m;
else{
ll xx=bigsummod(b, p/2, m)%m;
return xx=(xx+(bigmod(b, p/2, m)*xx))%m;
}
}
int main(){
while(cin>>b>>p>>m){ // b=Base, p=power+1(number of term), m=mod
cout<<bigsummod(b, p, m)<<endl;
}
return 0;
}
|
Subscribe to:
Posts (Atom)