Bit Inhaler

সোমবার, ১৯ সেপ্টেম্বর, ২০১৬

Matrix Expo Library / Contest Matrix Lib

/****************************************
              Zerus97
*****************************************/

#include <bits/stdc++.h>


#define loop(i,s,e) for(int i = s;i<=e;i++) //including end point

#define pb(a) push_back(a)

#define sqr(x) ((x)*(x))

#define CIN ios_base::sync_with_stdio(0); cin.tie(0);

#define ll long long

#define ull unsigned long long

#define SZ(a) int(a.size())

#define read() freopen("input.txt", "r", stdin)

#define write() freopen("output.txt", "w", stdout)


#define ms(a,b) memset(a, b, sizeof(a))

#define all(v) v.begin(), v.end()

#define PI acos(-1.0)

#define pf printf

#define sfi(a) scanf("%d",&a);

#define sfii(a,b) scanf("%d %d",&a,&b);

#define sfl(a) scanf("%lld",&a);

#define sfll(a,b) scanf("%lld %lld",&a,&b);

#define sful(a) scanf("%llu",&a);

#define sfulul(a,b) scanf("%llu %llu",&a,&b);

#define sful2(a,b) scanf("%llu %llu",&a,&b); // A little different

#define sfc(a) scanf("%c",&a);

#define sfs(a) scanf("%s",a);

#define getl(s) getline(cin,s);

#define mp make_pair

#define paii pair<int, int>

#define padd pair<dd, dd>

#define pall pair<ll, ll>

#define vi vector<int>

#define vll vector<ll>

#define mii map<int,int>

#define mlli map<ll,int>

#define mib map<int,bool>

#define fs first

#define sc second

#define CASE(t) printf("Case %d: ",++t) // t initialized 0

#define cCASE(t) cout<<"Case "<<++t<<": ";

#define D(v,status) cout<<status<<" "<<v<<endl;

#define INF 1000000000   //10e9

#define EPS 1e-9

#define flc fflush(stdout); //For interactive programs , flush while using pf (that's why __c )



#define CONTEST 1

using namespace std;

//CONTEST MATRIX LIB

#define GB 0

#define dim 4

#define mat vector<vector<int>>

mat GBv;

int idmat[] = //Each row
{
    1,0,1,1 ,
    1,0,0,0 ,
    0,1,0,0 ,
    0,0,0,1
};
mat assImat(int arr[]) // assign identity matrix
{
    mat X;



    int arridx = 0;

    vi rows;



    if(!rows.empty())
    {
        rows.clear();
    }

    loop(r,0,dim-1)
    {

        loop(c,0,dim-1)
        {
            rows.pb(arr[arridx]);

            arridx++;
        }
        X.pb(rows);
        rows.clear();


    }

    return X;

}

mat matmul(mat A,mat B,int ra,int ca,int rb,int cb)
{
    if(ca!=rb)
    {
        cout<<"ERR dim"<<endl;
        return GBv;
    }

    mat res;

    vi rows;

    loop(amr,0,ra-1) //ans matrix row
    {
        loop(amc,0,rb-1)
        {
            int rowi = 0;
            loop(crc,0,ca-1) //common row column
            {
                rowi+=A[amr][crc]*B[crc][amc];
            }

            rows.pb(rowi);

        }

        res.pb(rows);
        rows.clear();


    }

    return res;


}
mat expo(mat A, int row,int col,int p)
{
    if(p==1)
        return A;
    else if(p==2)
    {
        mat res = matmul(A,A,row,col,row,
                         col);
        return res;
    }
    else if(p%2==0)
    {
        mat halfp = expo(A,row,col,p/2);
        mat res = matmul(halfp,halfp,
                         row,col,row,col);
        return res;
    }
    else if(p%2==1)
    {
        mat halfp = expo(A,row,col,p/2);
        mat resp = matmul(halfp,halfp,
                          row,col,row,col);
        mat finres = matmul(resp,A,
                            row,col,row,col);
        return finres;
    }



}
void showmat(mat A,int row,int col)
{
    loop(r,0,row-1)
    {
        loop(c,0,col-1)
        cout<<A[r][c]<<" ";
        cout<<endl;
    }
}

int main()
{
    mat TT = assImat(idmat);

    showmat(TT,dim,dim);

    mat ans  = matmul(TT,TT,dim,dim,dim,dim);

    cout<<"----------"<<endl;

    showmat(ans,dim,dim);

    mat ans2 = expo(TT,dim,dim,2);
    
    cout<<"----------"<<endl;
    
    showmat(ans2,dim,dim);






    return 0;
}

শুক্রবার, ৮ এপ্রিল, ২০১৬

Quadratic Equation Solver : Lab Assignment

#include <iostream>
#include <math.h>
#define sqr(x) (x*x)
using namespace std;
class QuadraticEquation{
private:
    double a;
    double b;
    double c;
    double root1;
    double root2;
    double imaginaryRootReal;
    double imaginaryRootImg;
    bool isImaginaryroot;


public:
    QuadraticEquation();
    void setCoefficient(double a,double b,double c);
    void solve();
    bool isImaginary();
    double getRoot1();
    double getRoot2();
    double ImagReal();
    double ImagImg();


};
QuadraticEquation::QuadraticEquation()
{
    cout<<"Quadratic Equation is represented in the form aX^2 + bX + c = 0 ."<<endl;
    isImaginaryroot = false;

}
void QuadraticEquation::setCoefficient(double a,double b,double c)
{
    this->a  =a;
    this->b = b;
    this-> c = c;
}
void QuadraticEquation::solve()
{
double DETERMINANT;
DETERMINANT = sqr(b) - 4*a*c;
if(DETERMINANT<0)
{
    isImaginaryroot = true;
    DETERMINANT*=-1;
    imaginaryRootReal = -b/(2*a) ;
    imaginaryRootImg = sqrt(DETERMINANT)/(2*a);
    return;

}

root1 = (b + sqrt(DETERMINANT) )/(2*a);
root2 = (b - sqrt(DETERMINANT) )/(2*a);
}
bool QuadraticEquation::isImaginary()
{
    if(isImaginaryroot)
        return true;
    return false;
}
double QuadraticEquation::getRoot1()
{
    return root1;
}
double QuadraticEquation::getRoot2()
{
    return root2;
}
double QuadraticEquation::ImagReal()
{
    return imaginaryRootReal;
}
double QuadraticEquation::ImagImg()
{
    return  imaginaryRootImg;
}
int main()
{
    QuadraticEquation quadEqn;
    double a,b,c;
    cin>>a>>b>>c;

    quadEqn.setCoefficient(a,b,c);
    quadEqn.solve();
   if(quadEqn.isImaginary())
    {
        cout<<"The imaginary roots are "<<quadEqn.ImagReal()<<" + "<<quadEqn.ImagImg()<<"i"<<endl;
        cout<<"and "<<quadEqn.ImagReal()<<" - "<<quadEqn.ImagImg()<<"i"<<endl;

    }
    else
    {
        cout<<"The real roots are "<<quadEqn.getRoot1()<<endl;
        cout<<" and "<<quadEqn.getRoot2()<<endl;
    }

    return 0;
}

সোমবার, ২১ ডিসেম্বর, ২০১৫

BIT / Fenwick tree An implementation

#include <bits/stdc++.h>
#define garbazeVal -1
using namespace std;
int freq[100007] = {garbazeVal,3,4,0,12,4,5,23,45,23,35};
//How many students got 0,1,2,3,...............
//How many students got A+,A-,B+,B-,.......
//Map : sort according to some criteria
// A+ -> 1
// A  -> 2
// A- -> 3 (new indexes)
//For numerical - s we can do shifting
//minimum - 1000 ,so every index is now
// previous value + 1001
//-80  -> 921 [new index]
int Fentree[100007];
int query(int idx)
{
//Query 0 is not handled
    /*

    If it was , Then
                      if(idx==0)
                          return freq[0];
    */
    /*
    If 0 was included in the range
    then we d do just do this ,

    sum+=freq[0] ;


    ....
    ....

    return sum;

    */
    int sum=0;

    while(idx>0)
    {
        cout<<"Now at index "<<idx<<endl;
        sum+=Fentree[idx];
        idx -= idx & (-idx);
        cout<<"Sum is "<<sum<<endl;
    }
    return sum;

}
void update(int i,int v)
{
    //index 0 is untouched
    while(i<=10)
    {
        Fentree[i]+=v;
        i+=(i&(-i));
    }
}
void constr()
{
    for(int a=1; a<=10; a++)
    {
        update(a,freq[a]);
    }
}
int main()
{
    memset(Fentree,0,sizeof(Fentree));
    constr();

    cout<<"---------UPDATE---------"<<endl;
    for(int x=1; x<=10; x++)
    {
        int tt = x;
        cout<<"For "<<x<<" : ";
        while(tt<=10)
        {
            cout<<"+"<<" "<<tt;
            tt += tt&-tt;

        }
        cout<<endl;
    }

    cout<<"----------QUERY----------"<<endl;

    for(int x=1; x<=10; x++)
    {
        int tt = x;
        cout<<"For "<<x<<" : ";
        while(tt>0)
        {
            cout<<"->+["<<" "<<tt<<" ]";
            tt -= tt&-tt;

        }
        cout<<endl;
    }

//Why we can't use index 0
    cout<< "0 & -0 is just 0.-->"<< (0&(-0)) <<endl;
    cout<<"\nSo,to implement query 0 -> 0+(0&(-0)) -> 0 + 0 -> 0"<<endl;
    cout<<"0 calls 0.0 calls 0...When to stop?.But we could do this ..."<<endl;
    cout<<"if(idx == 0)\n    return freq[0] \n in O(1)"<<endl;
    cout<<"But that would make update function O(n) and ultimately \n" // Why ???
        <<"that would be q*log(n) [query] + u*n [update] for q queries and u updates with n items/buckets"
        <<"\n as for index 1 we updated index 1,2,4,8 [powers of 2]\n"
        <<"To include 0 we had to further update all i from 0 to n.\n";




    cout<<"Or,we could still include 0 and make the complexity q*log(n) + u*log(n)"<<endl;
    cout<<"The idea is that we keep the update function same 1 to n"<<endl;
    cout<<"But in the query function we first add freq[0] to sum and then do the decrementing of index"<<endl;

    while(1)
    {
        cout<<"Query :";
        int q;
        cin>>q;
        query(q);
    }

    return 0;
}

সোমবার, ২৮ সেপ্টেম্বর, ২০১৫

Sequence

https://oeis.org/

রবিবার, ২৭ সেপ্টেম্বর, ২০১৫

Sorting vector of structs

If you have some complex form of data and need to sort them according to some rules.

 #include <bits/stdc++.h>  
 using namespace std;  
 //A list of people with names,age,position  
 //sort them according to their ages( higher to lower ) names (lexicographical order [higher to lower])  
 //distance from origin (lower to higher)  
 //else on their relative position (lower to higher)//based on when the data is inserted  
 struct people  
 {  
   string name;  
   int age;  
   pair<int,int>pos;  
   int r_pos;  
   people(string nm,int ag,pair<int,int>ps,int r_pos)  
   {  
     this->name = nm;  
     this->age = ag;  
     pos.first = ps.first;  
     pos.second = ps.second;  
     this->r_pos = r_pos;  
   }  
 };  
 bool compare(people i,people j)  
 {  
   double dist_i = sqrt(i.pos.first*i.pos.first + i.pos.second*i.pos.second) ;  
   double dist_j = sqrt(j.pos.first*j.pos.first + j.pos.second*j.pos.second) ;  
   if(i.age!=j.age)  
     return i.age > j.age ; //previous element's age > next element's age in the final vector  
   if(i.name != j.name)  
     return i.name > j.name ; //previous element's name > next element's name in the final vector  
   if(dist_i!=dist_j) //not using EPS  
     return dist_i < dist_j ; //previous element's distance < next element's distance in the final vector (from origin )  
   return i.r_pos < j.r_pos ; //previous element's rel_position < next element's position in the final vector  
 }  
 int main()  
 {  
   vector<people>ppl;  
   people pip("Nabil",18,make_pair(3,4),1);  
   ppl.push_back(pip);  
   pip.r_pos = 2;  
   ppl.push_back(pip);  
   cout<<ppl.size()<<endl;  
 //Modification  
   pip.name = "Neo";  
   pip.age = 21;  
   pip.r_pos = 3;  
   ppl.push_back(pip);  
   pip.name = "Zan";  
   pip.pos = make_pair(5,6);  
   pip.r_pos = 4;  
   ppl.push_back(pip);  
   for(vector<people>::iterator it = ppl.begin(); it!=ppl.end(); it++)  
   {  
     people temp = *it ;  
     cout<<"People "<<it - ppl.begin() + 1 <<endl;  
     cout<<temp.name<<endl;  
     cout<<temp.age<<endl;  
     cout<<temp.pos.first<<" "<<temp.pos.second<<endl;  
     cout<<temp.r_pos<<endl;  
   }  
   sort(ppl.begin(),ppl.end(),compare); //Don't pass compare()  
   cout<<"-------------------------------------"<<endl;  
   for(vector<people>::iterator it = ppl.begin(); it!=ppl.end(); it++)  
   {  
     people temp = *it ;  
     cout<<"People "<<it - ppl.begin() + 1 <<endl;  
     cout<<temp.name<<endl;  
     cout<<temp.age<<endl;  
     cout<<temp.pos.first<<" "<<temp.pos.second<<endl;  
     cout<<temp.r_pos<<endl;  
   }  
 //people lister  
   cout<<"++++++++++++++++++++++++++++++++++++++"<<endl;  
   int n = 0;  
   cin>>n;  
   cout<<"Name Age pos_x pos_y\n";  
   ppl.clear();//clearing before new listing  
   for(int a=1; a<=n; a++)  
   {  
     string name;  
     int age;  
     int pos_x,pos_y;  
     cin>>name>>age>>pos_x>>pos_y;  
     pip.name = name;  
     pip.age = age ;  
     pip.pos.first = pos_x;  
     pip.pos.second = pos_y;  
     pip.r_pos = a;  
     ppl.push_back(pip);  
   }  
   sort(ppl.begin(),ppl.end(),compare); //Don't pass compare()  
   cout<<"-------------------------------------"<<endl;  
   for(vector<people>::iterator it = ppl.begin(); it!=ppl.end(); it++)  
   {  
     people temp = *it ;  
     cout<<"People "<<it - ppl.begin() + 1 <<endl;  
     cout<<temp.name<<endl;  
     cout<<temp.age<<endl;  
     cout<<temp.pos.first<<" "<<temp.pos.second<<endl;  
     cout<<temp.r_pos<<endl;  
   }  
   return 0;  
 }

শনিবার, ২৬ সেপ্টেম্বর, ২০১৫

STL C++ algorithm

 //STL ALGORITHM APPLICATION ON SEQUENCE CONTAIERS  
 #include <bits/stdc++.h>  
 using namespace std;  
 int main()  
 {  
  vector<char>vc;  
  vc.push_back('a');  
  vc.push_back('b');  
  vc.push_back('c');  
  vc.push_back('d');  
  //first occurrence and iterator  
  vector<char>::iterator it = find(vc.begin(),vc.end(),'c');  
  cout<<"c is at position "<<it - vc.begin() + 1<<endl;  
  vc.push_back('c');  
  vc.push_back('c');  
  vc.push_back('c');  
  //Counting number of appearances  
  int cnt = count(vc.begin(),vc.end(),'c');  
  cout<<"c appeared "<<cnt<<" times\n";  
  //Searching a subsequence  
  vector<int>v_prime;  
  v_prime.push_back(3);  
  v_prime.push_back(4);  
  v_prime.push_back(5);  
  v_prime.push_back(6);  
  v_prime.push_back(7);  
  v_prime.push_back(8);  
  v_prime.push_back(9);  
  vector<int>v_sec_1;  
  v_sec_1.push_back(7);  
  v_sec_1.push_back(8);  
  v_sec_1.push_back(9);  
  vector<int>v_sec_2;  
  v_sec_2.push_back(3);  
  v_sec_2.push_back(5);  
  v_sec_2.push_back(6);  
  //An iterator to the first element of the first occurrence of [first2,last2) in [first1,last1).  
  //If the sequence is not found, the function returns last1.  
  //SEARCH   S FOR SUBSEQUENCE  
  if(search(v_prime.begin()+2,v_prime.end(),v_sec_1.begin(),v_sec_1.end())!=v_prime.end())  
   cout<<"Found sequence\n";  
   else  
   cout<<"Not Found sequence\n";  
  if(search(v_prime.begin()+2,v_prime.end(),v_sec_2.begin(),v_sec_2.end())!=v_prime.end())  
   cout<<"Found sequence\n";  
  else  
   cout<<"Not Found sequence\n";  
   cout<<*min_element(v_prime.begin(),v_prime.end())<<endl;  
   return 0;  
 }

STL C++ list 2

STL list part 2 :

 //STL Container list part 2  
 #include <bits/stdc++.h>  
 #define p_l_i(l) for(list<int>::iterator it = l.begin();it!=l.end();it++)cout<<*it<<" ";cout<<endl;  
 using namespace std;  
 bool r_i_t_i_t(const int& val)  
 {  
   if(val>40 && val<90)  
     return true;  
   return false;  
 }  
 int main()  
 {  
   list<int>l1;  
   list<int>l2;  
   l1.push_back(34);  
   l1.push_back(4);  
   l1.push_back(3);  
   l1.push_back(41);  
   l2.push_back(31);  
   l2.push_back(20);  
   l2.push_back(91);  
   l2.push_back(16);  
   //Merging 2 lists O(n)  
   //Without sorting  
   l1.merge(l2);  
   p_l_i(l1); //Weird ordering  
   if(l2.empty())  
     cout<<"l2 is empty!\n";  
   //merging with sorting  
   list<int>l3;  
   list<int>l4;  
   l3.push_back(34);  
   l3.push_back(4);  
   l3.push_back(3);  
   l3.push_back(41);  
   l4.push_back(31);  
   l4.push_back(20);  
   l4.push_back(91);  
   l4.push_back(16);  
   l3.sort(); //this is the min to max sort version  
   l4.sort(); //this is the min to max sort version  
   p_l_i(l3);  
   p_l_i(l4);  
   l3.merge(l4);  
   p_l_i(l3);  
   if(l4.empty())  
     cout<<"l4 is empty!\n";  
   //Erasing elements O(1)  
                      //3 4 16 20 31 34 41 91  
   list<int>::iterator it= l3.begin(); //^  
   list<int>::iterator it2;  
   advance(it,4); //advancing iterator //      ^  (4 steps ahead from begin)  
   cout<<*it<<endl;  
   it2 = l3.erase(it);            //3 4 16 20 34 41 91 ....<><><>.... [31] it pointing to 31 still  
   //but l3 itself doesn't contain 31  
   p_l_i(l3);  
   cout<<*it<<endl; //prints 31 invalidated reference  
   //But it2 prints 34 previous position of 31  
   cout<<*it2<<endl;  
   //Can erase a range of elements  
   list<int>::iterator it3 = l3.begin(); //pointing to 3  
   list<int>::iterator it4 = l3.end() ; //pointing to next position of 91  
   it4--; //pointing to 91  
   it4--; //pointing to 41  
   advance(it3,3);//pointing to 20  
   l3.erase(it3,it4); //deleting 20 to 34 (34 is just before 41)  
   p_l_i(l3);  
   //removing all elements with a certain value  
   l3.push_back(3); //3 4 16 41 91 3  
   p_l_i(l3);  
   l3.remove(3);  
   p_l_i(l3);    //4 16 41 91  
   //Can come in handy while pruning  
   //removing with a condition  
   l3.remove_if(r_i_t_i_t); //remove if this is true //See the syntax not r_i_t_i_t()  
   p_l_i(l3);//no elements in (40,90)  
   //Splicing O(1)  
   //listX -------transferring-------->>>> listY  
   //merging whole list  
   //splice(the iterator of listX where I want to merge listY(or part of it) , name of listY(ref))  
   //merging just 1 element  
   //splice( || , || , the iterator of listY pointing to that element)  
   //merging a range of elements from listY  
   //splice( || , || , starting iterator , ending iterator )  
   l4.push_back(-12);  
   l4.push_back(-98);  
   l4.push_back(-67);  
   l4.push_front(445);  
   l4.push_front(345);  
   l4.push_front(125);  
   it4 = l3.begin();  
   it4++; //pointing to 16  
   cout<<*it4<<endl; //16  
   l3.splice(it4,l4); // merging whole list  
   p_l_i(l3);  
   if(l4.empty())  
     cout<<"l4 is now empty\n";  
   l4.push_back(-12);  
   l4.push_back(-98);  
   l4.push_back(-67);  
   l4.push_front(445);  
   l4.push_front(345);  
   l4.push_front(125);  
   l3.splice(it4,l4,l4.begin());//it4 still pointing to 16 .... just adding 125 in the position of 16  
   p_l_i(l3);  
   l4.push_back(999);  
   l4.push_back(99);  
   l4.push_back(9);  
   l3.splice(it4,l4,l4.begin(),l4.end()--); //Still adding 9 post increment ;-)  
   p_l_i(l3);  
   l4.push_back(888);  
   l4.push_back(88);  
   l4.push_back(8);  
   l3.splice(it4,l4,l4.begin(),--l4.end()); //Not adding 8 pre increment ;-)  
   p_l_i(l3);  
   //Keeping just unique values : Only works on sorted list  
   l3.sort();  
   l3.unique();  
   p_l_i(l3);  
   return 0;  
 }