Template Metaprogramming in C++ Part 1 / Infinity This (possibly series of) blog(s) should serve as in introduction to template metaprogramming in C++, and how you can use it to write more reusable and efficient snippets of code. You need to know nothing beforehand, and I believe its actually much simpler than most people think it is, looking at all the features you have in it. I will also be mentioning which version of `C++` you need to use each mentioned feature, if it is recent enough. Consider a rudimentary function like `std::max`. How do you even write `std::max`?. Well you could do ~~~~~ int max(int a, int b){ if(a > b) return a; else return b; } ~~~~~ Well you might use it on `float`s too. Why not add ~~~~~ float max(float a, float b){ if(a > b) return a; else return b; } ~~~~~ You very quickly realise this is a horrible idea. There has to be some way to say, I want to do this, but for any types. Here is where `template` comes in. `template` is where you write the list of t...

Full text and comments »

Outstanding members of my cp library I like to build my [cp library](https://github.com/demidenko/olymp-cpp-lib). I am not aiming to fill it by each algo I have met, so content looks poor. Instead I am focusing on frequently used features or implement convenient api for powerful methods. Also I like to rate cp libraries of others and currently I noticed that my lib have enough implementations which I never seen before, so I want to share it with community. Hope it will inspire you to improve or rewrite your library and eventually rethink about some algorithms (which happens to me couple times). ## #5 Centroid decomposition [graphs/trees/centriod_decomposition.cpp](https://github.com/demidenko/olymp-cpp-lib/blob/master/graphs/trees/centriod_decomposition.cpp) This one is the perfect example of what I am calling convenient api. I've seen a lot of centroid decomposition snippets and almost all of them is template code or unfinished data structure with piece of code where you need to add your solution. I have s...

Full text and comments »

Compilation and debugging tutorial In this tutorial I'm going to share some useful compilation and debugging tips. These tips can save you a ton of time debugging and make compilation and debugging convenient. ### Useful compilation flags G++ has many useful warning flags such as - `-Wall` enables all warnings. I highly recommend using this flags. - `-Wextra` enables extra warnings. - `-Wno-sign-conversion` silences sign conversion warnings for code like `x < vec.size()` - `-Wshadow` enables shadowing warnings, so that if you define another variable with the same name in a local scope, you will get a warning. Using these flags can save you time debugging silly mistakes like forgetting to return a value in a function or doing a comparison like `x < vec.size()-1` where `vec.size()-1` can underflow into `SIZE_MAX-1`. #### Precompiled headers You can use precompiled headers to substantially speed up the compilation of your code. Note that the precompiled header is only used if it is compiled with the ...

Full text and comments »

Big integers in Pascal Hello, Codeforces! When we talk the languages with built-in big integer implementation, usually such languages as _Java_ or _Python_ are mentioned. Now I'll tell you about long arithmetic implementation in _Pascal_ (more precisely, in the _Free Pascal Compiler_). The simplest code, which reads two big integers and outputs their sum, looks like this: <spoiler summary="Code"> ~~~~~ program sum; {$Mode Delphi} uses gmp; var sa, sb: string; a, b: MPInteger; begin readLn(sa); readLn(sb); a := sa; b := sb; writeLn(string(a + b)); end. ~~~~~ </spoiler> `gmp` unit contains all the classes and operators to work with big integers. How does it work? This unit contains bindings for [_GNU Multiprecision Library_](https://gmplib.org/). The program and the library are linked dynamically, so, to make the program work this library is required to install. Luckily, many Linux distros install `libgmp` by default and so this trick can be used in the te...

Full text and comments »

Object Oriented Programming Notes(C++) OOPs are actually very simple but we can have some difficult questions on OOPs as well. We will first have short notes of theory(which can be asked in form of questions) and then shift to questions. I am refering E balaguruswamy book for this. These are short notes and may miss something, if you think something is missing please comment. Also, we would be using this track: 1. Introduction to classes and objects 2. Constructors and Destructors 3. Operator Overloading 4. Inheritance 5. Polymorphism > We will be discussing major topics here and actually difficult ones. **You must know basic OOPs**. ### Introduction <spoiler summary="C structures Vs C++ Classes"> We know structures can be used to create user-defined data types in C and C++. But then why we need classes? We can have functions, constructors, etc in structures as well but what differentiates it from classes are lack of abstraction and inheritance(And actually many other things as well). We can hide certain...

Full text and comments »

Codeforces Round #940 and CodeCraft-23 (Div. 2) Editorial [problem:1957A] ================== **Idea:** [user:keyurchd_11,2024-04-21] **Problem Setting:** [user:shakr,2024-04-21] [user:lezirtin,2024-04-21] **Editorial**: [user:shakr,2024-04-21] [user:TheRaja,2024-04-21] There were a few solutions which passes pre-tests with the assumption that $a_i \leq n$. We apologize for the pre-tests on A not including this case. <spoiler summary="Hint 1"> To create the most polygons, you should use as few sticks as possible per polygon. What polygon has the least number of sides? </spoiler> <spoiler summary="Solution"> [tutorial:1957A] </spoiler> <spoiler summary="Rate this problem"> - Great Problem - Ok Problem - Bad Problem - Didn't solve </spoiler> <spoiler summary="C++ Code"> ~~~~~ #include <bits/stdc++.h> using namespace std; int main(){ int t; cin >> t; while(t--) { int n; cin >> n; vector<int> a(101, 0);...

Full text and comments »

Some tips regarding sets and multisets I actually thought I had a quite good understanding of std::set and std::multiset until D of the last Div. 2 contest taught me a lesson (you can tell from my submissions on D). So I decided to write this blog to prevent other people from making similar mistakes when overloading the < operator in sets (if these are just common sense then it's probably just my skill issue). If there exists a blog that talks about similar things please do inform me. Try to think of the output for each of the following codes. 1) (with std::set) <spoiler summary="Code 1"> ~~~~~ #include <bits/stdc++.h> using namespace std; struct node{ int l, r; bool operator < (node t) const& { return r - l < t.r - t.l; } }; int main(){ set <node> st; st.insert({1, 2}); st.insert({3, 5}); st.insert({6, 7}); cout << st.size() << "\n"; return 0; } ~~~~~ </spoiler> <spoiler summary="Explanation 1"> The output is 2 instead of 3 because {1, ...

Full text and comments »

Fast and furious C++ I/O For a long time I've been upset with C++ standard input/output. First of all, I heard that `fread`/`fwrite` are much faster than everything else, and it's impossible to get good times on problems with huge input or output without using those. Secondly, it's really annoying to write formatting string and ampersands in `scanf`, especially with many variables to read. Thirdly, the only way to expand I/O to custom types is by overloading `<<` and `>>` operators on streams, but they are the slowest. I tried to tackle all these issues in my implementation. Remember, that it's targeted for the common use case in programming contests, so it's not as flexible as one might wish. [The code is here](http://ideone.com/X1tP8Q) **Doesn't compile with MSVS.** I apologize in advance to everyone, who will be scrolling through this 500 lines trying to read my solutions. Also it's not advised for people without broad experience with C++ to try to understand the entirety of it (dangerous for your men...

Full text and comments »

[Tutorial] Sorting with lambda Hello, Codeforces! Today I want to share with you something that often gets brushed off because it's a very basic concept &mdash; sorting. I think that this topic is often overlooked even though it can be very useful. This blog (my first on Codeforces, yaay) is thus rather intended for beginners in C++. I'll describe a technique that makes sorting fast to implement &mdash; lambdas. For simplicity, arrays will always mean `vector` in this blog. There are two main usages of sorting I want to describe: #### 1. Sorting an auxiliary array to keep the original array unchanged. This is often the case when our data is splitted into several separate arrays, that are somehow connected together. This may occur when each type of data is given in separate rows. For example, one array could contain a value of a cell and the other one &mdash; it's color. Say that we want to simultaneously sort both those arrays by value (increasing). In order to do that, we may rather introduce a new a...

Full text and comments »

STL in CP — Understanding Named Requirements (part 2) **Before we get to the point, I kindly ask you to read [the previous part of the blog](https://codeforces.me/blog/entry/107211) if you haven't already. It contains a lot of the context we will be speaking of.** So, on the previous half of the blog, I explained the basics of named requirements, and promised to demonstrate implementing a working class based on the RandomNumberEngine requirement. It took some time (due to life & stuff), but here it is now. Here I explain the process of implementing Lehmer64, following the RandomNumberEngine requirement. First, I read carefully the [references for the RandomNumberEngine requirement](https://en.cppreference.com/w/cpp/named_req/RandomNumberEngine). Reading these requirements carefully before implementing can prevent many mistakes, so you may as well read the requirements before reading the rest of the blog. The concise description on the top of *Requirements* provides a very important information, not present in the table below. It...

Full text and comments »

Weird C++ template question I tried to define two template functions outputing pairs and vectors of any type. If it is overloaded operator it works fine, but for standard functions lookup fails to find function defined for pair if it is declared after called. Does anybody know why? ~~~~~ # include <bits/stdc++.h> using namespace std; int Hash(int x) { return x; } template <typename T> int Hash(vector<T> x) { int ans = 0; for (auto c : x) ans = 2 * ans + Hash(c);//Fails if c is a pair: no matching function for call to ‘Hash(std::pair<int, int>&) return ans; } template <typename T, typename C> auto Hash(pair <T, C> x) -> int { return Hash(x.first) + Hash(x.second) * 14; } template <typename T> ostream &operator<<(ostream &os, vector <T> x) { os << "{"; int cou = 0; for (auto c : x) { if (cou++) os << ", "; os << c;//Works even if c is a pair despite calling operator declared late } return os << "}"; } template <typename T, typename C> ostream & operator<< (ostream &os...

Full text and comments »

Ordered Set with Custom Sorting Operator in C++ ## Ordered Sets in C++ In C++, ordered sets can be created using special code templates. ~~~~~ #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>; ~~~~~ Two primary structures are introduced: - `ordered_set` maintains sorted unique elements in ascending order using `less` comparison. - `ordered_multiset` allows duplicates using a `less_equal` comparison, preserving the sorted order. ### Fucntions In addition to normal set operations, the ordered set supports: - `order_of_key(k)`: Gives the count of elements smaller than `k`. &mdash; O(log n) - `find_by_order(k)`: Returns the iterator for the `k`th element (use `k = 0` for the first element). &mdash; O(log n)...

Full text and comments »

Competitive C++ Manifesto: A Style Guide # Competitive C++ Manifesto: A Style Guide There are many style guides for C++ out there, but we can't really use them as competitive programmers. We just want to write our code correctly as fast as possible! Trying to hack people here on codeforces, I realized there is a need for a style guide! Our goal is to write correct, fast, clear and consistent code. > #### Disclaimer > This is not a rulebook. You can integrate parts of it into your coding style. > Don't overthink it, especially during a contest! I'm going to use this guide for myself and to [teach my students](https://in.harbour.space/computer-science/modern-c-programming-hossein-yousefi/). I'm planning to make some good stuff in the future following these principles! Stay tuned! ## Compiler Make use of C++17. Use `-Wall -Wextra -Wshadow` flags for compilation, and try to eliminate all of the warning messages, this will prevent you from having some silly bugs. There are more debugging flags like `-fsanitize=un...

Full text and comments »

Using Constructors and comparison function in C++ - Using constructors in C++ ~~~~~ struct point { int x, y; point() {} // default constructor point (int _x, int _y) { x = _x; y = _y; } }; ~~~~~ Another way ~~~~~ struct point { int x, y; point() {} // default constructor point (int x, int y): x(x), y(y) {} }; ~~~~~ - Using Comparison function in C++. For information of operator overloading visit [link](http://www.cprogramming.com/tutorial/operator_overloading.html) ~~~~~ struct point { int x, y; point() {} point (int x, int y) : x(x), y(y) {} // overloading of < operator bool operator<(const point &rhs) const{ // your main logic for the comparator goes here return make_pair(x,y) < make_pair(rhs.x, rhs.y); } }; ~~~~~ **Now A Sample Implementation** Thanks to [user:Break-Neck,2013-11-17] for pointing out the problem with earlier a <= b in the code of cmp function, see the comment of [us...

Full text and comments »

Modular Arithmetic for Beginners Introduction ------------------ If you're new to the world of competitive programming, you may have noticed that some tasks, typically combinatorial and probability tasks, have this funny habit of asking you to calculate a huge number, then tell you that "because this number can be huge, please output it modulo $10^9 + 7$". Like, it's not enough that they ask you to calculate a number they know will overflow basic integer data types, but now you need to apply the modulo operation after that? Even worse are those that say you need to calculate a fraction $\frac pq$ and ask you to output $r$ where $r \cdot q \equiv p \pmod m$... not only do you have to calculate a fraction with huge numbers, how in the *world* are you going to find $r$? Actually, the modulo is there to make the calculation *easier*, not *harder*. This may sound counterintuitive, but once you know how modular arithmetic works, you'll see why too. Soon you'll be solving these problems like second nature. Terminol...

Full text and comments »

Notes on using Kotlin for competitive programming I pretty much exclusively use Kotlin for competitive programming, mostly because it's the language I'm currently most comfortable with. Here are some scattered notes and tidbits about my experience which I think might be useful to others; if you have any tips/suggestions, feel free to let me know. ### Primer - Kotlin has an official [primer for competitive programming](https://kotlinlang.org/docs/tutorials/competitive-programming.html). However, the IO code suggested there is only so-so; it's definitely better than `Scanner`, but you definitely can save a lot of runtime in heavy input problems by using the classic Java combination of `BufferedReader` + `StringTokenizer` <spoiler summary="My current IO template"> ``` @JvmField val INPUT = System.`in` @JvmField val OUTPUT = System.out @JvmField val _reader = INPUT.bufferedReader() fun readLine(): String? = _reader.readLine() fun readLn() = _reader.readLine()!! @JvmField var _tokenizer: StringTokenizer = StringTokenizer(...

Full text and comments »

Reusable modular integer for C++ (with static/dynamic moduli) <spoiler summary="A little bit about myself"> This is my first blog post on CF, and is probably a good starting topic for someone of my rating. Technically I'm not a CS, but an engineer who worked professionally as a software developer. CP was uncharted territory to me until recently, though now I find myself studying algorithms and working to improve my math skills so I can have fun solving difficult problems. :) </spoiler> So here's what I present: a structure for modular arithmetic operations which is short, reusable across static and dynamic moduli, supports 64-bit moduli and is as efficient as performing the operations manually. It requires the C++17 standard or newer. ### Motivation For the most part, there's obviously nothing novel about this idea: it was inspired by other blog posts ([63903](https://codeforces.me/blog/entry/63903), [23365](https://codeforces.me/blog/entry/23365)), as well as by various submissions to CF problems. On the other hand, I haven't come a...

Full text and comments »

TODO: Open addressing hash table on C++ Hello, Codeforces! In late December and early January, I wrote a proof-of-concept of separate service in C ++, to take out heavy data from the Codeforces Java-code to C++. Long time I have not written in C ++, experienced a funny sense of immersion into another world. I was surprised to find the lack of open-addressing hashmap in the C++ standard library, and indeed in the boost, and in other popular libraries. It is strange somehow, because often open addressing should be better than separate chaining both in time and memory. And since I intend to keep small objects, then sure. I quickly sketched a prototype that actually shows that open addressing in 2-3 times faster than the standard std::unordered_map. Here's the output of the benchmark on my laptop: ~~~~~ std :: map takes 15779 ms std :: unordered_map takes 4698 ms oaht :: hash_map takes 1473 ms ~~~~~ I think that there is no good implementation of such container in stl-style with the support of C++11 (move sema...

Full text and comments »

Hello World (1926G Solution) Hi everyone! I'm not sure that I'll be posting here very often, but I'll be mainly outlining interesting solutions to hard problems or just noting something worthwhile to think about for competitive programming. Although I recently promoted to the Silver division in USACO, I managed to fail horribly in solving graph problems. Before I was promoted, I also saw this issue from past Codeforces contests, especially in problem C (see [problem:1830A]). A recent example is [problem:1926G], which I couldn't manage to solve in-contest. After trying to upsolve it and looking at the main solution, I still didn't get how dynamic programming portion over the three types of water functioned. After a very long time searching up other solutions, I suddenly got inspired to do dp over whether music was played or not at a particular node. I wrote down all of the details of the dp because being a newbie, I do not see the solution very clearly. **Solution** Denote a p-node as a node tha...

Full text and comments »

Kotlin in ICPC <img src="https://kotlinlang.org/assets/images/open-graph/kotlin_250x250.png" align="right" style="height: 200px; margin: 5px;" alt="text"/> Let us introduce the new programming language in ICPC: Kotlin. It is modern and developing language created by our sponsor JetBrains. Kotlin is inspired by Java and as Java is named after the island. Currently, Kotlin programs are compiled into JVM bytecode, all Java written code can be used from Kotlin sources and Kotlin written code can be used from Java sources as well out of the box. Kotlin being developed now most of the standard libraries are Java library classes, making Kotlin a programing language that is already used in many projects being the main language of their development. Comparing to Java language some Java disadvantages fixed and new features added. Some of them we will see in today's solution of ICPC World Finals 2016 problem C ([problem:101242C]). Less boilerplate code and syntactic sugar added 1. **new** operator om...

Full text and comments »

lambda expressions and pairs #### Introduction In this entry I will show how to use lambda expressions to deal with a fairly common situation that arises in problems. Also this post is specific to C++ 11 and beyond where lambda expressions were introduced to the language. #### The Situation Sometimes in problems it is natural to store inputs in pairs. For example it may be important to keep track of both the size of an element and where it occurs in the input; or when an element has two important attributes. This usually results in a vector of pairs. Next it can be useful to apply an algorithm to this vector of pairs and this where lambda expressions shine. #### An Example For an example problem I will use the codeforces problem The Meeting Place Cannot Be Changed http://codeforces.me/problemset/problem/780/B. The idea of the problem is you have people at n points who each have a maximum speed and who want to meet. You have to figure out the minimum time they can meet. My solution is interesting for thre...

Full text and comments »

Struct – Pairs Hi everyone This is Lecture 1 of the series. We’ll start with **structs**, how to use them, constructors, operator overloading, and finally pairs. --- ## 1. Motivation (Why Struct?) We all know the basic data types: ```cpp int x; string y; ``` But let’s say we have a **company with 100 persons**. Each person has: * `name` (string) * `age` (int) * `salary` (float) Naive approach: ```cpp string name[100]; int age[100]; float salary[100]; cin >> name[0] >> age[0] >> salary[0]; ``` Problem: arrays are stored in **different places in memory** → not grouped. Solution → **Struct**: ```cpp struct Person { string name; int age; float salary; }; ``` --- ## 2. Using Struct ```cpp int main() { Person x; x.name = "Nourhan"; x.age = 21; x.salary = 3000; cout << x.name << " " << x.age << " " << x.salary << endl; } ``` Array of Persons: ```cpp Person p[5]; for (int i = 0; i < 5; i++) { ...

Full text and comments »

Simplest Input/Output Template Functions in C++ Hi Codeforces, Here's a blog on easy IO I've meant to write for quite some time and was finally able to put together. Motivation: For many contests, all code needs to be produced from scratch in contest, i.e. no templates unless you are willing to write them in contest. This means that if you are going to have a template, it needs to be planned out aptly to minimize the time it takes to write. One of the best things about templates is the ability to have easy IO functions. This means writing `re(a,b,c,d)` instead of `cin >> a >> b >> c >> d` and similar (such as something with `scanf` and formatters). The problem is, creating such functions from scratch can take a very long time if done traditionally (blatant recursive calls), and this also loses some efficiency in runtime. But I recently came upon a novel method that can streamline this very process called operator forwarding. The process is extremely simple: you can write the entire set of functions in only four li...

Full text and comments »

Full Java Topics (Core -> Advanced && JDBC) Here are all the Java topics from Core to Advanced (up to JDBC): CORE JAVA **Introduction to Java** 1. JDK, JRE, JVM 2. Data Types & Variables 3. Operators 4. Control Statements (if, else, switch) 5. Loops (for, while, do-while) 6. Arrays 7. Strings & String Methods 8. Methods & Method Overloading 9. Recursion **OBJECT-ORIENTED PROGRAMMING (OOP)** 10. Classes & Objects 11. Constructors 12. this Keyword 13. Inheritance 14. Method Overriding 15. super Keyword 16. Polymorphism 17. Abstraction 18. Encapsulation 19. Interfaces 20. Abstract Classes 21. final Keyword 22. static Keyword 23. Instance & Static Blocks **PACKAGES & ACCESS MODIFIERS** **** 24. Packages 25. Access Modifiers (public, private, protected, default) 26.import Statement **EXCEPTION HANDLING** 27. Types of Errors 28. try, catch, finally 29. throw & throws 30. Custom Exceptions 31. Checked & Unchecked Exceptions **JAVA I/O** 32. Scanner Class 33. BufferedReader ...

Full text and comments »

C++ BigInteger Library ~~~~~ C++ BigInteger Library ~~~~~ ~~~~~ // header files #include <cstdio> #include <string> #include <algorithm> #include <iostream> using namespace std; struct Bigint { // representations and structures string a; // to store the digits int sign; // sign = -1 for negative numbers, sign = 1 otherwise // constructors Bigint() {} // default constructor Bigint( string b ) { (*this) = b; // constructor for string } // some helpful methods int size() // returns number of digits { return a.size(); } Bigint inverseSign() // changes the sign { sign *= -1; return (*this); } Bigint normalize( int newSign ) // removes leading 0, fixes sign { for( int i = a.size() - 1; i > 0 && a[i] == '0'; i-- ) a.erase(a.begin() + i); sign = ( a.size() == 1 && a[0] == '0' ) ? 1 : newSign; return (*this); } // assignment op...

Full text and comments »

Handy C++ Class for Order Statistics: SortedArray (PBDS Wrapper) Hey everyone! I recently built a neat wrapper around GNU PBDS's ordered multiset to simplify operations like: - Counting how many elements are <, <=, >, or >= a value - Range frequency queries like [l, r], (l, r], etc. - Accessing the k-th smallest element (0-based) with [] operator It's named **SortedArray**, and it makes these operations intuitive using operator overloading. Use the code below and make sure you have ordered_set included from PBDS, ~~~~~ class SortedArray { ordered_multiset arr; public: long long size() { return arr.size(); } void operator += (long long x) { arr.insert(x); } long long operator < (long long x) { return arr.order_of_key(x); } long long operator <= (long long x) { return arr.order_of_key(x+1); } long long operator > (long long x) { return arr.size() - arr.order_of_key(x+1); } long long operator >= (long long x) { return arr.size() - arr.order_of_key(x); } long long LR(long long l, long long ...

Full text and comments »

How to implement own function to read int? I very much like $cin >> $ but want to have [this fast reading integers function](https://codeforces.me/blog/entry/8080?#comment-138179). How to do it? For example, I want to input multiple integers in this $cin >> a >> b >> c;$ but the reading of integers is using the comment above. I tried this but it didn't work. ~~~~~ istream & operator >> (istream& os, int x) { bool minus = false; int result = 0; char ch; ch = getchar(); while (true) { if (ch == '-') break; if (ch >= '0' && ch <= '9') break; ch = getchar(); } if (ch == '-') minus = true; else result = ch-'0'; while (true) { ch = getchar(); if (ch < '0' || ch > '9') break; result = result*10 + (ch - '0'); } if (minus) os >> -result; else os >> result; return os; } ~~~~~ But I got this error ~~~~~ error: ambiguous overload for 'operator>>' (operand types are 'std::istream' {aka 'std::basic_istream<char>'} and 'int') 124 | os >> result; | ~~ ^~ ~~~~~~ ...

Full text and comments »

How to resolve this error in overloading ostream operator to print template vector as well as primitive data types? Hi guys, hope you are doing well. I wanted to create my debug template but I can't get around this error? <spoiler summary="code"> ~~~~~ template<typename T> ostream& operator<<(ostream &out,vector<T> &v){ for(const auto &ele:v){ out<<ele<<" "; } return out; } template<typename T> ostream& operator<<(ostream &out,T x){ out<<x<<" "; return out; } ~~~~~ </spoiler> <spoiler summary="error"> error: ambiguous overload for 'operator<<' (operand types are 'std::basic_ostream<char>' and 'const char [2]') </spoiler> Can somebody please help me? Thanks in advance.

Full text and comments »

Generic Input/Output Implementations [First Blog] Hi y'all, Input/output is by and far the most frequently used concept in competitive programming, so I thought it might be a good idea to cover an optimization I developed in my first blog post. We all know cin/cout, although convenient to type up, tend to be jarringly slow in the context of CP. This is because cin and cout are tied together and synced to stdio. To evade this, many rely on the classical C methods of I/O: scanf/printf. For example, when dealing with an int $a$, they may write the following to read and write: ~~~~~ int a; int main() { scanf("%d", &a); printf("%d\n", a); } ~~~~~ But the syntax here is painful and definitely cannot be generalized to support a wider variety of types. To that end, it is well-known that we can keep the convenience of cin/cout without having to sacrifice for performance insofar as we untie cin from cout and unsync from stdio. For instance, we may write the below: ~~~~~ int a; int main() { cin.t...

Full text and comments »

difficulty in operator overloading Hi...<div><br></div><div>I am facing problem while operator overloading in the priority queue... my following code snippet return wrong..</div><div><br></div><div><div>struct node</div><div>{</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>int vertex, dist;</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>node() {};</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>node(int v, int d) : vertex(v), dist(d) {};</div><div>};</div><div><br></div><div>bool operator &lt; (node p, node q)</div><div>{</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>if(p.dist &gt; q.dist)</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>return true;</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>else if(p.dist == q.dist)</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>{</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>if(p.vertex &gt...

Full text and comments »

Matrix implementation allowing brace-enclosed initializer list in C++ When solving a matrix exponention task I found myself wanting to overload the multiplication operator and to able to initialize a matrix like I would initialize a short vector with known values, i.e., `vector<int> vec = {1,2,3};` Inheriting the struct from `vector<vector<int>>` seemed useful. Not only that would allow for easy initialization it would also provide access to [] operator and many other useful vector methods. I discovered that the constructor is not inherited :( There is however a workaround introduced in C++11 described on [stackexchange](https://softwareengineering.stackexchange.com/questions/197893/why-are-constructors-not-inherited). The final struct looks something like this: ~~~~~ struct Matrix:vector<vector<int>> { // "inherit" vector's constructor using vector::vector; Matrix operator *(Matrix other) { int rows = size(); int cols = other[0].size(); Matrix res(rows, vector<int>(cols)); fo...

Full text and comments »

Memory allocated by user defined data structures in C/C++ Somwtimes we use different user deffined data structures in C/C++. For example, ~~~~~ struct data1{ string name; int id; double marks; } ~~~~~ We can also use operator overloading and user defined functions in structers. ~~~~~ struct data2{ string name; int id; double marks; bool operator < (const data &a) const{ return id<a.id; } void addMarks(double x) { marks+=x; } } ~~~~~ Using operator overloading or user defined functions makes the use of these structures easy. Now my question is, when I declare an array or vector of a structure, will it allocate more memory if the structure contains some user defined functions in it? For example, if I declare two vectors of the structures declared above ( **data1** and **data2** ) like given below, will they allocate same amount of memory? ~~~~~ vector <data1> v1(1000); vector <data2> v2(1000); ~~~~~ Is the amount of memory allocated...

Full text and comments »

Compilation error on Codeforces while my PC compiles the code just fine I am trying to submit a code on Codeforces, but I always get compilation errors. My computer does just fine. Here is the code: ~~~~~ var s, tmp: ansistring; i, j, c: integer; function elim(var s: ansistring): ansistring; var i: integer; begin elim:=''; for i:=1 to length(s) do begin if s[i]='(' then elim:=elim+s[i] else if elim[length(elim)]='(' then delete(elim, length(elim), 1); end; end; begin readln(s); tmp:=elim(s); c:=0; if (tmp<>'((') and (tmp<>'))') then writeln(0) else if tmp='((' then begin i:=0; s:=s+'0'; while (s[i+1]='(') and (s[i+2]=')') do i:=i+2; for j:=i+2 to length(s) do if s[j]='(' then c:=c+1; writeln(c); end else begin i:=length(s)+1; s:='0'+s; while (s[i-2]='(') and (s[i-1]=')') do i:=i-2; for j:=i-2 downto 1 do if s[j]=')' then c:=c+1; writeln(c); end; end. ~~~~~ ...

Full text and comments »

Need help in custom comparators. Can anyone explain how to use custom comparators or provide a link? What confuses me the most is that for some comparator we write the comparator as a struct/class and overload the < operator while sometimes we just write a comparator that takes two instances returns true if first should be before second in ordering. I'll write the following snippets. Is there any difference in those two? It is just a preference? Or both are just different ways to write? If so, which is better? Also, we can just use lambda function to do this, which is much easier but I really wanted to know how traditional comparators worked. ~~~~~ bool comp(int& a, int& b) { return freq[a] < freq[b]; // Freq is a global array. } ~~~~~ To sort using above comparator we write, vector<int> arr = {0,5,6,1}; sort(arr.begin(), arr.end(), comp); ~~~~~ class comparator{ bool operator()(int& a, int& b) { return freq[a] < freq[b] ; } }; ~~~~~ To sort using thi...

Full text and comments »

The implementation of the Rational class using operator overloading: class Rational: def __init__(self, numerator, denominator): self.numerator = numerator self.denominator = denominator def __add__(self, other): # Calculate the numerator and denominator for addition numerator = self.numerator * other.denominator + other.numerator * self.denominator denominator = self.denominator * other.denominator return Rational(numerator, denominator) def __sub__(self, other): # Calculate the numerator and denominator for subtraction numerator = self.numerator * other.denominator - other.numerator * self.denominator denominator = self.denominator * other.denominator return Rational(numerator, denominator) def __mul__(self, other): # Calculate the numerator and denominator for multiplication numerator = self.numerator * other.numerator denominator = self.denominator * other.denominator return Rational(nume...

Full text and comments »

Custom Comparators for Priority Queue Custom Comparator for Priority Queue ------------------ STL: template <class T, class Container = vector<T>, class Compare = less<typename Container::value_type> > class priority_queue; i.e. the custom comparator for a priority queue is declared in a compare class by overloading the function call operator. #### CODE: ~~~~~ class compare{ bool operator()(pair<int,int> below,pair<int,int> above){ //return FALSE:requires swap //basically we write the condition which is ideal if(below.first==above.first){ reteurn below.second<above.second;//maxheap=>below should be smaller } return below.first>above.first;//minheap=>below should be larger } }; void solve(){ priority_queue<pair<int,int>,vector<int>,compare> pq; for(int i=0;i<3;i++){ pq.push({1,i}); } for(int i=0;i<3;i++){ pq.push({2,i}); } cout<<"we are designing the custom comparator such that its minheap acc t...

Full text and comments »

Taking input of the entire line of space separated integers without predefined size We know that in python, we can use the following to get a list of integers (space separated) in a line: ~~~~~ arr = list(map(int,input().split())) ~~~~~ This doesn't require us to input the number of integers in the line before. In C++ however, it is not that easy. But fortunately for us, most cp questions give the input `n` (size of the vector). What if we don't get the size beforehand, huh? Here's a possible fix.... ~~~~~ #define ll long long istream& operator>>(istream& stream,vector<ll>& a) { string line; getline(stream, line); istringstream lineStream(line); ll x; while(lineStream >> x) a.push_back(x); return stream; } ~~~~~ . <spoiler summary="How to use?"> 1) paste the above snippet in your C++ template 2) ~~~~~ vector<ll> a; // empty vector cin.ignore(); // Use only b/w a normal cin and the above overloaded cin, otherwise ignore this line cin>>a; // Vector now contains all the space separated inte...

Full text and comments »

Organized C++ Ordered Set and Multiset Hello everyone! After a long break from competitive programming, I’m back with something I wanted to have ready in my template: an ordered set and multiset with a clean member-function interface. One of the main reasons I created this project was to support the competitive programming community at Latakia University (Previously Tishreen University). I wanted contestants to have a reusable ordered-set and multiset template they can keep in their own templates and adapt to their problems. The project is **Organized C++ Ordered Set**. You can write `ordered_set<int>` or `ordered_multiset<int>`, access sorted ranks with `s[i]`, and use normal-looking bounds and erasure functions. It uses GNU PBDS with a strict comparator, including when duplicates are present. [Code, examples, and complete API reference](https://github.com/Tareq-Ali-1998/Organized-CPP-Ordered-Set) [GitLab mirror](https://gitlab.com/tareqali591998/organized-cpp-ordered-set) ## Usage first ```c++ ordere...

Full text and comments »

Can't compile file: Compilation process timed out. Hi guys. I wrote my segment tree structure using static buffer in order not to use heap memory. Locally my code was compiling OK, but at Codeforces it wasn't. I'd be grateful if somebody could explain me what's the problem. Here are links of my submissions. In [first](https://codeforces.me/contest/1251/submission/63374314) submission I had overloaded `new` operator for my segment tree structure. In [second](https://codeforces.me/contest/1251/submission/63375398) submission I've written my own function, which returns `void*`. Both submission I tried on all available GNU compilers, and any of them wasn't compiling. [Third](https://codeforces.me/contest/1251/submission/63375016) submission was sent using Microsoft C++ 2017 and it compiled fine. P.S. I know that I could have written segment tree using arrays instead of pointers, but it's too easy and boring :D

Full text and comments »

cin and printf together? There have been countless blogs about whether one should choose scanf/printf, or cin/cout as the main methods for getting inputs/outputs for C++. There are advantages and disadvantages of each kind, like the ability to easily format outputs, stream operator overloading, or not having to care about the decltype, etc. But, from what I have seen, there are rarely any blogs that I can find myself, that mention the combination of cin/printf. This seems like a pretty good combination, and I have seen one or two people using it. One can get inputs without having to painfully type `&` every time, and nicely formatted outputs without a bunch of `<<` operators. Is there any disadvantage of this combination? Why do we hardly see anyone using those together?

Full text and comments »

Do you guys make your own cin or cout? Do you write your own C++ code for cin and cout? Maybe operator overloading, templates. Like [user:Benq,2020-06-22]. What is the code for them? Sorry for bad english. :P

Full text and comments »

Optimizing Treap Code I am trying to solve this treap problem. http://poj.org/problem?id=3580 But it is getting TLE, though I think my solution is O(nlogn). If the code is poorly written how can I optimize it? Thanks for your help. Here is my code: http://paste.ubuntu.com/8533067/ Update: I got accepted by using an overloaded new operator(allocated 40mb at first). Here is accepted code: http://paste.ubuntu.com/8539750/

Full text and comments »

Strange behavior in C++ output? The output for this piece of code is not what I expected : ~~~~~ #include <iostream> using namespace std; int main() { int n = 10; cout << n << " " << n++; } ~~~~~ **OUTPUT** : 11 10 Is it because of the way iostream overloads bitwise shift operator or something else? ...

Full text and comments »

compare function in priority queue struct compare { bool operator()(node l, node r) { .... } }; We use above struct in the priority queue to define custom compare function. Why () operator overloading works? Thanks in advance..

Full text and comments »

A C++ debug header that prints anything, and a build that names the line you crashed on Hi Codeforces! A mod bug in my combination code recently cost me two wrong submissions on a Div. 3 problem C. Stripped down, it was this: ```cpp const int MOD = 1e18 + 7; // "big enough that I never need a real mod" ... fact[i] = fact[i - 1] * i % MOD; ``` `fact[i - 1] * i` overflows `long long` long before the `% MOD` runs, and the program happily printed garbage. Here is the same code in my current setup, first run, sample input: ``` ✗ Runtime error: UB trap, one of • signed overflow: a * b or a + b too big for long long • 1 << j with j >= 31: write 1LL << j • x / 0 or x % 0 • C-array index out of range → line 12: fact[i] = fact[i - 1] * i % MOD; ``` This post is about the pieces behind that: a debug header that prints anything you give it, and a build that catches the mistakes the judge only reports as "Wrong answer on test 2". Everything is on GitHub: [harly24-cp](https://github.com/Abhayanthk/harly24-cp). It works with any editor; I...

Full text and comments »

Dijkstra implementation without pairs I recently read that you could improve the performance of the Dijkstra algorithm by getting rid of pairs and doing comparison operator overloading (https://cp-algorithms.com/graph/dijkstra_sparse.html#getting-rid-of-pairs) Does anyone have this implementation?

Full text and comments »