| # | User | Rating |
|---|---|---|
| 1 | Um_nik | 3459 |
| 2 | tourist | 3438 |
| 3 | maroonrk | 3359 |
| 4 | ecnerwala | 3347 |
| 5 | Benq | 3317 |
| 6 | ksun48 | 3309 |
| 7 | boboniu | 3300 |
| 8 | Petr | 3293 |
| 9 | Radewoosh | 3289 |
| 10 | TLE | 3223 |
| # | User | Contrib. |
|---|---|---|
| 1 | Errichto | 206 |
| 2 | Monogon | 196 |
| 3 | SecondThread | 191 |
| 4 | pikmike | 187 |
| 5 | antontrygubO_o | 186 |
| 6 | vovuh | 183 |
| 7 | Um_nik | 182 |
| 8 | Ashishgup | 181 |
| 9 | Radewoosh | 169 |
| 10 | pashka | 168 |
There have been some questions about this comment (and its parents) and it seems different people understand the expression differently. So I wanted to create a poll.
If your answer is "depends on the context", vote based on the context of that comment.
I wanted to create this blog because there will probably not be really much discussion of solutions in the award ceremony (currently in progress). Also people who aren't finalists themselves can't see that anyway.
I'm interested to hear approaches of the higher-scoring finalists. (We, TÜ Randomized Algorithms did not do anything interesting :D)
A bit on the negative side: this seemed to be not be a 4-hour contest at all. The problem was kinda complex, I felt that I spent all the contest swamped in implementation, not being able to implement even 1/10 of the ideas I had. Well, it's also partially our fault for coming to troll in the finals with a 2-person team :P.
Also, did anyone manage to use the visualizer?
Recently there have been several suggestions that there is significant rating inflation now due to COVID-19. The typical hypothesis seems to be along the lines of:
Because people stay at home more now, there is a lot of new inexperienced users who add a lot of rating to the system, pushing "old" users upwards without actual improvement.
A simplified and a bit more general hypothesis that I'm going to test:
Because of the virus I'm gaining more rating than usual without working more.
But most of these comments are based on anecdotal evidence, which is not worth much. I wanted to see if there is any truth to these claims. Specifically, this blog is an implementation (although I modified the approach a bit) of the following comment by geckods:
Let's define the "test period" and "control period".
The test period refers to the period from 12 March 2020 to 12 Apr 2020. It was around 12 March when coronavirus became a big deal in most of the world, and for most of the Codeforces userbase. In that period, we had:
The control period is another period that should be "reasonably similar" to the test period, in terms of both length and the contests held. It should be from before coronavirus was known, even to China. It also can't be from too long ago. I have chosen 26 Sep 2019 to 26 Oct 2019. It fits all the criteria; as a matter of fact the "contest summary" is the exact same, except for an additional unrated Technocup mirror. But I have provided the code, you can try other periods and other period lengths.
Consider the users who were active during these periods: at least 3 contests in both periods. If our hypothesis is true, then the distribution of rating changes of these users would be different: these users would have gained more rating during the test period, compared to the control period. It also might be that there is rating inflation in Div. 2, but it has not "propagated" to Div. 1 yet, so it's interesting to see what happens if we take the initial rating into account.
In short, we are asking "Given an user who had rating $$$x$$$ at the beginning of the test period, what was their rating at the end of the test period?" and comparing it to "Given an user who had rating $$$x$$$ at the beginning of the control period, what was their rating at the end of the control period?".
I have implemented it here.
The graph on the left corresponds to the test period, the graph on the right corresponds to the control period. The color of the $$$i$$$-th row and $$$j$$$-th column corresponds to the probability that a participant with rating $$$i$$$ a the beginning of the period would have rating $$$j$$$ at the end of the period. Black corresponds to probability 1, white to probability 0.
I don't want to jump into conclusions from this data, I'll leave it up to you to interpret it. But just from these it seems that there is no serious inflation. Of course, one month is a short period to see the effects. And it does seem that the left graph shows a bit of inflation, but it's hard to tell. At least it seems to cast doubts on the "my rating has risen more without me working more!" claim. I think that if your rating has risen in the last month, you're just getting better even if you don't "feel better", don't worry so much about inflation :)
Disclaimer: I'm not very experienced in statistics, I just decided to implement this because no one else seemed to and I was also curious about what the result would be.
Hi.
Sometimes I use Codeforces groups for private trainings. On occassion, this means importing (via Polygon) problems from some other contests (that have public test data and are free to be used like that).
But when importing test cases "from the files" or "from the archive", this happens a lot: 
(By the way I have no idea why it happens so frequently. My best guess is sometimes that OI-style contests have to repeat test cases in different subtasks. But I have also seen this with ICPC-style.)
Anyway, my question is:
(I guess I should be smarter and write a local script to remove the duplicates).
The Open Competition is an annual week-long competition for Estonian high school students which serves as the first contest of the season. Just as in last year, we are welcoming international participants as well. The contest started on 14 October, 08:00 EEST and lasts a week, ending at 21 October, 00:00 EEST.
The contest consists of 7 problems with scoring distribution 20-30-40-50-60-60-60. The problems have partial scoring. The first five problems are "classical" problems of increasing difficulty, while the last two slots are reserved for output-only, interactive, out of scope, approximation, optimization — just in general "weird" problems. The problems are mostly aimed at Div. 2 level participants.
Problem statements will be available in Estonian, English and Russian. However, to register, you will need to navigate through a bit of Estonian.
Please note that you might not appear on the scoreboard immediately after registering.
(Huawei Marathon 2)
Inspired by people losing their mind over dp[mask][-1] here...
Sometimes you need to implement an array with negative indices. For example you may want to have an array dp[i] which stores values for all $$$i$$$, $$$-10^5 \le i \le 10^5$$$. One way is to make dp an (unordered) map. But this is slow and can get TLE in certain problems. Another way is this:
const int MAX_N = 2e5 + 20;
const int ZERO = 1e5 + 5;
int dp [MAX_N];
and instead of calling dp[i] you call dp[ZERO + i]. If I want to access dp[-5] for example, I access dp[ZERO - 5]. But this is tedious and error-prone. It's very easy to make a mistake by forgetting to write ZERO somewhere.
Do the above, but do it like this!
const int MAX_N = 2e5 + 20;
const int ZERO = 1e5 + 5;
int dp_ [MAX_N];
int& dp (int idx) { // the '&' is very important!
return dp_[ZERO + idx];
}
A very important part is that dp doesn't return an int; it returns an int& — a reference to the given position in the array. This means that it's very convenient to use. We can assign to dp(i), modify dp(i) etc.
int main () {
int main () {
dp(-300) = 7;
dp(40) = 5;
dp(-300) += 777; // All of those are fine!
cout << dp(40) << " " << dp(-300) << endl;
swap(dp(40), dp(-300)); // Even this works!
cout << dp(40) << " " << dp(-300) << endl;
}
This is a tutorial/exploration of problems that can be solved using the "DFS tree" of a graph.
For a way too long time, I didn't really understand how and why the classical algorithm for finding bridges works. It felt like many tutorials didn't really explain how it works, kind of just mentioned it in passing and quickly just moved on to implementation. The day someone explained what the DFS tree is, I finally understood it properly. Before, it took me ages to implement bridge-finding properly, and I always had to look up some detail. Now I can implement it at typing speed.
But more importantly, I began to see how the same techniques can be used to solve graph problems that have more or less nothing to do with bridges. The thing is, when you have a black box, you can only ever use it as a black box. But if you have a box that you understand well, you can take it into pieces, repurpose the pieces for completely different things, all without getting lost.
In my opinion, the DFS tree one of the most useful techniques for solving structural problems about graphs that I know of. Also, sometimes there are questionable greedy algorithms whose correctness becomes obvious once you think about the DFS tree.
Consider an undirected connected graph $$$G$$$. Let's run a depth-first traversal of the graph. It can be implemented by a recursive function, perhaps something like this:
1 function visit(u):
2 mark u as visited
3 for each vertex v among the neighbours of u:
4 if v is not visited:
5 mark the edge uv
6 call visit(v)
Here is an animation of what calling visit(1) looks like.
Let's look at the edges that were marked in line 5. They form a spanning tree of $$$G$$$, rooted at the vertex 1. We'll call these edges span-edges; all other edges are called back-edges.
This is the DFS tree of our graph:
Observation 1. The back-edges of the graph all connect a vertex with its descendant in the spanning tree. This is why DFS tree is so useful.
For example in the graph above, vertices 4 and 8 couldn't possibly have a back-edge connecting them because neither of them is an ancestor of the other. If there was an edge between 4 and 8, the traversal would have gone to 8 from 4 instead of going back to 2.
This is the most important observation about about the DFS tree. The DFS tree is so useful because it simplifies the structure of a graph. Instead of having to worry about all kinds of edges, we only need to care about a tree and some additional ancestor-descendant edges. This structure is so much easier to think and write algorithms about.
The DFS tree and observation 1 are the core of Tarjan's bridge-finding algorithm. Typical tutorials about finding bridges only mention the DFS tree in passing and start by defining weird arrays like $$$\mathrm{dfs}[u]$$$ and $$$\mathrm{low}[u]$$$: forget all that. These are implementation details, and in my opinion this isn't even the most intuitive way to implement finding bridges. In bridge-finding, $$$\mathrm{dfs}[u]$$$ is simply an obfuscated way to check whether one vertex is an ancestor of another in the DFS tree. Meanwhile it is even kind of hard to clearly explain what $$$\mathrm{low}[u]$$$ is supposed to represent.
Here's how to find bridges in an undirected connected graph $$$G$$$. Consider the DFS tree of $$$G$$$.
Observation 2. A span-edge $$$uv$$$ is a bridge if and only if there exists no back-edge that connects a descendant of $$$uv$$$ with an ancestor of $$$uv$$$. In other words, a span-edge $$$uv$$$ is a bridge if and only if there is no back-edge that "passes over" $$$uv$$$.
For example, in the DFS tree above, the edge between 6 and 2 isn't a bridge, because even if we remove it, the back-edge between 3 and 8 holds the graph together. On the other hand, the edge between 2 and 4 is a bridge, because there is no back-edge passing over it to hold the graph together if $$$2-4$$$ is removed.
Observation 3. A back-edge is never a bridge.
This gives rise to the classical bridge-finding algorithm. Given a graph $$$G$$$:
Because of the simple structure of the DFS tree, step 2 is easy to do. For example, you can use the typical $$$\mathrm{low}[u]$$$ method. Or, for example, you can use some kind of prefix sums, which is what I prefer. I define $$$\mathrm{dp}[u]$$$ as the number of back-edges passing over the edge between $$$u$$$ and its parent. Then,
The edge between $$$u$$$ and its parent is a bridge if and only if $$$\mathrm{dp}[u] = 0$$$.
Consider the following problem. Unfortunately I don't know if you can submit solutions somewhere. This is 118E - Дороги в Бертауне.
Problem 1. You are given an undirected connected graph $$$G$$$. Direct all of its edges so that the resulting digraph is strongly connected, or declare that this is impossible.
I know of a solution without using the ideas of DFS tree in linear time, but it is quite annoying and I would never want to implement this. Meanwhile, a DFS tree solution is very easy to implement in only a few lines of code.
Observation 4. If $$$G$$$ contains bridges, this is impossible.
So from now on, suppose that the graph doesn't have bridges. Let's look at its DFS tree. Direct all span-edges downwards and all back-edges upwards.
Observation 5. There is a path from the root to each vertex.
Observation 6. There is a path from each vertex to the root.
Therefore, the graph is now strongly connected! This solution can be implemented without an explicit reference to the DFS tree, but it is a very good example of proving the correctness using DFS tree.
Sometimes the DFS tree is just a way to represent a graph that makes implementation of certain things convenient. Like an adjacency list but "next level". This section is purely an implementation trick.
A cactus is a graph where every edge (or sometimes, vertex) belongs to at most one simple cycle. The first case is called an edge cactus, the second case is a vertex cactus. Cacti have a simpler structure than general graphs, as such it is easier to solve problems on them than on general graphs. But only on paper: cacti and cactus algorithms can be very annoying to implement if you don't think about what you are doing.
In the DFS tree of a cactus, for any span-edge, at most one back-edge passes over it. This puts cycles to an one-to-one correspondence with simple cycles:
This captures most properties of cacti. Often, it is easy to implement cactus algorithms using this representation.
For example, consider this problem:
Problem 2. You are given a connected vertex cactus with $$$N$$$ vertices. Answer queries of the form "how many distinct simple paths exist from vertex $$$p$$$ to vertex $$$q$$$?".
This is named appropriately: 231E - Кактус. The official tutorial has a solution like this:
It isn't very hard to understand why this works. The more interesting part is implementation.
- "squeeze" every cycle to a single vertex, and paint these vertices black;
Great. How?
After some time, most people will probably find some way to implement this. But here is a simple way using the DFS tree:
Step 2 can be done like this, for example:
1 function visit(u):
2 for each vertex v among the children of u:
3 visit(v)
4
5 if there is a back-edge going up from u:
6 cycleId[u] = the index of that back-edge
7 else:
8 cycleId[u] = u
9 for each vertex v among the children of u:
10 if cycleId[v] != v and there is no back-edge going down from v:
11 cycleId[u] = cycleId[v]
Problem 3. Consider an undirected graph. Find all the edges whose removal will produce a bipartite graph.
This is 19E - Фея. There is no official tutorial, but an unofficial tutorial mentions using complicated data structures like Link/cut tree. Using DFS tree, we can solve the problem without any advanced data structures.
In the original problem, the graph need not be connected. However, observe that:
Thus, the only interesting case is when we have exactly one non-bipartite connected component. Obviously the edge we remove must also come from that component, so we can just pretend that this is the only component. From now on, we assume that we have a non-bipartite, connected graph.
Let's consider the DFS tree of the graph. We can paint the vertices black and white so that each span-edge connects a black vertex and a white vertex. Some back-edges, however, might connect two vertices of the same color. We will call these edges contradictory.
Observation 7. A back-edge $$$uv$$$ is a solution if and only if $$$uv$$$ is the only contradictory edge.
Observation 8. A span-edge $$$uv$$$ is a solution if and only if the set of back-edges passing over $$$uv$$$ is the set of contradictory edges.
Thus, we can solve the problem as such:
What happens if we find the DFS tree of a directed graph? Let's run our depth-first traversal again:
1 function visit(u):
2 mark u as visited
3 for each vertex v among the neighbours of u:
4 if v is not visited:
5 mark the edge u->v
6 call visit(v)
To clarify, on line 3 we only mean such vertices $$$v$$$ that there is an edge from $$$u$$$ to $$$v$$$.
It might be the case that this traversal never reaches some vertices. For simplicity, we assume that:
visit(1);Let's call the edges marked at step 5 span-edges.
Observation 9. Span-edges form a rooted spanning tree, directed away from the root.
Other edges fall in two categories:
It's possible to further divide the back-edges into up-edges and down-edges based on their direction.
Observation 10. Cross-edges are always directed from the vertex that was explored later, to the vertex that was explored earlier.
The directed variant of DFS tree is used to construct the dominator tree of a directed graph, but that is a beast on a whole another level that warrants its own tutorial.
Solved in this tutorial:
Others:
If you know any other tasks that can be solved like this, share in the comment section! I might add them here, too.
Discussion of Интересные идеи в диапазоне 2300-2700(или 2000-3000)
Sometimes we see problems where a seemingly naive algorithm — for example simple brute force — is actually the correct solution. Mostly, I mean problems where, due to some clever observations, the complexity of the brute force algorithm is greatly reduced.
For example, in a recent contest we had 1168B - Good Triple. You can notice that any string of length at least 9 contains a "good triple", which means a brute force is sufficient here and runs in $$$O(n)$$$.
Or 1028F - Make Symmetrical where you can notice that on any given circle, there are not too many lattice points.
Randomized input is also a good source of these. In 896C - Willem, Chtholly and Seniorious you can observe that after a bit of time, most adjacent elements of the array are equal and write something seemingly naive based on that.
What are some other examples of problems where a stupid brute force is actually the correct solution?
The Baltic Olympiad in Informatics will be held in Tartu, Estonia from April 27 to May 2. Both days of the contest will feature an online mirror contest. We invite you to take part.
Both online mirrors will start one hour after the corresponding onsite contests. Both contests last 5 hours.
Solutions will be accepted in the following programming languages: C++, Java and Python. We have separate time limits for C++/Java and Python. Tasks have IOI-style batched partial scoring. Problem statements will be available in English and a multitude of languages spoken in the participating countries.
Some links:
Let's discuss problems here after the contests!
Can someone else staying at this hotel please tell me how to turn off that light:
This is urgent, I need some sleep before the finals.
The Open Competition is an annual week-long competition for Estonian high school students which serves as the first contest of the season. This year, we are welcoming international participants as well. The contest started on 15 October, 10:00 EEST and lasts a week, ending at 22 October, 00:00 EEST.
The contest consists of 7 problems with scoring distribution 20-30-40-50-60-60-60. The problems will have partial scoring. The first five problems are "classical" problems of increasing difficulty, while the last two slots are reserved for output-only, interactive, out of scope, approximation, optimization — just in general "weird" problems. The problemset should be interesting for most Div. 2 participants.
Problem statements will be available in Estonian, English and Russian. However, to register, you will need to navigate through a bit of Estonian.
Please note that you might not appear on the scoreboard immediately after registering.
#define rep(i, l, r) for ((i) = (l); (i) < (r); (i)++)
Things like that are pretty common. Why do so many of you need to do things like this? What is wrong with a good old for-loop? Is it that slow to write one explicitly?
I tried to add a problem prepared in Polygon to a mashup contest. Instead of the problem however, the statement shows this wonderful piece of art:
What is going on?
To my (untrained) eye, it seems that Codeforces servers are unable to handle the traffic that comes with a regular Codeforces round. If this is indeed so, a possible solution to alleviate the server load would be to simply limit the number of participants in any given contest: only allowing a fixed number of people to register for the contest — first come, first serve. A limited-access contest is better than "no" contest at all.
Should Codeforces do this? Discuss.
(of course if the issues originate elsewhere then don't mind this)
Title says it all. What are some of your favourite problems in competitive programming?
I was hoping to see discussion on the problems, but the announcement seems to have disappeared.
EDIT: Back up!
I often, not that often, but still often see things like this while hacking:
#define MIN(a,b) (a) < (b) ? (a) : (b)
#define MAX(a,b) (a) > (b) ? (a) : (b)
#define ABS(a) (a) > 0 ? (a) : -(a)
While these are not as common as other (dubious) preprocessor macros, I still see these being used fairly commonly. There are, in my opinion, several downsides to using these -- if the inputs were functions, one of them gets executed twice.
So I want to ask, is there any advantage to using these over std::min(a, b) and others?
