I wanted to suggest some improvements for the blog system. Some of these things have probably been said before. Some of these things should be pretty easy to implement, others are harder and might require a complete rework. I tried to put the easy things first.

Let's do something about necroposting

This is probably my biggest pet peeve about Codeforces blogs. Most of the time, Recent Actions is filled with very old blogs, some of which have been brought up for pretty much no reason at all. Currently, we have useful C++ "library from 2013 in Recent Actions, where the recent comment answers an old question which has already been answered better. Similarly, there is How to add friends? which was brought up to make some joke that has already been done.

The thing is though, a lot of the time these blogs are not brought up by trolls or anything like that. They are brought up by helpful people who simply did not notice that the blog is old and the question has already been answered. Sometimes people reply to those guys with angry comments, but that doesn't do much because people don't make that mistake more than once — we just have a constant stream of new users doing that. And it isn't good to chastise people for trying to be useful. My suggestion is to just prevent people from accidentally doing that. I propose that if you are replying to an old blog with no activity in the last 6 months, you get a popup saying something like

The most recent activity in this blog was X years ago. Are you sure you want to write a reply? It's not recommended to reply to old blogs without a good reason.

There are a few types of necroposting that I find annoying but can be argued to have a good reason:

• replying to an old tutorial with "thank you" (because these tutorials can be useful now and if they are in Recent Actions, they are seen by younger people);
• replying to an old editorial with "please debug my code" (because posting a new blog is pretty much equivalent).

In my ideal world, these replies wouldn't be necessary, but more about that later.

Don't allow users to delete blogs

The issue here is that if you delete a blog, then you delete all the discussion that happens in the comments. In my opinion, once you have posted a blog, it's not really yours to control anymore. It "belongs" to the community. Sometimes there is some important discussion in the comments that just gets deleted on the author's whim. Sometimes I put hard work and effort into writing a comment, only to discover the next day that the author of the blog has undone all that with the click of a button. We already can not delete comments. Why should we be allowed to delete blogs?

There can be some reasonable reasons to delete blogs, but they can be handled in other ways.

• if a blog is against the rules, it will be moved to drafts by CF moderation (this is already being done).
• if a blog is just spam, it will get downvoted and will disappear from Recent Actions (this is also already being done).
• if you are ashamed of the blog or something along these lines, you can edit the blog and disallow viewing history, but you won't delete other people's thoughts by doing that.
• if you have a really serious reason for deleting the blog, you can reach out to CF administration.

I also suggested that in a comment yesterday, but the blog got... deleted.

Have a separate place where beginners can ask questions

There have been attempts to create some megathreads for that, but they have always been unofficial and they have always eventually just disappeared, and beginners have gone back to making new blogs or posting under old editorials. For this to work, it needs to be official and there needs to be an official access point.

Also, it needs to have some sticky posts. There are a few recurring points that will solve a large part of the problems beginners have. For example, we have Codeforces Round #FF(255) Editorial and Codeforces Round #134 in Recent Actions currently, and both of them are there because a beginner asked a question of the type "my solution prints different output on Codeforces". Almost always, the solution to that is "You have undefined behavior, use tools like -fsanitize=address to find out where it is. There are two other typical problems:

• "I have WA and I can't find a reason" — the solution is to write a very simple and naive solution, a program that generates small random tests and a program that compares the output of the two solutions.
• "I have TLE" — the solution is to learn what the words "time complexity" mean.

Beginners need to see these things before asking a question. And the only way to ensure that is to have some kind of sticky or readme before you ask a question.

Have a separate place for educational resources

This was once suggested here, but it is not implemented. Again, there have been some unofficial attempts to create "lists of tutorials" but they will get similarly buried and updating them depends on the author. Again, for something like this to work, it needs to be official and it needs to have an official access point. Otherwise, it will get buried and obsoleted. EDU is somewhat like that, but it's a bit different — EDU is more like an online course platform, while tutorials can be all kinds of community-created resources that need not follow the EDU format.

Make the blog system into a forum system

This is the ultimate one and it would solve the two previous problems automatically. The real problem is that Codeforces has a blog system, but it has grown into a stage where the blog system is practically used as a forum system, except it doesn't have typical forum features. Currently Recent Actions is the only access point to the blog system, and it is very inflexible.

If we had a forum system, we could have sub-forums "Contest announcements", "Contest editorials", "Beginner questions", "Tutorials", "General discussion" etc. In each of them, you could sort the threads by most recent action, allowing you the same experience as Recent Actions currently has, but with none of the annoying blogs that you don't want to see. Sub-forums could have sub-forums of their own, allowing us to create a separate discussion thread for every problem in every contest (something that has been requested several times). Or to create different sub-forums for different difficulty levels of tutorials, allowing "ODE and differential technique" to not be buried in a sea of "DP for beginners, part 7". You could create sticky threads, solving the problem of beginners asking questions that have a standard solution. And so on.

There was a blog today with a similar title, and although it was (I think, not really sure as I didn't get a good look) some kind of satire/joke blog, I wanted to post some serious advice about things I (don't) like to see when people are PMing me. However I decided that this wouldn't be in the spirit of the blog and decided to make a separate blog. And now that blog is deleted anyway.

While it's not a bad thing to write messages to more experienced users, most people who write me do things that make them very difficult to deal with. These are my opinions, but somewhy I feel that many reds will agree. Some things here feel silly to write because they are so obvious. But I'm only writing them because people regularly mess them up.

Use punctuation and spelling.

There are some very simple rules that make your messages infinitely more readable. I find it especially strange when many of these messagers call me "sir", which is supposed to show respect, but then write like this. Is this how you write to someone you respect? Do you write to your teachers or boss like that?

Don't be pushy.

The worst case was when someone contacted me by email, and 20 minutes later sent another message "please reply ??". Think about it like this: you are writing someone who you don't know, who you don't have any previous agreement with and whose job is not to reply to you. I think you aren't automatically entitled to a reply at all. And although I try to reply to most messages, I think it's very rude to expect them to reply in less than a day or even two. Replying to you is not anyone's top priority.

Don't overstay your welcome.

A big reason why I'm wary of responding to PMs is that many people treat this as an invitation to ask 1000 more questions. Of course it's normal to have some followup questions and maybe write again another time, but there comes a point where you just being to annoy. You should understand when that moment comes and stop before.

Don't ask people to debug your code.

I will send the following template message if you get WA/RE:

Have you tried the following:

• Write a very naive and simple solution to the problem (maybe exponential complexity) (if you can, you may also just copy someone else's solution)
• Write a program to generate thousands of small (!) test cases
• Using those two, find a test case where your program gives the wrong answer
• Use print statements or a debugger to see where exactly your program does the wrong thing.

98% of WAs and REs can be resolved this way. I don't have time to delve into every code I'm sent, it's much harder to debug somebody else's code and being able to debug your own code is a valuable skill. It is also a very routine process that can be learned much faster than problem solving and algorithms.

And if you get TLE, make sure before writing that:

• you know what complexity is and
• you read/print input efficiently (sync_with_stdio and friends).

On that note, by the way: cin.tie(NULL) is useful but cout.tie(NULL) doesn't do anything.

Don't go in over your head

This section feels somewhat controversial to write, but I have some bad experience from the past with people who have asked help understanding some advanced tutorials. I accepted but every time it became evident after some time that the person did not yet have the capacity to understand this advanced algorithm or DS.

There is some amount of mathematical/algorithmical maturity needed to understand some complex things. (I don't think that you must have a high rating to understand, after all many top computer scientists haven't even heard of CP, but real understanding of simpler things is required). Moreover, you can not expect complex tutorials to hold a beginners hand and explain everything in such basic terms that anyone will understand. Mathematics (and the kind of CS we do here is basically mathematics) is cumulative and builds upon itself. Abstract stuff requires experience with concrete stuff, complex algorithms use many simple algorithms as subroutines. And you should be able to read some quite dry or terse mathematical text without someone showing you "what this intuitively means" at every little step.

Speak in a language the receiver will understand

It's surprising but I have received a number of messages in languages I don't understand. Now of course you can't really know, but use common sense here. For example, my profile will tell you where I live. If I don't live anywhere near Bangladesh and don't even have a South Asian name, what is the probability that I can understand your message in what I think is Bengali? Same goes for any other language.

Thoughts some common questions

• "Please give me some guidance" I have no idea what to answer. If you have some specific question, write.
• "Should I sort by number of solves or by difficulty?" Please understand that there is no consensus or real science on "how CP should be practiced". Furthermore, such questions likely have very little effect on your practice.
• "How many minutes before looking at the editorial" I will say "until you have solved it". I will also point out that many strong contestants have conflicting views and thus I think it's not the most important thing.
• "Can you give me some resources" If you ask something specific, maybe I have something good. But 99% of the time I will just send links to train.usaco.org and cses.fi/book.
• "The resources you sent are too hard" See the part about going in over your head. Also I don't know what you expected but some people expect resources where you don't need to think to understand. This is an unrealistic expectation.
• "How do you approach problems like X" In high school algebra and calculus you often have well defined recipes that tell you how to solve every problem (of some specific kind) ever. I suspect some people think this applies to CP as well. It doesn't. Most of the time, there is no "standard first step" that you do, you just have to think. But if you have enough experience, many problems have solutions that become obvious immediately.
• "Can you be my mentor" No.

In gneeral I must say (this is about me though, not necessarily other reds) that I'm much more likely to be able to answer technical questions (specifics of some problem, solution, algorithm...) than "career" questions ("how to practice" and similar). If you have a question in the latter category, it may be a good idea to write to someone else.

Concluding words

Unfortunately I don't think this is going to have a big effect because many of these people who write PMs are beginners who aren't going to see this blog. It would be a really cool feature if I could set some kind of "status" that is visible at the "send message" panel.

See this and this for example.

It seems that sometimes after writing an equation on a separate line with Latex like [dollar][dollar][equation][dollar][dollar], the next equation written inline like [dollar][equation][dollar] doesn't work.

From some experiments it seems like Codeforces internally changes single dollar signs to triple dollar signs if there is a match, and uses those to delimit Latex. I suspect the double dollar signs screw up the parser and after an inline equation, the single dollar signs won't get converted.

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?

Introduction

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:

Methodology

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:

• 2 Div. 1 contests
• 5 Div. 2 contests
• 2 Div. 3 contests
• 2 Educational rounds
• 1 Global round

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.

Results

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:

• Why does Polygon even care if there are multiple equal tests? It doesn't seem to care if there are two equal tests from generators.
• Why does it only show one error at a time, and a seemingly random pair at that (It doesn't seem like it is the "lexicographically smallest" pair)?
• Can I somehow turn this validation off? There are some (probably more important) checks that you can turn off.

(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.

• Registration (Google Translate works well; foreign participants should sign up in the "other" category and enter the country name in the "school/institution" field)
• Ranking
• The contest itself

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...

Motivation

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.

The solution

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;
}

Introduction

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.

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.

Suppose that there is an edge $$$uv$$$, and without loss of generality the depth-first traversal reaches $$$u$$$ while $$$v$$$ is still unexplored. Then:

• if the depth-first traversal goes to $$$v$$$ from $$$u$$$ using $$$uv$$$, then $$$uv$$$ is a span-edge;
• if the depth-first traversal doesn't go to $$$v$$$ from $$$u$$$ using $$$uv$$$, then $$$v$$$ was already visited when the traversal looked at it at step 4. Thus it was explored while exploring one of the other neighbours of $$$u$$$, which means that $$$v$$$ is a descendant of $$$u$$$ in the DFS tree.

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.

Finding bridges (or articulation points)

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$$$.

Removing the edge $$$uv$$$ splits the spanning tree to two disconnected parts: the subtree of $$$uv$$$ and the rest of the spanning tree. If there is a back-edge between these two components, then the graph is still connected, otherwise $$$uv$$$ is a bridge. The only way a back-edge can connect these components is if it connects a descendant of $$$uv$$$ with an ancestor of $$$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$$$:

1. find the DFS tree of the graph;
2. for each span-edge $$$uv$$$, find out if there is a back-edge "passing over" $$$uv$$$, if there isn't, you have a bridge.

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$$$.

Directing edges to form a strongly connected graph

Consider the following problem. Unfortunately I don't know if you can submit solutions somewhere. This is 118E - Bertown roads.

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.

If $$$uv$$$ is a bridge and we direct it $$$u \to v$$$, then there is no path from $$$v$$$ to $$$u$$$.

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.

You can simply move down using the span-edges.

Observation 6. There is a path from each vertex to the root.

Consider a non-root vertex $$$v$$$; let $$$u$$$ be its parent in the spanning tree. Because the graph contains no bridges, there must be a back-edge passing over $$$uv$$$: it connects a descendant of $$$v$$$ to an ancestor of $$$u$$$. We can move downwards from $$$v$$$ until we reach that back-edge, then use it to move to an ancestor of $$$u$$$. This way we have moved at least one step towards the root. Repeat until we reach 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.

Implementing cacti

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:

• each back-edge forms a simple cycle together with the span-edges it passes over;
• there are no other 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 - Cactus. The official tutorial has a solution like this:

1. "squeeze" every cycle to a single vertex, and paint these vertices black;
2. root the tree;
3. for each vertex $$$u$$$, calculate the number of black vertices on the path from the root to $$$u$$$; denote this $$$\mathrm{cnt}[u]$$$.
4. the answer to query $$$(p, q)$$$ is either $$$2^{\mathrm{cnt}[p] + \mathrm{cnt}[q] - 2 \mathrm{cnt}[\mathrm{lca}(p, q)]}$$$ or $$$2^{\mathrm{cnt}[p] + \mathrm{cnt}[q] - 2 \mathrm{cnt}[\mathrm{lca}(p, q)] + 1}$$$ depending on the color of $$$\mathrm{lca}(p, q)$$$.

It isn't very hard to understand why this works. The more interesting part is implementation.

1. "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:

1. give each back-edge an unique index starting from $$$N + 1$$$;
2. for each vertex $$$u$$$, calculate the index of the back-edge $$$u$$$ is under; call that $$$\mathrm{cycleId}[u]$$$; if $$$u$$$ isn't in a cycle then $$$\mathrm{cycleId}[u] = u$$$;
3. form a new adjacency list where for each $$$u$$$, each instance of $$$u$$$ is replaced by $$$\mathrm{cycleId}[u]$$$.

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]

Removing edges to form a bipartite graph

Problem 3. Consider an undirected graph. Find all the edges whose removal will produce a bipartite graph.

This is 19E - Fairy. 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:

• if the graph has no non-bipartite connected components, then removing any edge will produce a bipartite graph;
• if the graph has multiple non-bipartite connected components, then it is not possible to make the graph bipartite.

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.

If we remove the only contradictory back-edge, the graph-edge now has a coloring in two colors, thus it is bipartite.

If there are other contradictory edges or we remove a non-contradictory edge, the remaining contradictory edges will continue to form odd cycles and the graph won't be bipartite.

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.

If we remove a span-edge $$$uv$$$, the spanning tree will split into two parts: the subtree of $$$uv$$$, and the rest. The other span-edges still must have a white vertex on one end and a black vertex on the other in any bipartite coloring. Thus, the only other possible way to color the graph with two colours is if we flip the colors in the subtree of $$$uv$$$.

The removed span-edge $$$uv$$$ is then a solution if and only if flipping the colors eliminates all contradictions and doesn't generate new ones. This happens if and only if the contradictions are exactly the edges from the subtree of $$$uv$$$ to the rest of the graph.

Thus, we can solve the problem as such:

1. find the DFS tree of the graph and paint it in two colors;
2. if there is exactly one contradictory back-edge, add it to the answer;
3. use dynamic programming to calculate, for each span-edge, how many contradictory and how many non-contradictory back-edges pass over it;
4. if a span-edge has all contradictory and no non-contradictory edges passing over it, add it to the answer.

Directed variant

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:

• we started the traversal at vertex 1, i.e. called visit(1);
• it is possible to reach every vertex from the vertex 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:

• edges that connect an ancestor with a descendant: back-edges;
• edges that don't: cross-edges.

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.

Suppose there is a directed edge $$$u \to v$$$, and the depth-first traversal reaches $$$u$$$, but hasn't yet explored $$$v$$$. Then:

• if the traversal doesn't go from $$$u$$$ to $$$v$$$, it means that the traversal already visited $$$v$$$ during exploring some of the other children of $$$u$$$ and thus $$$u \to v$$$ is a back-edge;
• if the traversal does go from $$$u$$$ to $$$v$$$, then $$$u \to v$$$ by definition is a span-edge.

Thus the only way $$$u \to v$$$ could be a cross-edge is if the traversal reaches $$$v$$$ before exploring $$$u$$$.

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.

Problems for practice

Solved in this tutorial:

• 231E - Cactus
• 19E - Fairy

Others:

• 858F - Wizard's Tour
• 412D - Giving Awards
• 101612G - Grand Test
• any task where you have to find a block-cut tree

If you know any other tasks that can be solved like this, share in the comment section! I might add them here, too.

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.

• Mirror of day 1 takes place on April 29, 10:00 EEST;
• Mirror of day 2 takes place on May 1, 10:00 EEST.

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:

• Main page of BOI 2019
• Registration to the online mirror
• Live ranking of onsite contest
• Live ranking of online mirror
• Final results (the above two links will likely die/be reused for something else soon)
• Tasks, tests and solutions

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.

• Summary of the rules in English
• Registration (Google Translate works well; foreign participants should sign up in the "other" category and enter the country name in the "school/institution" field)
• Ranking
• The contest itself

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?