Fst Block 4 Online Chapters: Fill & Download for Free

Following the way of the first answer written by Ashish Gupta, I will write about not exactly ‘hacks’ but things that make coding in C++ for competitive programming a lot more convenient and clearer, including the use of standard library. I guess these will come really handy if you can use them while coding.Let’s go!Chapter 1: Syntactic SugarsKeyword autoYou probably know about auto in C++. When C++11 introduced it, it really made our life a lot easier, which became more convenient in C++14 from when auto can be generic:auto merge(auto a, auto b)  {  vector<int> c;  // do stuff and assign the result in c  return c; }  vector<int> a, b; auto c = merge(a,b); And also, lambda expressions can be a lot more concise:auto lamb = [](auto x, auto y)  {  // do stuff  auto result = x+y;  return result; }; Remember that the compiler should be provided some way to deduce the types of your variables. For example, you cannot write the above lambda function this way:auto lamb = [](auto x, auto y)  {  // do stuff  auto result;  result = x+y;  return result; }; This gives you an error instantly:error: declaration of ‘auto result’ has no initializer auto result; ^~~~ This type-deducing by compiler can be really useful when you have complex data structures. Look at this small demo:void populate(auto &data) // see! {  data.insert({"a",{1,4}});  data.insert({"b",{3,1}});  data.insert({"c",{2,3}}); }  auto merge(auto data, auto upcoming_data) // don't write long declaration again {  auto result = data;   for(auto &it: upcoming_data)  {  result.insert(it);  }   return result; }  int main() {  map<string, pair<int,int>> data;  populate(data);   map<string, pair<int,int>> upcoming_data;  upcoming_data.insert({"d",{5,3}});   auto final_data = merge(data,upcoming_data);   for(auto itr: final_data)  {  auto [v1,v2] = itr.second; // structured bindings discussed below  cout<<itr.first<<" "<<v1<<" "<<v2<<endl;  }   return 0; } Class Template Argument DeductionIn C++11, you could do this:pair<int,double> p = {12,2.1}; C++17 made it more convenient:pair p = {12,2.1} Type is deducted by the compiler which will be <int,double>.Structured BindingsOkay I really liked this one when it was introduced in C++17.So you have some kind of structure with different data types. You want to bind them to different variables according to the types.Previously, you had to write quite a few lines of code to do bindings to separate variables:template<typename T1, typename T2, typename T3>  struct info  {  T1 x; T2 y; T3 z;  // overload () to make tuple  auto operator()()   {  return make_tuple(x,y,z);  } };  info<int,string,double> data{1,"one",1.1};  int a; string b; double c;  // do the structured bindings tie(a,b,c) = data(); Then it became so much convenient in C++17!template<typename T1, typename T2, typename T3>  struct info  {  T1 x; T2 y; T3 z; };  info<int,string,double> data{1,"one",1.1}; // do the structured bindings auto [a,b,c] = data; In case you want to to bind using reference, just add an &.auto &[a,b,c] = data; One particular example that makes a lot more sense now is the use of structured bindings while working with C++ containers:map<string,int> id; for(auto [key,value]: id)  {  // do stuff with key and value } Neat!gcd() and lcm() in Standard LibraryYep! From C++17, you can just write this:int gcd_val = gcd(12,4); // returns 4 int lcm_val = lcm(12,4); // returns 12 Init Statement in if and switchOkay I just got to know about it while writing this answer. Apparently, C++17 introduced `init` statement inside if and switch.set<int> input = {1,5,3,6};  if(auto it = input.find(7); it==input.end())  {  cout<<7<<" not found!"<<endl; } else  {  // `it` is available here  cout<<"voila, 7 is there!"<<endl; } So the form will be like:if(init-statement(var); condition(var)) {  // do stuff } else // other stuff Remember that, var will be available to the following else block!Non-member begin() end()In order to access the beginning of a container, we use container.begin() and similarly for end, container.end(). C++11 introduced non member begin() and end(), which lets you write begin(container), end(container) etc.Later on, from the 17, we have non-member size(), empty(), data().One powerful thing of this addition is that they not only work for containers, but also for old C-type arrays! Previously you could not do this:int a[] = {1,5,3,2,5}; for(auto it=a.begin(); it!=a.end(); it++) {  // some stuff on the data } But you can do it now:int a[] = {1,5,3,2,5}; for(auto it=begin(a); it!=end(a); it++) {  // value on (*it)  // do stuff } This makes generic programming easier for you. Guess you want to write some generic code for all types of containers, and you want to include C type arrays, too. This will come in handy.C++ Standard Library <array>Not exactly a syntactic sugar, C++ <array> was useful when working on multiple data of same type, specially in Graph problems. An example:vector<array<int,3>> graph[N]; // N = maximum number of nodes Say you have [math]n[/math] nodes and [math]m[/math] edges, and for each edge, you want to input its length and time to travel through this edge:for(int i=0; i<m; i++) {  cin>>u>>v>>w>>t; // each edge (vertex1, vertex2, length, time)  graph[u].push_back({v,w,t}); } Now you can just access like you do in an array:for(int i=0; i<size(graph[1]); i++) {  // corresponding node, length and time  cout<<graph[1][i][0]<<" "<<graph[1][i][1]<<" "<<graph[1][i][2]<<endl; } And another convenient feature is that you can always call sort(begin(graph[1]), end(graph[1])) without the necessity of declaring comparison function. This will sort the array based on the [math]0[/math]th element onward.I found this useful, instead of writing plain old structure again and again. Of course readability decreases a bit, and if you have different types of data like int, string, double you cannot just do this.Chapter 2: Algorithm LibraryThe following points discussed are available in C++ <algorithm> library. I would like to mention few useful functions below.Convenient minmaxminmax returns the minimum and maximum of the given two values, or the given list. It returns a pair and it can also provide the functionality of your own comparison method. And more conveniently, minmax_element does the same for your container:int a = 9, b = 12; // out.first contains the minimum element, out.second is the maximum one auto out = minmax(a,b);  vector<int> collection = {6,5,3,2,1,4,6,7}; auto result = minmax_element(begin(collection), end(collection));  // you can also add compare function as the third argument // (result.first - collection.begin()) is the index of the minimum element // (result.second - collection.begin()) is the index of the maximum element And note that, there are also functions like min_element and max_element which find minimum and maximum values respectively inside your containers.The nth_element of an ArrayThis function is quite useful, given that it has an interesting complexity. If you want to know the n-th element of your collection if it was sorted, but you do not want to sort the collection to make an [math]O(n log(n))[/math] operation, nth_element is your friend. It finds the desired element in [math]O(n)[/math].vector<int> collection = {1,2,13,5,12,3,4};  auto median_pos = collection.begin() + collection.size()/2; nth_element(begin(collection),median_pos,end(collection));  // note that the original vector will be changed due to the operations // done by nth_element Randomized OrderTo order an array of elements randomly, we used random_shuffle before. From the standard of C++17, random_shuffle has been removed. Now we prefer shuffle which is more effective, given that it takes the advantages of the header random.vector<int> collection={1,2,13,5,12,3,4}; random_device rd; mt19937 rand_gen(rd()); shuffle(begin(collection), end(collection), rand_gen); I personally have interesting experience on random_shuffle. On a specific problem during team practice, we found a problem on flow. The only solution that we could think of would get TLE because we were probably doing something like running flow from each node. Then we kind of realized that if we could do the flows randomly, we ‘might’ pass the TL. And guess what, it worked! :PMerging ConciselyYou have two sorted collections, you want to merge them, and you also want the merged collection to remain sorted. You can just add the second collection to the first one and sort the resultant again which adds an extra [math]O(log(n))[/math] factor. Instead of that, we can just use merge!vector<int> c1={1,2,5,5,5,6,9,12}; vector<int> c2={2,4,4,5,7,15}; vector<int> result; // contains merged elements  merge(begin(c1), end(c1), begin(c2), end(c2), back_inserter(result));  // result = {1, 2, 2, 4, 4, 5, 5, 5, 5, 6, 7, 9, 12, 15} On the other hand, do you remember when implementing merge sort, we need to merge two sides of our array? inplace_merge can be conveniently used for that.Look at this tiny merge sort based on the example given in cppreference:void merge_sort(auto l, auto r) {  if(r-l>1)  {  auto mid=l+(r-l)/2;  merge_sort(l,mid);  merge_sort(mid,r);  inplace_merge(l,mid,r);  } }  vector<int> collection = {2,4,4,1,1,3,9}; merge_sort(begin(collection), end(collection)); For more, you can look into the Medium post linked in the reference section where I wrote about useful functionalities from C++ algorithm library.Chapter 3: MiscellaneousBigger Numbers with __int128GCC has support for __int128 but all online judges don’t support this data type. I have faced necessity of this data type quite a few times, during onsite and practice team contests. And this got AC.__int128 input() {  string s;  cin >> s;  long long fst = (s[0] == '-') ? 1 : 0;  __int128 v = 0;  for(int i=0; i<s.size(); i++)   v = v * 10 + s[i] - '0';  if(fst) v = -v;  return v; } ostream& operator << (ostream& os,const __int128& v)  {  string ret, sgn;  __int128 n = v;  if(v < 0) sgn = "-", n = -v;  while(n) ret.push_back(n % 10 + '0'), n /= 10;  reverse(begin(ret),end(ret)); // using C++ free functions begin() and end()  ret = sgn + ret;  os << ret;  return os; } int main() {  __int128 n = input();  cout << n << endl; } Remember that this data type can be slow. But if the problem requires big numbers and of course writing the big-num library in C++ on your own is not a very good idea, you can use __int128 based on the range of the numbers.Random Number GenerationRandom number generation is risky, given that it is random, and you can fall in unexpected traps pretty easily. But using modern C++ <random> library, things can be made pretty secure. I learned this generation of random numbers from Codeforces:#include <random> #include <chrono> using namespace std;  // Seeding non-deterministically mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); random_device rd; mt19937 mt(rd());  uniform_real_distribution<double> r1(1.0, 10.0); uniform_int_distribution<int> r2(1,INT_MAX); normal_distribution<double> r3(1.0,10.0); exponential_distribution<> r4(5);  int main() {  cout<<rng()<<endl;  cout<<r1(mt)<<endl;  cout<<r2(mt)<<endl;  cout<<r4(mt)<<endl;  return 0; } Finding MSB in [math]O(1)[/math]Found in Stack Overflow, this was pretty interesting:int msb(unsigned x)  {  union {   double a; int b[2];   };  a = x;  return (b[1] >> 20) - 1023; } That’s all for now. I would like to add more if I remember or find out any other interesting techniques that can be useful which is very unlikely though.I hope this answer helped! And of course, feel free to point out any mistake you findReferenceC++17 in details: Code SimplificationHow I discovered the C++ algorithm library and learned not to reinvent the wheel by M Chowdhury on Mediummochow13/competitive-programming-libraryUsing the GNU Compiler Collection (GCC): __int128C++17, competitive programming edition - Codeforcesr/cpp - Motivation for non-member functions begin, end?