[ SPOJ ] MULTQ3 - Multiples of 3

Author            : Anwar Jahid Ruman Hossain 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : [ SPOJ ] MULTQ3 - Multiples of 3
Source            : Light OJ
Category          : Segment Tree
Algorithm         : Segment Tree
Verdict           : Time Limit Exceeded

1. #include<bits/stdc++.h>  
2. using namespace std;  
3. #define ll long long int  
4. #define mx 100005  
5. int tree[mx*3][3];  
6. int arr[mx];  
7. void build_segment(int node,int left,int right){  
8.     if(left==right){  
9.         tree[node][0] = 1;  //divisible by 3 means %3 = 0  
10.         tree[node][1] = 0;  // %3 = 1  
11.         tree[node][2] = 0;  // %3 = 2  
12.         return;  
13.     }  
14.     int mid=(left+right)/2;  
15.     build_segment(node*2, left, mid); //left subtree build  
16.     build_segment(node*2 + 1, mid+1, right); //right subtree build  
17.     tree[node][0] = tree[node*2][0] + tree[node*2+1][0];  
18.     tree[node][1] = tree[node*2][1] + tree[node*2+1][1];  
19.     tree[node][2] = tree[node*2][2] + tree[node*2+1][2];  
20. }  
21.   
22. int query_seqment(int node,int left,int right,int ia,int ib){  
23.     if(right < ia || left > ib)return 0;  
24.     if(ia <= left && right <= ib){  
25.         return tree[node][0];//the divisible count  
26.     }  
27.     int mid=(left+right)/2;  
28.     int cnt = 0;  
29.     cnt += query_seqment(node*2 + 1, mid+1, right, ia, ib); //right subtree query  
30.     cnt += query_seqment(node*2, left, mid, ia, ib); //left subtree query  
31.     return cnt;  
32. }  
33. void update_segment(int node,int left,int right, int ia,int ib){  
34.     if(ia>right || ib<left)  
35.         return;  
36.     if(left==right){  
37.         int tmp = tree[node][0];  
38.         tree[node][0] = tree[node][1];  
39.         tree[node][1] = tree[node][2];  
40.         tree[node][2] = tmp;  
41.         return;  
42.     }  
43.     int mid=(left+right)/2;  
44.     update_segment(node*2,left,mid,ia,ib);  
45.     update_segment(node*2+1,mid+1,right,ia,ib);  
46.     tree[node][0] = tree[node*2][0] + tree[node*2+1][0];  
47.     tree[node][1] = tree[node*2][1] + tree[node*2+1][1];  
48.     tree[node][2] = tree[node*2][2] + tree[node*2+1][2];  
49. }  
50. int main(){  
51.     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);  
52.     //freopen("input.txt","r",stdin);  
53.     //freopen("output.txt","w",stdout);  
54.     int n,q;  
55.     while(scanf("%d%d",&n,&q)!=EOF){  
56.         build_segment(1,1,n);  
57.         int op,ia,ib;  
58.         for(int i=1;i<=q;i++){  
59.             scanf("%d%d%d",&op,&ia,&ib);  
60.             if(op==1)  
61.                 printf("%d\n",query_seqment(1,1,n,ia+1,ib+1));  
62.             else if(op==0){  
63.                 update_segment(1,1,n,ia+1,ib+1);  
64.             }  
65.         }  
66.     }  
67.     return 0;  
68. }  

[ LightOJ ] 1082- Array Queries

Author            : Anwar Jahid Ruman Hossain 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : [ LightOJ ] 1082- Array Queries
Source            : Light OJ
Category          : Segment Tree
Algorithm         : Segment Tree
Verdict           : Accepted

#include<bits/stdc++.h>  
using namespace std;  
#define ll long long int  
#define mx 100005  
int tree[mx*3];  
int arr[mx];  
void build_segment(int node,int left,int right){  
    if(left==right){  
        tree[node]=arr[left]; //leaf node value set  
        //cout<<"Index "<<node<<": "<<tree[node]<<endl;  
        return;  
    }  
    int mid=(left+right)/2;  
    build_segment(node*2, left, mid); //left subtree build  
    build_segment(node*2 + 1, mid+1, right); //right subtree build  
    tree[node]=min(tree[node*2], tree[node*2 + 1]); //parent min value set  
    //cout<<"IndexMin "<<node<<": "<<tree[node]<<endl;  
}  
int query_seqment(int node,int left,int right,int ia,int ib){  
  
    if(ia>right || ib<left)  
        return INT_MAX;  
    if(left>=ia && right<=ib)  
        return tree[node];  
    int mid=(left+right)/2;  
    int p=query_seqment(node*2, left, mid, ia, ib); //left parent query  
    int q=query_seqment(node*2 + 1, mid+1, right, ia, ib); //right parent query  
    return min(p,q);  
  
  
}  
int main(){  
    //freopen("input.txt","r",stdin);  
    //freopen("output.txt","w",stdout);  
    int t;  
    scanf("%d",&t);  
    for(int tc=1;tc<=t;tc++){  
        int n,q;  
        scanf("%d%d",&n,&q);  
        for(int i=1;i<=n;i++){  
            scanf("%d",&arr[i]);  
        }  
        //root node, left most node, right most node  
        build_segment(1,1,n);  
        int ia,ib;  
        printf("Case %d:\n",tc);  
        for(int i=1;i<=q;i++){  
            scanf("%d%d",&ia,&ib);  
            //root, left most, right most, from node, to node  
            printf("%d\n",query_seqment(1,1,n,ia,ib));  
        }  
    }  
    return 0;  
}  

[LightOJ ] 1043- Triangle Partitioning

Author            : Anwar Jahid Ruman Hossain 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : [ LightOJ ] 1043- Triangle Partitioning
Source            : Light OJ
Category          : Searching and Sorting
Algorithm         : Bi-Section(Binary Search)
Verdict           : Accepted

1.  #include<bits/stdc++.h>  
2. using namespace std;  
3. #define ll long long int  
4. double TrianlgeRatio(double ab,double ac,double bc,double ad){  
5.     double ae,de,s1,s2,largeTriangleArea,smallTriangleArea,trapheziumArea,ratio;  
6.     ae=(ad*ac)/ab;  
7.     de=(ad*bc)/ab;  
8.   
9.     s1=(ab+ac+bc)/2.0;  
10.     s2=(ad+de+ae)/2.0;  
11.   
12.     largeTriangleArea=sqrt(s1*(s1-ab)*(s1-bc)*(s1-ac));  
13.     smallTriangleArea=sqrt(s2*(s2-ad)*(s2-de)*(s2-ae));  
14.     trapheziumArea=largeTriangleArea-smallTriangleArea;  
15.   
16.     ratio=smallTriangleArea/trapheziumArea;  
17.     return ratio;  
18. }  
19. double BiSection(double ab, double ac,double bc, double ratio){  
20.     double low,high,mid,ad;  
21.     low=0.0;  
22.     high=ab;  
23.     for(int i=0;i<100;i++){  
24.         mid=(low+high)/2.0;  
25.         ad=mid;  
26.         if(TrianlgeRatio(ab,ac,bc,ad)>ratio)  
27.             high=mid;  
28.         else low=mid;  
29.     }  
30.     return ad;  
31. }  
32. int main(){  
33.     //freopen("input.txt","r",stdin);  
34.     //freopen("output.txt","w",stdout);  
35.     int t;  
36.     cin>>t;  
37.     for(int i=1;i<=t;i++){  
38.         double ab,ac,bc,ratio,result;  
39.         cin>>ab>>ac>>bc>>ratio;  
40.         result=BiSection(ab,ac,bc,ratio);  
41.         cout<<"Case "<<i<<": "<<fixed<<setprecision(10)<<result<<endl;  
42.     }  
43.     return 0;  
44. }  
45. 
    

1. Technique: BiSection(Binary Search) 
2. Firstly , we assume a value of AD. Then we calculate ratio of ADE and BDEC(ADE/BDEC) according to our assumed value. Then we compare 
3. new calculated ratio with given ratio. To find value of AE and DE we use property of "similar triangle".Similar Triangle property is 
4. (AD/AB) = (AE/AC) = (DE/BC).As ans have to  correct upto 10^-6 fraction value, we can't say mid+1 OR mid-1 for high and low value 
5. because fraction value can be between 0.0 to 0.99(That means between 1).That's why we cant increase or decrease directy 1 from mid value 
6. of high and low.