/**************************************** 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; }
সোমবার, ১৯ সেপ্টেম্বর, ২০১৬
Matrix Expo Library / Contest Matrix Lib
শুক্রবার, ৮ এপ্রিল, ২০১৬
Quadratic Equation Solver : Lab Assignment
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 | #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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 | #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; } |
সোমবার, ২৮ সেপ্টেম্বর, ২০১৫
রবিবার, ২৭ সেপ্টেম্বর, ২০১৫
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;
}
এতে সদস্যতা:
পোস্টগুলি (Atom)