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.

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?