Hello, Codeforces!

Today I want to share with you something that often gets brushed off because it's a very basic concept — 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 — 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 — 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 array, order, which will at first contain numbers from 0 to n - 1. We now simply sort according to the following lambda: sort(order.begin(), order.end(), [&values](int a, int b) { return values[a] < values[b]; });.

Let's break down the lambda expression. It contains three types of brakets:

a. square brakets containing captures — elements that are not parameters to the lambda but are captured for the use in the body of the lambda. In our example, we use values to compute order of elements in the array order. I recommend capturing references rather than objects themselves (that's why we have &values rather than values in the square brakets).

b. round brakets containing parameters — for sorting purposes those are always two elements of the same type as sorted vector elements (in case of vector<structs> you may also want to use references, ie. [](mystruct & a, mystruct &b) { ... }).

c. curly brackets containing body of our lambda — exactly the code that will execute and compute whether object a should go before b in sorted array. It should return bool value, that is true whenever we want to have a before b.

Now, when we have our array order sorted, it suffice to call colors[order[i]] and values[order[i]] to process the elements in the correct order.

2. We want to sort complex objects or we need more comparators than one.

Sometimes we need to sort objects that are more complex than basic integers / floats etc. Those use cases may include sorting weighted edges (ex. in Prim's MST algorithm), queries (which may later be required to reorder back to the original ordering), etc. In those two usecases we will rarely use captures and simply use relevant fields of sorted objects.

Let's say, that our problem includes ranged queries, to which the answer is a single integer. Obviously, we need to answer queries in order of appearience in the testcase. Let's also say that we discovered that processing those queries is very easy in the order of increasing length. We may then introduce a structure of a query:

struct query {
    int left, right;
    int ans;
    int index;
};

During reading input we need to assign something like queries[i].index = i for reordering back the queries. Now we may solve our problem with the following code:

sort(queries.begin(), queries.end(), [](query& a, query& b) { return a.right - a.left < b.right - b.left; });
// ... process queries with your observation in order 0..n-1 and assign computed answer to queries[i].ans;
sort(queries.begin(), queries.end(), [](query& a, query& b) { return a.index < b.index; });
for(query& q : queries)  cout << q.ans << endl; 

Example usage of this technique is problem 1513C.

Conclusion

Even though we all know and love sorting, in advanced uses writing comparator objects, functions or operator overloading may be a gruesome and time consuming task. Lambdas provide simple, short syntax for expressing complex sorting operations and are very fast to use during contests. I highly recommend getting used to this (seemingly weird) syntax and you will thank me later.

This is my first blog on Codeforces. Thank you very much for reading thus far :) If you notice some mistakes that can improve its quality, please let me know. Write in the comments which variant of sorting you prefer: lambdas, operator< overloading, comparator function or comparator object?

Have a great day,

Wielomian (or more like aeiilmnoW)