### Golovanov399's blog

By Golovanov399, 2 years ago,

Hello, codeforces.

I would like to tell you about some tricks and constructions I use in C++. They are not hidden or anything, moreover, most of them are from stl or maybe well known among software engineers, but I often see codes where something is done by hand in, say, 5 lines, while in stl there is a function which does the same.

The things below are filtered by my personal sense of non-popularity (so no __builtin functions) and usage frequency (so there almost surely are similar things I don't know about) and are not really sorted in any reasonable order. Let's begin.

• ### all(x)

This may be an exception to the rule of non-popularity -- this is quite widely used, but some next items will depend on all(x), so I define it here. So, I talk about

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


Now sorting a vector looks like sort(all(vec)) instead of sort(vec.begin(), vec.end()).

However, it's not all about this define. Imagine you need to build a convex hull of a set of points. Usually the code looks approximately as follows:

vector<Point> getConvexHull(vector<Point> pts) {
int min_pos = min_element(all(pts)) - pts.begin();
swap(pts[0], pts[min_pos]);
sort(pts.begin() + 1, pts.end(), &cmp);
// ...
}


And it might not come to one's mind that pts.begin() + 1 is the same as 1 + pts.begin(), and hence the code can be rewritten as

vector<Point> getConvexHull(vector<Point> pts) {
int min_pos = min_element(all(pts)) - pts.begin();
swap(pts[0], pts[min_pos]);
sort(1 + all(pts), &cmp);
// ...
}


Be, however, careful with this, because this reduces code readability significantly. Thanks to my teammates AndreySergunin and WHITE2302 for showing me this 1 + all(...) trick.

• ### std::unique

This is also well known, but not as well as I want, so I leave it here. std::unique(begin, end) goes from begin to end, removes consecutive duplicates and returns the end of the resulting iterator range. So, for example, if vec = {1, 1, 2, 2, 3, 2, 1}, then unique(all(vec)) makes it equal {1, 2, 3, 2, 1, ?, ?} (where ? is not known, but probably the last two symbols are 2 and 1) and returns vec.begin() + 5. Usually, to make a vector containing only its unique elements, one writes

sort(all(vec));
vec.resize(unique(all(vec)) - vec.begin());


or creates a function/define make_unique (which is, actually, also a name of some existing function in C++) which does so.

• ### nxt()

I noticed that many Kotlin Heroes participants often have some functions in their templates like readLong(), readToken() and so on. I understand that this may be for the sake of similarity with C++ paradigm where you can just read stuff or maybe because val (n, k) = readLine()!!.split(' ').map(String::toInt) is too long and weird for writing it just to read two numbers. However, what doesn't often come to mind is that a similar function in C++ can simplify a lot of things (or maybe it's just a matter of taste). So the function may look as follows:

int nxt() {
int x;
cin >> x;
return x;
}


If a usual reading a graph looks like this:

int n, m;
cin >> n >> m;
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
--u, --v;
g[u].push_back(v);
g[v].push_back(u);
}


then with your little mriemd nxt() you can write the following:

int n = nxt(), m = nxt();
for (int i = 0; i < m; ++i) {
int u = nxt() - 1, v = nxt() - 1;
g[u].push_back(v);
g[v].push_back(u);
}


However, be careful! If pts is a vector of points, then it's really better to read it in the following way:

for (int i = 0; i < (int)pts.size(); ++i) {
cin >> pts[i].x >> pts[i].y;
}


or at least in the following C++17 way:

for (auto& [x, y] : pts) {
cin >> x >> y;
}


But don't do the following:

for (int i = 0; i < (int)pts.size(); ++i) {
pts[i] = {nxt(), nxt()};
}


because in the last implementation the order of nxt() calls is not defined.

Also you may change the type to long long or even make the function template, but I haven't really ever felt I need the last.

Big thanks to my former teammates savinov and sokian for introducing this to me in their team template back in 2015 when I joined them. nxt() will return later in this blog.

• ### std::fill and std::iota

Many of you know that if one wants to fill a piece of memory with a specific byte, they can use memset. It's quite fast and can be used to fill some (usually 1-dimensional) C-arrays by zeroes and minus ones. What if you want to fill a container by ones? The answer is as easy as pie:

fill(all(vec), 1);


And if you need to fill it by consecutive numbers, you can use std::iota. Now the constructor of a Dsu class with two optimizations may look as follows:

int n;
vector<int> parent, rank;

Dsu(int _n): n(_n), parent(_n), rank(_n) {
iota(all(parent), 0);
}


Here 0 denotes the value of *parent.begin(), and each next value is obtained from the previous one by the pre-increment.

• ### std::generate

If you have a 0-ary function (that is, with no arguments) and want to fill a range by its calls, instead of writing a for loop you can call std::generate: filling a vector vec by random values (assume it's rand() calls) may look like

generate(all(vec), rand);


My favourite: to read $n$ followed by $n$ numbers you can write

int n = nxt();
vector<int> a(n);
generate(all(a), nxt);


or, if you don't need the value of n later, even

vector<int> a(nxt());
generate(all(a), nxt);


Bonus: the last three function have a _n analogs. Instead of the end iterator/pointer, fill_n, iota_n and generate_n take the size as the second argument. So if you want to read, say, first $n$ numbers into a vector vec of size greater than $n$, you can use

generate_n(vec.begin(), n, nxt);


generate(vec.begin(), vec.begin() + n, nxt);


Thanks to fdoer for telling this.

• ### std::rotate

Assume you write a profile dp. Or a 3-layer bfs. Or something else, where you need sometimes to cyclically shift a vector by $k$. If $k = 1$ then one can write a loop of swaps:

for (int i = 0; i < (int)vec.size() - 1; ++i) {
swap(vec[i], vec[i + 1]);
}


But if $k > 1$ then the easiest way to do this manually is probably to create another vector, fill it accordingly and then set the initial vector to this. However a simple

rotate(vec.begin(), vec.begin() + k, vec.end());


can do the trick. This function works in such a way that after rotate(begin, middle, end) the element *middle becomes the first from begin to end.

• ### std::merge

If you want to build a segment tree where each node contains a sorted list of values from the corresponding range then on its initialization you may need to merge two vectors several times (or if you implement your own merge sort). Some of you, probably, write some code like this:

for (int v = n - 1; v > 0; --v) {
int i = 0, j = 0;
while (i < (int)nodes[2 * v].size() || j < (int)nodes[2 * v + 1].size()) {
if (j == (int)nodes[2 * v + 1].size() || (i < (int)nodes[2 * v].size() && nodes[2 * v][i] < nodes[2 * v + 1][j])) {
nodes[v].push_back(nodes[2 * v][i++]);
} else {
nodes[v].push_back(nodes[2 * v + 1][j++]);
}
}
}


However, this code can be shortened:

for (int v = n - 1; v > 0; --v) {
nodes[v].resize(nodes[2 * v].size() + nodes[2 * v + 1].size());
merge(all(nodes[2 * v]), all(nodes[2 * v + 1]), nodes[v].begin());
}


Basically, std::merge takes 5 arguments: begin and end of one interval to merge, begin and end of the second interval to merge, and where to write the result. Don't forget to allocate the required memory (the purpose of .resize() in the code above)!

• ### Create a set from a vector

Not many of us know, but if you want to create a std::set from a vector and find out that set doesn't have a constructor of vector, you may go write a loop with an ok face, like:

set<int> S;
for (int x : a) {
S.insert(x);
}


However, std::set has a constructor of two iterators, so one can write

set<int> S(all(a));


This is actually very natural and one can deduce that set should have such a constructor, but I, to my shame, didn't know it until WHITE2302 told me this recently.

• ### Check if set or map have a key

This may be the most well known of above (as well as the least time-saving trick), but I still see that some experienced guys do the subj like

if (S.find(key) != S.end()) {
// ...
}


However, set and map have a .count() method which returns 1 iff the key is in the container, otherwise 0:

if (S.count(key)) {
// ...
}


The reason why it is called so and has an int type is that std::multiset and std::multimap also have this method, and for them the method returns the count of elements, which may exceed 1, obviously. Thanks to my former students dimaskovas and krock21 for enlightening me about this.

Of course, if you need to do something with the element, if it is present in the set (for example, erase it), it may be useful to actually call .find() method in order to erase by iterator, not by element (thus kind of caching one tree descent).

• ### Check if an element occurs in a sorted sequence

Assume that you have, say, a sorted vector, and you want to check if it contains an element, but unlike the previous case, you don't care about the element itself. In this case you don't need to implement your own binary search like

bool has(const vector<int>& vec, int key) {
int l = 0, r = vec.size();
while (r > l + 1) {
int m = (l + r) / 2;
if (vec[m] <= key) {
l = m;
} else {
r = m;
}
}
return l + 1 == r && vec[l] == key; // not to fall on the empty vector
}


if (binary_search(all(vec), key)) {
// ...
}


I think the function doesn't need any explanation (it returns bool, so there is really not much else one can extract from this). Thanks to some guy who used this method in some easy problem in an SRM.

• ### std::partition_point

If we talk about binary search: assume you have a vector and a predicate p(x) so that p(x) = true for all elements of some prefix of vector vec and false on all others. To find the first place where p(x) doesn't hold one can simply use

int pos = partition_point(all(vec), p) - vec.begin();


In other words, partition_point(begin, end, p) returns the first iterator iter that p(*iter) = false, assuming that the condition above holds, that is, p is true on some prefix of [begin, end). I didn't use this in competitive programming (yet), but once wanted to use it for my job. Thanks to fdoer again for sharing his wisdom.

• ### !!

Assume you want to use a function which maps 0 to 0 and every non-zero number to 1 (for example, to count non-zero numbers on all prefix subrectangles). The most observant of you may have notices that this is simply a cast to bool. The easiest bool casting operator is !! and it works like this:

for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
pref[i + 1][j + 1] = pref[i][j + 1] + pref[i + 1][j] - pref[i][j] + !!a[i][j];
}
}


Afaik, a mnemonic rule to remember it (if needed) is "bang, bang, you're boolean".

• ### Print a binary representation of a number

If you want to print, say, last 20 bits of a number, it's not necessary to write smth like

void show_binary(int n) {
for (int i = 0; i < 20; ++i) {
cout << !!(n & (1 << i));
}
cout << "\n";
}


cout << bitset<20>(n) << "\n";


However, you need to fix the number of bits to show (which is usually not a problem because in most of the cases you need it for debug purposes) and get used to the order where the lowest bit is the rightmost (which is actually a natural order for a binary representation of a number, but not so natural if you consider a mask as a sort of a boolean vector).

Also, if you want to print an octal or a hexadecimal representation of a number, you can simply write cout << oct << n << "\n" and cout << hex << n << "\n", respectively. To return back to normal decimal, use cout << dec.

• ### lambda type deduction

Imagine you want to quickly write a lambda which calculates the number of ways to choose $2$ elements from $n$. You may write something like this:

auto choose2 = [&](int n) {
if (n <= 1) {
return 0;
} else {
return 1ll * n * (n - 1) / 2;
}
};


and see that the compiler cannot deduce the type of your lambda: in one place you return int and in another place you return long long. Ok, you may think, let's show the type explicitly. without auto:

function<long long(int)> choose2 = [&](int n) {
if (n <= 1) {
return 0;
} else {
return 1ll * n * (n - 1) / 2;
}
};


To your surprise, the error doesn't disappear. You are not very happy, you replace 0 by 0ll and move forward feeling that you could surely have done this using some language tools.

Indeed, in the very first version you could actually explicitly specify the output type by a simple arrow:

auto choose2 = [&](int n) -> long long {
if (n <= 1) {
return 0;
} else {
return 1ll * n * (n - 1) / 2;
}
};


Big thanks to my friends and colleagues Wild_Hamster, ArtDitel and fdoer again for showing me this construction (not only in this context, however).

• ### Introducing variables inside an if statement

Imagine the following: you have a function f(), which takes time to be computed, and if its value satisfies some condition, you want to somehow use it. You don't want to write

if (is_good(f())) {
use_somehow(f());
}


since it costs two calls of f. You may write something like this:

int x = f();
if (is_good(x)) {
use_somehow(x);
}


but this is not very clean and leaves a variable which is not used then, maybe under a potentially useful name. To avoid this, one can wrap all this into a block like this:

{
int x = f();
if (is_good(x)) {
use_somehow(x);
}
}


but a shorter version would do the following:

if (int x = f(); is_good(x)) {
use_somehow(x);
}


This is possible since C++17.

• ### The smallest element from three

I bet many, many of you at least once wrote something like

int x = min(min(a, b), c);


feeling that something you do in your life is not right (while you type this, you usually have time to think about such things). Things get worse if you want to get a minimum of four elements:

int x = min(min(min(a, b), c), d);


(the order or arguments and the way to regroup them does not matter). You may have written a variadic template in your, well, template, to call something like min(a, b, c, ...), but you may do this without any prewritten code. Just watch:

int x = min({a, b, c, d});


Credits to the Jinotega twitter for this.

I'm sure I forgot something. I also feel that this blog is like a quick start guide into stl. Still, I hope a lot of you will find something useful here. C++, as every other language (programming or natural), is evolving, after all, and we should keep our eyes on how we can use it efficiently.

• +756

 » 2 years ago, # |   +44 I'm sure I forgot something I forgot to add that you guys are welcome to post similar tricks in comments if you think they are also useful!
•  » » 2 years ago, # ^ | ← Rev. 2 →   +4 The nth_element(all(X), n) gives the nth element from the first in the sorted list. I believe it uses randomized quick search to achieve the linear complexity. So, there's a side effect of a part of X being randomized during the call. This, I think, can be avoided if we call the method in another function which takes X as a call-by-value argument.
 » 2 years ago, # |   +93 About lambdas: auto choose2 = [&](int n) { if (n <= 1) { return 0LL; // You can also specify the 0 literal's type explicitly. } else { return 1LL * n * (n - 1) / 2; // I also recommend LL instead of ll to avoid confusion with 11. } }; About multiset::count and multimap::count: they work in $O(count + \log n)$, not $O(\log n)$ as one may expect. So do not use them at all if your container has a lot of duplicates.
 » 2 years ago, # |   +36 About unique: instead of vec.resize(unique(all(vec)) - vec.begin()); I prefer vec.erase(unique(all(vec)), vec.end());.
•  » » 7 months ago, # ^ |   0 yes, I use the same :)
 » 2 years ago, # |   +272 1 + all(ptr) is just wild
•  » » 2 years ago, # ^ |   +237 x + all(ptr) - y
 » 2 years ago, # |   +3 Very nice! my favorites:1- vector a(nxt()); generate(all(a), nxt); 2- std::partition_point3- !!4- cout << bitset<20>(n) << "\n";5- if (int x = f(); is_good(x)) { use_somehow(x); } 
 » 2 years ago, # | ← Rev. 2 →   0 to master std::rotate you can use this video (if I didn't mixed it with some other from Sean)
•  » » 2 years ago, # ^ |   0 It's a rotate!
•  » » 2 years ago, # ^ |   +6 It's easier to understand rotate as swap two ranges
 » 2 years ago, # |   +42 std::nth_element (I don't remember from where I got this function but I guess CP3 book.) which rearranges the list in such a way such that the element at the nth position is the one which should be at that position if we sort the list. templatevoid nth_element (RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last); first: Random-access iterator to the first element in the list.last: Random-access iterator to the last element in the list.nth: Random-access iterator pointing to the position in the list, which should be sorted. Where can use?It can be used to find the median of an array, find first n smallest / n largest numbers, but they may or maynot be ordered.Time Complexity of std::nth_element(): O(n)more details equal_range (thanks to pllk in his book) returns both the lower_bound and upper_bound pointers Where can use?the following code counts the number of elements whose value is x auto a = lower_bound(array, array+n, x); auto b = upper_bound(array, array+n, x); cout << b-a << "\n"; and then it should be shortened to: auto r = equal_range(array, array+n, x); cout << r.second-r.first << "\n"; 
 » 2 years ago, # | ← Rev. 2 →   -9 Can I ask a dump question ?In this code if (int x = f(); is_good(x)) { use_somehow(x); } Why is there only one ';' for the for-loops ?
•  » » 2 years ago, # ^ |   0 we don't have any for-loops there, only if
•  » » » 2 years ago, # ^ |   0 :v sorry, I dont know why but I thought that was a for-loops
•  » » 2 years ago, # ^ |   0 cppreference/if helps a lot. If Statements with InitializerIf init-statement is used, the if statement is equivalent to { init_statement if constexpr(optional) ( condition ) statement-true } 
 » 2 years ago, # | ← Rev. 2 →   +13 Well C++20 is coming soon, and the new features include a way to not use all() macro.
 » 2 years ago, # | ← Rev. 2 →   +36 About std::merge  nodes[v].resize(nodes[2 * v].size() + nodes[2 * v + 1].size()); merge(all(nodes[2 * v]), all(nodes[2 * v + 1]), nodes[v].begin()); This code can be shortened further:  // nodes[v].clear(); merge(all(nodes[2 * v]), all(nodes[2 * v + 1]), back_inserter(nodes[v])); 
•  » » 2 years ago, # ^ | ← Rev. 2 →   +8 You'd better nodes[v].reserve(nodes[2 * v].size() + nodes[2 * v + 1].size()) as well before using back_inserter to avoid reallocations.
 » 2 years ago, # | ← Rev. 3 →   -10 Thanks for the nice blog !!
 » 2 years ago, # |   +10 Thx for the nice blog, especially the last one T-T(*me thinking about hours of writing min(min(min(min(min . . .*).
 » 2 years ago, # |   +34 That's a lot of aliases for trivial loops.
 » 2 years ago, # |   +232 That's a nice collection of little things to make life easier, thanks.But I don't like the idea of such blogs because of how many novices view competitive programming. All these things won't make you able to solve more problems in less time, and even spending 2 minutes less time on writing your monstrous 300-line solution to simple 30-lines problem won't help you get better places.So, to all div2 people who thinks "That's what I needed": no, you need to train more. That is, if you want to get better.
•  » » 2 years ago, # ^ | ← Rev. 8 →   +24 "That's what I needed": no, you need to train more. That is, if you want to get better.But sir, I see some people have become GM (red) in one year (whereas I cannot solve div 2 A and B after 10 years and solving 10000 div 3A level problems on different OJs). So there must be some secret programming trick/library/macro and code editor/test case parser that you LGMs are hiding. I urgently need to become red so that I can show off to my Google interviewer and clinch a high paying job. Um_nik sir, please teach me how to give contests so that I can become red in 6 months.p.s. I will treat you to Biryani and Dosa for one year if you show me the secret backdoor.
•  » » » 2 years ago, # ^ |   +20 LoOooOoOLoOOooOoLoOOoOoOOooOooOOLoOooOOoOOoOOL. ROFL. LMAO.
•  » » » 2 years ago, # ^ |   0 Since when you guys will understand there is no short cut in this line
•  » » 2 years ago, # ^ |   0 See my 900 line premade function set for an example of div 2 noobs building monstrous codes rather than training! It not only includes many obscure, useless, functions, but several functions for which STD also provides implementation for!
 » 2 years ago, # |   +81 nxt() and 1 + all hacks seem to me too dangerous, they will save you several seconds when you write code, but one case per 20 you will lose 10 minutes to find strange bug
•  » » 2 years ago, # ^ |   -9 What can possibly go wrong with nxt()?
•  » » » 2 years ago, # ^ |   +26 You even wrote it in your blog. Sure there are several more cases when order is not defined.
 » 2 years ago, # |   +29 Other libstd functions I use are std::accumulate, std::partial_sum and std::is_sorted.
 » 2 years ago, # | ← Rev. 2 →   +26 I'm pretty sure that also guaranteed to work left-to-right. because there's a common trick to put everything in brace-initializer to make it ltr for (int i = 0; i < (int)pts.size(); ++i) { pts[i] = {nxt(), nxt()}; } 
•  » » 2 years ago, # ^ |   +20 It is guaranteed per #10 here: https://en.cppreference.com/w/cpp/language/eval_order
•  » » » 2 years ago, # ^ |   0 Ok, it seems that one day I've encountered the wrong order when I wrote Point p(nxt(), nxt()) or something like this and generalized this behaviour for all similar cases
•  » » » 2 years ago, # ^ |   -7 What about make_pair(nxt(), nxt())? Is order guaranteed then?
•  » » » » 2 years ago, # ^ |   +20 I don't think so -- make_pair is a function and eval order is not guaranteed for functions.
•  » » » » 2 years ago, # ^ |   0 Only {} cases are guarantied. Moreover, there are MSVC issues with the order of arguments construction in the case of {} style constructor call, like this: //some_type(std::vector, std::vector) //std::vector v some_type some{ v, std::move(v) }; //on MSVC vector(vector&&) may be called before vector(vector const&) I do not know does this problem affect expression evaluation order or not.
•  » » » 2 years ago, # ^ |   0 Good to know, that's another reason for switching to using list-initialization whenever possible.
•  » » » » 2 years ago, # ^ |   +8 struct point { int x; int y; }; struct line { point p; int c; }; line l{ 0, 0 }; //ok 
 » 2 years ago, # |   +2 Wow, this is such a helpful blog. Thanks for your work!
 » 2 years ago, # | ← Rev. 2 →   +26 std::minmax_element vector x = {1, 2, 3, 4}; auto it = minmax_element(all(x)); cout << *it.first << ' ' << *it.second << endl; output: 1 4 std::equal bool is_palindrome(string s) { return equal(all(s) - s.size() / 2, s.rbegin()); } 
 » 2 years ago, # |   +10 Note that if _GLIBCXX_DEBUG is defined, then lower_bound will give an error if the invariant is not satisfied: std::vector data {1, 2, 3, 2, 1}; std::lower_bound(begin(data), end(data), 2); // error, good However, partition_point will not: std::partition_point(begin(data), end(data), [&] (int x) { return x < 2; }); // no error It's possible to use lower_bound instead like this (but the intention is less clear) std::lower_bound(begin(data), end(data), std::monostate{}, [&] (int x, std::monostate) { return x < 2; }); std::monostate can be replaced by anything.
 » 2 years ago, # |   +20 Talking about ugly functional oneliners, one can use copy_n(istream_iterator(cin), n, A.begin()); to read n integers and write it to A, copy_n(istream_iterator(cin), n, back_inserter(B)); to read n integers and push them to B and copy(B.begin(), B.end(), ostream_iterator(cout, " ")); to write them to cout. Never actually used it, though.
 » 2 years ago, # |   0 We can use rall as well using the reverse iterator to do things like order a vector in descending order. #define rall(x) (x).rbegin(), (x).rend() And then sort(rall(vec)) instead of sort(all(vec)) and reverse(all(vec))
 » 2 years ago, # | ← Rev. 2 →   +28 One day I wrote a code for problem during a contest where I should know a number of capitals on prefix, something like this: std::string s; std::cin >> s; std::vector cap{0}; for (auto it : s) cap.push_back(cap.back() + std::isupper(it)); Of course, it was incorrect, because this function returns any non-zero value if 'A' <= it && it <= 'Z' and zero if not. It was a small part of program, so I debugged a 20 mins correct solution. Now I always use !!std::isupper(it) and !! with any function like this.
•  » » 2 years ago, # ^ |   0 Also, calling isupper and similar standard functions on values outside of [0;127) is undefined behavior, IIRC.
•  » » 2 years ago, # ^ |   +12 Not using "using namespace std;" in competitive programming is shooting yourself in a foot and getting absolutely nothing in return. Have you ever used abs on long longs :)? This is just evil what happens then.
•  » » » 2 years ago, # ^ |   0 https://en.cppreference.com/w/cpp/numeric/math/absWhy do you think abs on long long is a problem? It seems to me that there is an overload for long long in C++, not in C though.
•  » » » » 2 years ago, # ^ |   +14 Of course, if you use it with std then everything is fine. But if you don't preced it with std:: then it will compile as well and very likely work on samples and give very hard to find WA, because there is abs outside of std:: as well which works on ints only. Of course if you remember you should preced it with std:: then it is fine, but it is particularly evil trap and you can't really be sure you know all of them and how to prevent them. And again, absolutely no profit for not using std.
•  » » » 2 years ago, # ^ |   0 I prefer to use next tips and tricks when nobody sees: using namespace std; using namespace boost; using namespace experimental; using namespace pmr; using namespace __gnu_pbds; using namespace tr1; 
•  » » » » 2 years ago, # ^ |   0 Do you use boost on Codeforces?
•  » » » » » 2 years ago, # ^ | ← Rev. 2 →   +3 Only on atcoder.jp
•  » » » 7 months ago, # ^ |   0 Jiangly never used using namespace std, I wonder why.
•  » » 2 years ago, # ^ |   0 This is scary!! (O∆O)
 » 2 years ago, # | ← Rev. 3 →   +20 std::function choose2 = [&](int n) { if (n <= 1) { return 0; } else { return 1ll * n * (n - 1) / 2; } }; To your suprise this kind of code may work painfully slow (link) and it misuses the std::function type. The rule for competitive programming is: you never need std::function.The right version of the snippet is: const auto choose = [&] (int n) { return n <= 1 ? 0 : 1ll * n * (n - 1) / 2; }; 
•  » » 2 years ago, # ^ |   0 Well, your suggested code mustn't compile because of the same reason, that is: the results of ternary operator must have the same type, while 0 and 1ll * ... are of different types.Could you please elaborate why we should never use std::functions? They are very convenient sometimes, and i don't remember many cases when they were a bottleneck
•  » » » 2 years ago, # ^ |   0 The code of course compiles, because ternary detect common type for both expressions.I don't remember any case where it would significantly help but you can't easily replace with actual lambda type (except for recursion where slowdown may be quite significant and where it's still straightforward to avoid)
•  » » » 2 years ago, # ^ | ← Rev. 2 →   +10 In competitive programming you have the entire program in one TU (.cpp file) and you like never need to use TypeErasure classes (e.g. std::function or std::any) as you can preserve the entire type information with templates (mainly auto lambdas; see also: recursion). TypeErasure classes are very convenient when you need to pass the TU (or project) boundary (e.g. when you need to read open world input), but you will never do this on Codeforces.tl;dr version: std uses std::function only for std::thread (system API requires function type to be erased).
•  » » » » 2 years ago, # ^ |   0 I often use function dfs in competitive programming. It is very convenient if I want to modify local variables (such as vector color, for example). If I want to do this using an auto lambda, I have to pass the lambda reference into itself, which I find ugly. Usually I prefer the std::function, because usually it's only negligibly slower (otherwise I'd not use it).That being said, I don't agree with your statement "it was created only for this, so you competitive guys don't ever need it, because it's not for you".
•  » » » » » 2 years ago, # ^ |   -10 I've made the right recursive lambda example for you. "I have to pass the lambda reference into itself, which I find ugly" is just a mistake made by intuition and passing self is the right way to do the recursion. There are differences between language basics and C++ version is: you must provide compiler with as much information as possible (not to be confused with Java version: declare variables with interface types). This basic affects not only performance but also the ability of compiler to check your code and generate errors. Just look at this example: std::function lambda = [&] () { return lambda; }; //OK!!!! 
•  » » » » » » 2 years ago, # ^ |   0 To me seems that we talk about different things. You say that "passing self is the right way to do the recursion" while I only say about usability (maybe you mean something related to fixed point combinators in typed languages, but I can only guess). I may not understand completely what you mean by "the right way", but during the contest I will not waste time on using a longer and less convenient implementation, while I know another one just for my needs which works, no matter how passing the lambda into itself is "right".
•  » » » » » » » 2 years ago, # ^ |   0 So you will prefer the implementation with the same code length that is twenty times slower, uses like three times more stack and contains much more potential errors am I right?
•  » » » » » » » » 2 years ago, # ^ |   0 What do you mean the same code length? I don't need your combinator class
•  » » » » » » » » » 2 years ago, # ^ | ← Rev. 2 →   -10 Well ok I surely should not waste 1 more minute in the case I can not use prewrittens. This will surely never help me to avoid sudden TLs when the real std::function worst case happens, CPU branch prediction will fail and I will capture 5 references and overflow small object optimization so memory allocation and extra cache miss happen.
•  » » » » » » » » » 2 years ago, # ^ |   0 I get your point, but personally I have never encountered any problems connected with its slowness. Again, that's because when I need to write something that will work fast, I don't use std::function for that purposes (neither use I auto lambdas, I prefer ordinary functions).
•  » » » » » » » » » 2 years ago, # ^ |   -10 Lambda body is an ordinary member function and lambda without capture is an ordinary function.
 » 2 years ago, # |   +13 std::basic_string is rarely used but it's super cool. I wrote a blog post about it some time ago. Also std::valarray for implementing Gaussian elimination.
•  » » 2 years ago, # ^ |   +10 Yes, valarray is imba sometimes, I confirm
 » 2 years ago, # |   +9 I don't know how is it called but there is something like anonymous function in g++, here is code using anonymous function as a check function inside if: int l = 0, r = k; while (r - l > 1) { int m = (l + r) / 2; if (({ // check function implementation with result in ok ok; })) { l = m; } else { r = m; } } The result of the last expression is the result of function itself.
•  » » 2 years ago, # ^ |   0 using tuples to implement less operator in struct: struct day { int p, a, i; day(int p, int a, int i) : p(p), a(a), i(i) {} bool operator < (day x) const { return make_tuple(p, a, i) < make_tuple(x.p, x.a, x.i); } }; 
•  » » » 2 years ago, # ^ |   +14 std::tie(p, a, i) < std::tie(x.p, x.a, x.i)
•  » » 2 years ago, # ^ |   0 When we store -1 as uncalculated marker in our memoisation table, we can use ~ operator to check whether value calculated: int f(int x, int y) { if (~d[x][y]) return d[x][y]; int &res = d[x][y]; // do something with res return res; } memset(d, 255, sizeof d); f(n,m); 
•  » » 2 years ago, # ^ |   0 Could you provide a full, compilable example? I'm very interested.
•  » » » 2 years ago, # ^ | ← Rev. 2 →   +10 int n = 100; vector v(({ int x = 0; for (int i = 1; i <= n; ++i) { x += i; } x; })); assert(static_cast(v.size()) == n * (n + 1) / 2); It works on both gcc and clang.
•  » » 2 years ago, # ^ |   0 Inlining comparator, usually you need comparator only once in sort function in your code: struct MyStr { int a, b, c; }; vector v; // fill v sort(all(v), [](MyStr &a, MyStr &b) { return tie(a.a, a.b, a.c) < tie(b.a, b.b, b.c); }); 
•  » » 2 years ago, # ^ |   0 It's actually called statement expressions. If someone is interested, more info is available here.
 » 2 years ago, # |   0 this is such a beautiful post and helpful also. Thank you :)
 » 2 years ago, # |   +1 Some time ago I didn't know about the last trick (finding the smallest element from three). I horribly bashed the problem 1283E. Here is my solution: https://codeforces.com/contest/1283/submission/71453985
•  » » 2 years ago, # ^ |   +3 That was awful.
 » 2 years ago, # | ← Rev. 2 →   0 it was helpful
 » 2 years ago, # |   0 mymap.count(key). Is awesome.... I didn't know so many of the tricks.. thanks for sharing . Awesome blog..
 » 2 years ago, # |   +8 template void input(Args&&... args) { (cin >> ... >> args); } int main() { int a, b; string s; input(a, b, s); } or as lambda: auto input = [](auto&&... args) { (cin >> ... >> args); }; 
 » 23 months ago, # | ← Rev. 2 →   +12 Instead of templates, we can use auto in arguments of functions. Something like auto f(auto x, auto y, auto z). Example; Assembly If function that returns pair or own struct, we can use auto [x,y,z] = f();. It can be used in cycles for too. Example
•  » » 23 months ago, # ^ |   -6 (1) is a C++20 feature. auto function parameters only work in GCC because it has experimental support for it.I don't think it is a good idea to use an experimental feature.
•  » » » 23 months ago, # ^ | ← Rev. 2 →   0 Yes, it can be used in GCC compiler with version $\ge 6.1$. I think, that using experimental GCC features during a contest is a good idea if you are confident in them.
•  » » » » 23 months ago, # ^ | ← Rev. 2 →   0 dmkozyrev Can you please tell me. Why people use - Spoiler... auto I = [&](int n) { //Some code }in main function. Why do we use this.
•  » » » » » 23 months ago, # ^ |   +10 It is effective way to make a local for main function (lambda function) and capture all local variables in main above its implementation. Example#include int main() { int a,b,c,d; std::cin >> a >> b >> c >> d; auto p = [&](int x) { // calculate p(x) = a*x^3+b*x^2+c*x+d // coefficients a,b,c,d is captured from local scope return d + x * (c + x * (b + x * 1LL * a)); }; for (int x = -5; x <= 5; x++) std::cout << p(x) << ' '; } ideone
 » 21 month(s) ago, # |   0 Does the nxt() function that you’ve mentioned has any cons? Like increasing the runtime or something? I personally like this style of writing, but I’ve refrained from using it to be safe. Followup: Can we also define a readArray() to be used as vector A = readArray()? I believe that the reading done in our function has to be copied to A, so an additional $O(n)$. (Or am I wrong? I’m not very clear about how returning a local vector works in memory point of view.)
•  » » 21 month(s) ago, # ^ |   0 std::vector got move assignment operator so it's fine, nothing will be copied in this case
•  » » » 21 month(s) ago, # ^ | ← Rev. 3 →   +1 In statements like vector A = readArray(); it does not matter (it is not assignment).BTW, I would redefine all(x) macro as begin(x), end(x) to sort arrays as well.
•  » » » » 21 month(s) ago, # ^ |   0 Fair enough, but if you have a global array with MAXN elements, and you read the first n elements, then you probably don't want to sort the whole array, neither intentionally, nor accidentally, so I think that begin(x), end(x) is more a potential danger than a shortcut
 » 21 month(s) ago, # |   0 Nice Blog. Very Helpful.
 » 21 month(s) ago, # |   0 Similar to min({a,b,c,d}), do we have something like gcd({a,b,c,d})?
 » 10 months ago, # |   0 using ceil() functions sometimes gives wrong answer for int if we don't use double or float before it, I used to face the same problem not because the ceil() is badly written, because of my little knowledge about it. So alternatively I started using int a,b; int cile= a/b +(a%b!=0); The later part is to check if 'a' is divisible by 'b' or not,if yes the later part becomes '0' (false) thus returning a/b + 0, else becomes '1' (true) thus return **a/b +1 ** ,where is a/b is the integer division.
•  » » 10 months ago, # ^ | ← Rev. 4 →   0 A simple $1 + \dfrac{x - 1}{y}$ gives the correct $Ceil$ $division$ always..
•  » » » 10 months ago, # ^ |   0 gives the correct Ceil division always How about long long x = 9223372036854775807ll; long long y = 2;?
•  » » » » 10 months ago, # ^ |   0 Okay thanks for pointing it out, I have edited my comment.
•  » » » 10 months ago, # ^ |   +8 Still doesn't work if $x$ is negative or something. I tried writing a short implementation at some point, but it's surprisingly hard to get all the cases right in a short amount of code.
•  » » » » 10 months ago, # ^ |   0 i64 x = -101ll, y = 2; cout << ((x > 0) ? (1 + (x — 1)/y) : (x / y)); //Output is -50 Afaik this works when $x < 0$ and $y > 0$. If this is not the case then we can swap the signs of $x$ and $y$ such that $x < 0$ and $y > 0$. So this is the final one-liner which should work.  i64 x = 101ll, y = -2; cout << 1 + ((y < 0 ? -1*x : x) — 1)/(y < 0 ? -1*y : y) << endl; //Output is -50 Note that this line is based on the fact that $\dfrac{negative}{positive}$ always gives us a ceiled output. (Shown above)
•  » » » » » 10 months ago, # ^ |   0 Yeah, this is what I had to resort to, but it isn't the best code in my opinion (two branches are slow). You can do something similar for floor as well (the two cases get swapped, and the expression changes a bit too).
 » 10 months ago, # |   0 nxt() cannot read multiple data types.Of course, you can use nxtInt(), nxtLong(), nxtString(), etc.But we have a better sol: template T nxt() { // assert(0) } template<> int nxt(){/*...*/} template<> double nxt(){/*...*/} template<> std::string nxt(){/*...*/} // template<> // nxt(){/*...*/} Then, you can use nxt(), nxt(), etc. (You can even use custom types!)
 » 7 months ago, # | ← Rev. 3 →   -15 .
•  » » 7 months ago, # ^ |   +8 But why not just do something like { auto x=some_function(); do_something_here(); } 
•  » » » 7 months ago, # ^ | ← Rev. 2 →   0 .
•  » » » » 7 months ago, # ^ |   0 How do you define "disposable" and how is the variable in STommydx's example less disposable than in yours?
 » 7 months ago, # |   -23 To multiply a string n times. For example : "hi"*5->hihihihihi We can do the following : string operator*(const string& s, unsigned int n) { stringstream out; while (n--) out << s; return out.str(); } int main(){ string s = "hi"; string ans = s * 5; cout << ans << ln; // cout<
•  » » 7 months ago, # ^ | ← Rev. 2 →   +5 But why make multiple copies of string while pushing in stringstream and then write to cout, when you can do just write to cout? string s = "hi"; fill_n(ostream_iterator(cout, ""), 5, s); 
•  » » 7 months ago, # ^ | ← Rev. 2 →   +5 https://quick-bench.com/q/n-5F1v_hwm53ViP80oDL9Hs1U8wHmmmmm...... I need some time to reserch why my way is slower, though it's direct write to stream without copies.I gave you upvote:)P.S. https://quick-bench.com/q/snMbBBUOHrEbLy1w7CgpdRnlJK0, change "" to nullptr leads to speed-up. I believe it's because when delim is nullptr there is one operator<< calls instead of two per item.
 » 4 months ago, # | ← Rev. 2 →   0 We could define the nxt function as inline function. Since it is small and inline function will be fast;inline nxt() {body; }
 » 3 weeks ago, # |   -16 Cool