Hello, beautiful people of Codeforces.

Yesterday I spent several hours trying to solve the following problem, which feels that should be an easy dp. I then tried to search it on Google and failed. I feel like it's almost impossible to find solutions to algorithmic problems via search engines, they always return stuff that matches with one or two words from the statement but not the problem itself. Anyway, here's the problem:

You are given $$$n$$$ line segments $$$[l_i, r_i]$$$ ($$$1 \leq l_i \leq r_i \leq 2n$$$) and a number $$$k$$$. You are allowed to select $$$k$$$ points on the number line. What is the maximal number of segments that conitain at least one of the selected points you can obtain?

Example:

6
1 7
3 5
6 8
2 7
7 11
10 12
2

The answer is 5. We can select points 4 and 7, hitting all segmets but the last one. Hitting all segments is impossible, as [3, 5], [6, 8] and [10, 12] are disjoint. Note that even though segment [1, 7] is hitted twice, it is only counted towards the solution once.

We are also given that $$$k$$$ is much less than $$$n$$$. I expect the solution to run in $$$\mathcal{O}(nk)$$$ with possibly some $$$\log$$$ s.

Note 1: When k = 1 this is a well know problem and can easily be solved in $$$\mathcal{O}(n \log n)$$$:

1. Create $$$2n$$$ event of the form $$$(l_i, +1)$$$ and $$$(r_i, -1)$$$;
2. Sort the events by the first coordinate;
3. The answer is the maximal sum of the second coordinate over the events with the first coordinate up to some $$$i$$$ (this can be computed with a single loop);

Note 2: I called it a "dual" problem to another well know problem: Given $$$n$$$ line segments $$$[l_i, r_i]$$$ ($$$1 \leq l_i \leq r_i \leq 2n$$$), what is the minimal number of points to hit all the segments?

This "primal" problem is easily solvable in $$$\mathcal{O}(n \log n)$$$ by a greedy, selecting always the first end of not-yet-hit segments.

On the today's round I noticed something peculiar about Rating Changes. Particularly, let's compare my rating change and the change of a user taking 166th place.

• My final position in the ranking is 151 and their is 166.
• My rating before the round was 2378 and their was 2370.
• My delta was +8, and their was +35.
• My rating after the round is 2382 and their is 2405.

The interesting thing is the apparent lack of monotonicity. Finishing at higher position and starting with higher rating may not necessairly mean higher final rating.

Any thoughts?

Hello, fellow Codeforces fans!

During my training I select problems by their Problem Rating. But recently I noticed something peculiar about this feature. Namely, problems that have the same ratings may actually differ in hardness! The difference in hardness cannot be, in my opinion, explained by the rounding-to-the-nearest-100 rule, as my percieved difference should be sometimes in the order of 200-250. In my opinion this is connected to the Divisions system.

Suppose that I want to solve a 1900 rated problem from the Problemset. I noticed that in such situation I'm able to solve such a problem in around 15 mins if it comes from Div3, around 30 mins if it comes from Div2 and up to 50 mins for Div1 problems. Those times include implementation time.

My explaination for that is that a 1900 rated problem in Div3 is either F or G, in Div2 it's D or E and in Div1 it's A or B. If most participants solve problems in the A,B,C,... order, div3 participants have to solve 5 or 6 problems simply to reach this problem, let alone solve it during the round. Meanwhile, div1 participants would basically start by solving this problem.

In other words, if a round duration is 2 hrs, a (strong) div3 participant solving F or G will have some 40 minutes for this problem (as they spend say 80 minutes solving A-E/F). But div1 participant have full 2 hrs to solve their A / B problem, since they start the round with them. What I mean to say, is that the Problem Ratings of late-div3 problems is inflated -- most participants don't even manage to reach those problems, so they have a high "during the competition" failure rate and in consequence they seem harded than they really are. On the other hand, rating of early-div1 problems is deflated -- even if many participants will struggle for say over an hour, it will be counted as successfully solved "during the competition" thus decreasing the Problem Rating.

Other explaination that comes to my mind is that I'm simply biased and the Problem Rating System is working well. For example, maybe when I see "div3" next to the problem statement I'm more relaxed about the problem and the solution comes faster. And for "div1" problems I anticipate some nasty trick and overcomplicate solutions? Different bias could be a confirmation bias -- if I solved a div1 1900 problem in 15 minutes I would subconciously think something like "well that was obviously an outlier" while in fact on average all 1900 problems are similarly hard?

Do you think that there is something to it or am I simply too fast with conclusion? Do you think the system should take into account more parameters than "during-competition solvers rating" (e.g. problem number on the list, average time to submit the problem, or something else)? Do you think that Problem Ratings may be artificially influenced by cheaters or unofficial div1 participants? Please, comment you opinion because good Problem Rating System is very important for effective training.

Happy problem solving and many ACs, Wielomian

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)