This is my in-contest submission for 2048F - Kevin and Math Class: 297343653. It got "runtime error on pretest 3", which I initially thought was some stupid bug. After the contest was over, I was surprised to see "exit code: -1073741571 (STATUS_STACK_OVERFLOW)". Stack overflow happens when the recursion goes too deep, but the stack limits on Codeforces are pretty generous, and recursion 2e5 calls deep is generally not an issue (imagine how annoying all DFS problems would be otherwise).

At first I thought that this must still be a bug that led to infinite recursion. But I verified locally that this is not the case, and I added an assertion to check that no more than 2e5 calls to solve(ll, ll) are performed in any one test case:

ll solve (ll l, ll r) {
  cnt++;
  assert(cnt < maxn);
// .. rest of the function ..

I also moved the references to tree and arr to global variables for good measure. Still a stack overflow: 297352244.

For what it's worth, both versions get accepted under C++20: 297353626, 297353915.

I'm just in a funny mood. Don't take this post too seriously.

These are all of the problems I've solved using unordered_map. This should be a complete list. For context, I've solved maybe around 4000 problems in total?

• 1120C - Compress String
• Logistics from Estonian Open 2016

I think neither solution is intended. The moral of the story: this class (and unordered_set) are very rarely if ever necessary in competitive programming. Yes, in theory they can do in $$$O(1)$$$ what map does in $$$O(\log n)$$$. In practice, they have a pretty large constant and are maybe only marginally faster than map. And that's not to mention all the times you can get hacked on it.

Meta Hacker Cup is upon us again. Along with it comes the unique format where we have to run our code on large test cases ourselves. Unfortunately, past experience shows that not everyone knows how to do this reliably. Usually, after the first round, many people lose points as a result of an unreliable workflow. This time, let's try to prevent that from happening. Sorry for the somewhat self-important title, but I really do wish that everyone understood this and that no one will fail the contest because of this.

Don't EVER copy-paste huge files

A lot of people's workflow to run a solution is the following:

• Click some green button in the IDE
• A box comes up, copy-paste the input into that box
• The output shows up somewhere

This may work well for running your solution on small sample test cases. It is terrible for running your solution on the huge test cases in Meta Hacker Cup. In last year's Round 1, the full test case for problem C was 37.5 megabytes in size and 6 million lines long. A 20 year old computer is very much capable of handling a file that large, but most graphical tools are not built with such files in mind.

I did an experiment. I opened my code for that problem in VS Code, compiled it and ran the program in VS Code's terminal. Then, I copy-pasted that 6 million line input file into that terminal. VS Code froze and I had to kill it. I'm fairly certain that this will happen on pretty much every consumer laptop. If you do this and your computer crashes, it's not because your laptop is old and slow, it's because you used a tool for something it wasn't designed for. Even if it doesn't crash, the clipboard itself has an upper limit on some systems. You shouldn't even need to open these files. Many text editors aren't designed for large files either and might crash; again, this is not because your computer is slow, it's because the tools aren't designed for large files.

Here's how you should be working with these files.

Option 1. Use pipes to read the input from a file and write the output to a file. For example, ./program < input.txt > output.txt reads the input from input.txt and writes it to output.txt. Read my blog on command line to learn more.

Option 2. Read the input from files directly. In your program, you can write

#include <fstream>

// ...

int main () {
  ifstream fin ("input.txt");
  ofstream fout ("output.txt");
}

Now, you can read from fin (e.g. fin >> n >> m) and write to fout (e.g. fout << "Case #" << i << ": " << ans << '\n').

Option 3. If you like Option 2, but cin and cout are burnt deeply into your muscle memory, you can do

#include <cstdio>

// ...

int main () {
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
}

Now cin reads from input.txt and cout writes to output.txt.

Set a higher stack size

I've written a simple C++ program. It generates a random tree by selecting the parent of vertex $$$u$$$ to be in $$$[u - 6, u - 1]$$$. Then, it prints the depth of the last vertex. Here is the program.

#include <iostream>
#include <vector>

using namespace std;

const int N = 1e6;

vector<int> ch [N];
int depth [N];

void dfs (int u, int d) {
  depth[u] = d;
  for (int nxt : ch[u])
    dfs(nxt, 1 + d);
}

int main () {
  for (int i = 1; i < N; i++) {
    int p = i - 1 - rand() % 5;
    if (p < 0)
      p = 0;

    ch[p].push_back(i);
  }

  dfs(0, 0);
  cout << depth[N - 1] << '\n';
} 

Try running this on your computer; it doesn't take any input. With high probability, you'll see this message:

    Segmentation fault (core dumped)

What is going on? Have I perhaps made some implementation mistake? No: the reason this code segfaults is that the recursion goes too deep. A slightly simplified explanation is that when you are calling a recursive function, the compiled program needs to remember all recursive calls that led to the current call, and it runs out of memory to write this information into. This issue commonly comes up if there is, for example, a graph problem where you need to write DFS.

Option 1. (Linux and probably Mac OS, only if running command line) Type ulimit -s unlimited into the terminal before running your solution in the same terminal.

Option 2. (All platforms) Follow the instructions here.

Compile with -O2

-O2 is a flag given to the compiler that enables certain optimizations. You might not be aware of it, but every submission you submit to Codeforces or any other online judge is compiled with that flag. If the input files are large, you probably want to compile with this as well, otherwise your solution will run rather slowly.

If you compile from the command line, you can just do g++ -O2 solution.cpp -o solution. If you compile using some button in your IDE, it depends on your IDE, but you should be able to add this flag from some menu. Here's how to do it on some common tools. Please note that there are all kinds of setups and if you are doing something different, you probably need to do these things differently as well. If you use some tools, you should in general be well-versed in how to use and configure these tools.

{
	"shell_cmd": "g++ \"$$${file}\" -O2 -o \"$$${file_path}/${file_base_name}\"",
	"file_regex": "^(..[^:]*):([0-9]+):?([0-9]+)?:? (.*)$",
	"working_dir": "${file_path}",
	"selector": "source.c++",

	"variants":
	[
		{
			"name": "Run",
			"shell_cmd": "g++ \"$$${file}\" -O2 -o \"$$${file_path}/$$${file_base_name}\" && \"$$${file_path}/${file_base_name}\""
		}
	]
}

If you disregard any of the rules above and lose points as a result, it is your own fault! It's not the fault of Hacker Cup organizers and it's not because you have an old and slow computer!

A few months ago, I was pretty disheartened. I wrote a blog that I put thought and effort into, and it got only +163 votes and basically no discussion. Meanwhile, a dumb parody I had published just 5 days earlier got +959 votes. Ok, but let's say that this is a bad example, maybe my explanation was bad or uninteresting or people just don't care about residual graphs that much. That's fair.

But I suspect this is a bigger trend. I don't know if my memory deceives me here, but I feel like some years ago there were more high-quality, educational blogs with active discussion. WeakestTopology posted a math blog recently and there are no comments, the blog might just slide out of Recent Actions pretty soon. This seems to happen a lot with such blogs, especially on "advanced" topics.

What I see a lot instead is poor quality content. Lots of blogs like "please debug my code" and "how can I improve" just overwhelm all other content. A lot of comments have extremely bad quality. They are poorly formatted (please tell me — how is it possible that an adult who goes to university doesn't know that there is no space before a period?), often incoherent and disorganized, start with "bro really thought", show a complete lack of reading comprehension or are just plain wrong. It's funny and sad at the same time how often I see greys teaching cyans how to become purple. It seems that too many people have given up on even simply downvoting, let alone debunking low quality content.

Especially blogs about cheaters. Fighting cheating is a noble cause, but can you please at least format your blog well? Use paragraphs, organize your writing, link to submissions. Preferably don't bother with screenshots or links to someone bragging about their rank 2632 on LinkedIn. And familiarize yourself with the system.

Years ago, I used to look at the Codechef discussion board and laugh at what a mess it was. I was happy that Codeforces was much better. Today, I feel like Codeforces blogs are exactly like the Codechef board I used to laugh at.

Here's a poll. If your account is at least 5 years old, please vote.

• Yes, you are right, things have gone downhill
• No, you're gotten old/crazy, it was always bad
• I joined less than 5 years ago

In Polygon, if you go to a contest, this link is almost unusable:

Specifically, I mean the "English (from working copies)". If you have a typical ICPC-style contest with 12 or so problems, it will almost always load for a really long time until I am eventually served with a CloudFlare "timeout" screen. (The one from packages works fine, but sometimes you want to see how the whole contest looks without committing your changes or packaging.)

My suggestion is, if there is truly that much work to do for the server, then run this PDF generation in some sort of background thread and show the user a progress bar.

Cheating has been discussed a lot lately. I'm writing a blog post about it with actual data (mainly, I want to know if there is an actual increase). However, in the many discussions that have ensued both here and on Discord servers, I noticed several recurring misconceptions. I wrote a section to debunk them and it grew kind of long, long enough to be a post in itself. So while my scripts are running, we can treat this as a kind of teaser.

Things you should know before you write a comment about cheating

Vocabulary:

• To plagiarize means to use someone else's work while passing it off as yours. It refers to the act itself, not to its detection or punishment. "jrandomcoder plagiarized all of his solutions in round 987" is a meaningful statement. "jrandomcoder cheated in round 987 but he still hasn't gotten plagiarized, I request MikeMirzayanov to look into this" is not.
• Plague is a disease. In a metaphorical sense it can mean any disease and in a doubly-metaphorical sense it could refer to cheating. However, it is not the same word as "plagiarism" and usually can't be used in its place. "jrandomcoder cheated in round 987 but he still hasn't gotten plagued" is a doubly meaningless statement. If this is a suggested punishment then I'm wrong.

Procedural:

• Codeforces has a plagiarism detector.
• The plagiarism detector is run after every round. However, this does not happen live or immediately. Presumably it takes a while and requires considerable human input (for example, if there are close calls).
• The plagiarism detector will be eventually run, likely within a few days after the contest.
• Ratings are updated soon after the round and likely before plagiarism detection happens. This is because users are impatient. Usually, if ratings are not updated 6 hours after the contest, there is already a sea of "is it rated" and requests for MikeMirzayanov to look into it.
• Ratings will eventually be updated to take disqualified people into account. This does not necessarily happen right after the plagiarism check. When it happens, you see a notification of the form "Ratings are temporarily rolled back. They will be returned soon."
• People have been banned for cheating.

Behavioral:

• When you report cheaters, don't tag random testers you found in the contest announcements. Most of them do a virtual contest, leave some feedback and that's it. They are not the organizers or administrators of the contest. They do not have any powers to punish cheaters. (I also doubt that tagging authors or maybe even coordinators is useful, but since I have been neither, I can't really comment on this).
• Definitely don't tag random "famous" or active members of the community who had nothing to do with organizing the contest. We can't do anything.
• Absolutely definitely don't write your cheater reports as replies to unrelated people's unrelated comments. What the hell?

If you are collecting data:

• If a user is caught cheating, they will usually be marked as "out of competition" and the verdict of all their submissions is set to Skipped.
• However, it appears that they are not always marked "out of competition". I don't really know why or what's the difference.
• Having some skipped submissions (and being out of competition) does not necessarily mean someone is a cheater. This also happens if you are e.g. Div 1 in a Div. 2 contest and you make a submission, pass the pretests and then make another submission to the same problem (for example, if you were only a few milliseconds below the time limit). The earlier submission will also be Skipped after system tests.
• Even having all skipped submissions (and being out of competition) does not necessarily mean someone is a cheater. See discussion here. We can ignore this here when gathering statistics because such cases are rare. But this has to be taken into account when discussing individuals.
• If you call https://codeforces.net/api/contest.status?contestId=2000&handle=jrandomcoder to check if all of someone's submissions in the contest are Skipped, you need to filter out all submissions made in practice mode and similar. They will not be skipped even if the user got caught cheating.
• When someone is caught cheating but before the ratings have been updated, the contest will appear on their profile as if they solved 0 problems, but with a rating change, possibly even a positive one.
• When someone is caught cheating and after the ratings have been updated, the contest appears on their profile as if they participated in it but it wasn't rated for them. You will see it if you choose "Only unrated" or "All" in the drop-down menu in the top-right corner in the Contests tab.
• If you want to compare the frequency of cheating (or many things, in fact), it is not enough to compare one recent contest to one older contest (and similar). Because everything varies unpredictably all the time, you will be comparing random noise to random noise. Some problems may be more suitable for detecting cheaters. The leakers may have had a good or a bad run. For all we know, even the time of day and the day of the week might affect cheating.

Keep in mind though, as I've said before, on a platform with a history as long as Codeforces has, you can't really assume "condition X happens (if and) only if a user got caught cheating". You also can't assume that various unusual situations have always been handled the same way, or even that they have been handled the same way in recent cases, just because you checked a number of recent ones and noticed a pattern. So everything here should be treated as a heuristic only.

If you say "wait, so Mike finally listened and started to ban cheaters?"

When you go visit some profiles, you might very well be greeted with this message.

This is message is a very recent addition. But I'm not sure about "finally". I don't think it's the case that Mike "finally" started banning cheaters this week or something. Because I don't think the bans are that recent. I can't prove it but I have some evidence.

Workflow:

• Pick contest from a few months to a year or so old.
• Go to the Status tab and filter for Skipped verdict.
• Click on the usernames randomly until you find someone who has been disabled.
• Go to their Submissions tab. Note the time of the last submission and the last Skipped submission.

I think we can assume that for many people, the time of the last submission is close to the time of their banning. With the delays between contests, plagiarism checks and revised rating updates, I think we can also assume that if someone is banned for cheating, it doesn't immediately happen after the contest. I've repeated this procedure for the following users:

• abhishek_1624 (last submission: 16.03.2024, last Skipped submission: 01.03.2024)
• bansala271 (last submission: 22.04.2024, last Skipped submission: 06.04.2024)
• Var57 (last submission = last Skipped submission: 29.04.2024)
• BhuvaneshwariM (last submission: 03.06.2024, last Skipped submission: 25.05.2024)
• binary_search75 (last submission = last Skipped submission: 30.06.2024)
• AlicenBob (last submission: 18.01.2024, last Skipped submission: 30.11.2023)
• manishreddy03 (last submission = last Skipped submission: 03.12.2023)

Not cherry-picking data here. In almost all of these cases, the user got caught cheating and stopped submitting some 2 weeks or so later. It doesn't prove anything but in my opinion it is strong evidence that these users did not get banned yesterday, they got banned months ago after getting caught cheating multiple times. (To be sure, we need to look at more data and compare to people who didn't get banned and so on. But it's a good starting point for a hypothesis.)

I think the reason why some people still believe that cheaters are never banned is that Codeforces, for the longest time, did not really indicate that an user is banned. Let us take rotavirus, perhaps the most famously banned user on Codeforces. For the longest time, you could tell he was banned only by the fact that the "Send message" link was missing. Compared to his new account, the links in the red rectangle were missing.

Obviously, not many people are aware of this small detail, so many people perhaps didn't realize how many people are banned (for cheating or trolling). Now it's quite easy to see if you follow my procedure above.

What this blog is not

[Added an hour after publishing based on some early discussion.]

This blog is not an attempt to say that everything is fine and stop complaining. There's lots of suggestions going around, and I think some of them are good, but I'll let other people defend them. I wrote this blog because a lot of people appear to be misinformed, especially about the bullet points in the "Procedural" section. And you can't seriously discuss any situation on false premises.

This blog is also not an excuse to write the final closing remark. It's something I realized after I typed most of this up.

One final note...

As I'm writing my actual blog, it has become clear to me just how much effort does in fact go towards combating cheaters. Things are not perfect and you can always do better, but people are working on this and people do care. And then I see comments and messages where people casually write "bro the admins don't care they just want to inflate participant counts" [the word 'bro' is not my addition]. I've tried pushing back against this once, ages ago, and I got some "bro you think this proves anything" type message.

Maybe Mike doesn't want to say this but I do: this is so entitled, inconsiderate and rude. I've been in a position where I put in a lot of work into something. And then people who don't even look into how much work this is come and tell me that this is trivial or I'm stupid or I don't even care. Or maybe they don't say it about me, but do say it about people who are working on things similar to what I'm working on. Mike doesn't deserve this kind of feedback.

I once read a paper that claimed and used the fact that the Hungarian algorithm can be implemented in such a way that it runs in $$$O(m n \log n)$$$ time. Using the soft-O notation which ignores log factors, the complexity can be written as $$$\tilde{O} (m n)$$$. If the graph is dense, i.e. $$$m = \Theta(n^2)$$$, the log factor can be removed There are many tutorials on how to get $$$O(n^3)$$$, but I couldn't find any references that directly show how to do $$$\tilde{O}(mn)$$$ from end to end (but I found just enough to conclude that it is probably possible). So I decided to write one up myself and well, this is as good a place as any.

In my last blog, I showed how thinking in terms of linear programming and duality can be useful when working with maximum flows and minimum cuts. The usefulness of this is best demonstrated with examples, and this is a good example. In fact, this is pretty much the primal-dual algorithm: it was one of the prototypes that inspired the entire theory. So, this should in fact be an excellent example to gain more intuition of the concept.

As I said, this algorithm makes a nice case study of linear programming and duality. It also brings together many other ideas, so this is a learning opportunity for many things.

Problem statement

You are given a bipartite graph with $$$n$$$ vertices and $$$m$$$ edges. Each edge has a cost $$$c_e$$$. You want to find the minimum cost perfect matching: each vertex on the left must be matched to exactly one vertex in the right and vice versa. The sum of the costs of the edges that are in the matching must be minimized. We assume that at least one perfect matching always exists.

I have previously written about flows in these blogs: 1, 2, 3.

Minimum cuts are a very fascinating topic for me. There are a lot of maximum flow problems where there's a fairly simple chain of reductions leading to "you should use flow", but there are also a lot of flow problems where flow comes apparently out of nowhere. Particularly fascinating are those where it's more convenient to think in terms of minimum cut: they work, because minimum cut allows you to model partitioning a set in two, with some additional implication-like constraints. Here are a couple of problems with that nature:

• ARC085E - MUL (this reduction is almost standard these days)
• ARC142E - Pairing Wizards
• 104925D - Filesystem

There are also flow problems on graphs with special shapes where thinking in terms of cuts makes the flow easy to efficiently calculate.

• 724E - Goods transportation
• 1919F2 - Wine Factory (Hard Version)

Anyway, let's move on to the actual topic of the blog. I recently had a couple discussions on various Discord servers about some problems on minimum cuts. The problems were:

1. Given a flow network where all minimum cuts have a nonempty intersection, prove that there exists an edge that is in every minimum cut.
2. Given a flow network where each edge has a label (independent of capacity), calculate the lexicographically smallest minimum cut, in time $$$O(n^2 m)$$$.

Both problems involve statements like "among all minimum cuts". I thought the problems were very interesting, and shared a common thread, so I decided to write them up in a blog. They also lead neatly into some discussion of more general and abstract theory.

Today I did absolutely nothing.

Hi all.

Osijek camp will be returning again in the summer of 2024. We are looking for problemsetters.

To apply, contact us at ocpc (at) mathos (dot) hr or contact me (-is-this-fft-) or adamant directly. Specific compensation might depend on how successful we are with sponsors and participation fees. As a reference point, last time, we offered 2000€ per contest, plus an additional bonus for authors who conducted analysis sessions onsite for their own contests. Note that the compensation might be subject to some taxation.

You don't need to have enough ideas for a full problemset yet, but you should have a somewhat good idea of what your contest is going to be, i.e. you should have at least 6-7 problem ideas already. The most important criterion for us is whether your contest fits the camp in terms of style and difficulty. The camp is aimed at the highest level of competition, thus the difficulty should be comparable or harder than typical ICPC regional contests. However, it is good if the difficulty distribution between problems is spread out: do not hesitate to add a few very easy or super-hard problems.

It is also possible to suggest individual problems, but we'll likely consider those with a lower priority.

Also, we welcome proposals of unconventional or unusual problems and contests (such as the Run Twice contest in Universal Cup). Camps are a good opportunity to showcase problems that can't be included in an "official" contest for one reason or another. Of course, not every contest can be like this as that would defeat the purpose of a training camp. However, having one or two such contests has proven popular with participants.

Can I propose a contest if I am also a camp participant?

Yes, and in fact, we encourage you to. If you are a camp participant and prepare a contest, your team will not participate on that day, but will otherwise take part in the camp normally. We will also charge no admission fee from your team if you author a contest.

What if I have some interesting ideas, but no time to prepare them?

It's best if you can find a co-author for your contest, who may help you with preparation. You may also reach to reach out to us, we can discuss some options. Please note that since a significant part of the work involved in authoring a contest is preparing the tests, the compensation might be reduced for such proposals.

Can I re-use problems or contests that appeared somewhere else before?

Generally, we prefer problems that are original, or have very little public exposure. In principle, we can still consider your contest if it has some problems from low profile local or private competitions that already happened, but we would need to minimize the possibility that our participants were exposed to them. We might also reduce the compensation for the contest, if you already was compensated for it before.

Can I re-use the problems after I used them in the camp?

We recognize that it is natural for an author to desire for greater exposure for their problems, and we believe that it is a nice thing to give back to the community by making the contests more accessible. As such, we do not want to restrict you from re-using or publishing your problems after the camp has concluded.

However, based on the feedback from previous camps, we will have a "silence period" after the camp, during which camp materials won't be released to the public. Thus, we ask you to refrain from publishing the problems at least until a few months after the camp. We will set a specific date later.

Hello all! I'm pleased to announce the 19th stage of the 2nd Universal Cup. It will be held from January 20 to January 21. You can choose between one of seven possible time windows.

Problems were authored by me (-is-this-fft-) and SLLN. I would also like to thank Andres_Alumets, marko312, sandra.schumann426 and nor for valuable discussion, as well as all of the Universal Cup staff for hosting the contest.

This contest was originally used in the Osijek Competitive Programming Camp Fall 2023. If you participated, please refrain from participating in this stage of the Universal Cup.

About Universal Cup

Universal Cup is a non-profit organization dedicated to providing trainings for competitive programming teams. Up to now, there are more than 700 teams from all over the world registering for Universal Cup.

• A more detailed introduction: https://codeforces.net/blog/entry/118679
• Register a new team: https://ucup.ac/register (the registration request will be processed before each stage)
• Results of past stages: https://ucup.ac/results
• Terms: https://ucup.ac/terms
• Ratings: https://ucup.ac/rating

If you liked this contest and want more like this, come to the next Osijek camp! Registration is now open. If you hated this contest and never want to see anything like this ever again, still come to Osijek and we'll try to make contests that are less like this one.

Someone posted a modified variant of ABC 180 F here before and asked for help solving it. The task went as follows: given $$$n$$$ and $$$\ell$$$, count the number of labeled graphs on $$$n$$$ vertices such that no vertex has a degree exceeding 3, there is no cycle in any connected component (i.e. the graph is a forest) and the largest connected component has exactly $$$\ell$$$ vertices.

I wrote a rather long comment explaining how to solve it. I hit "post" and...

the blog was gone.

To whoever was the author: please don't do this. It's very frustrating to put effort into writing an explanation only to discover that it had been completely in vain. Even if you already got an answer from elsewhere, other users might enjoy reading the solution. It was not the case here, but especially don't delete/hide your blog if there already are answers in the comments. This way you're effectively just erasing other people's work. That sort of thing can really put me and others off from helping people in the comments altogether.

So that my effort wouldn't be completely wasted, I decided to post the contents of my comment here as a separate blog. (In theory, this might have been some ongoing contest or interview problem. But it really is an obvious modification to the AtCoder problem and I sort of believe the author. Besides, all of this is rather standard.)

Let's first learn to count the number of labeled trees with $$$k$$$ vertices where each vertex has degree at most 3. We'll use Prüfer sequences. A Prüfer sequence of a tree with $$$k$$$ vertices is an array consisting of $$$k-2$$$ entries. Importantly, each tree corresponds to exactly one sequence and vice versa. Also, every vertex $$$u$$$ appears in the sequence exactly $$$\mathrm{deg}(u) - 1$$$ times.

So we need to count the number of arrays consisting of $$$k - 2$$$ entries such that every vertex appears in the array 0, 1 or 2 times. We will do that with DP: let $$$\mathrm{dp}[i][j]$$$ be the number of sequences where we have already placed the first $$$i$$$ vertices that have length $$$j$$$ now. We'll try to place the $$$i$$$-th vertex now. A sequence of $$$j$$$ elements has $$$j + 1$$$ "slots" where we could insert the instances of the $$$i$$$-th vertex. So,

• $$$\mathrm{dp}[i][j]$$$ contributes once to $$$\mathrm{dp}[i + 1][j]$$$;
• $$$(j + 1)$$$ times to $$$\mathrm{dp}[i + 1][j + 1]$$$;
• $$$\binom{j + 1}{2}$$$ times to $$$\mathrm{dp}[i + 1][j + 2]$$$.

You can calculate this DP in $$$O(n^2)$$$ time and you'll be interested in the value of $$$\mathrm{dp}[k][k - 2]$$$ for every $$$k$$$. Let's call this value $$$f(k)$$$.

Now to the original problem. I'm going to change it slightly and say we instead need to find the answer where the largest connected component can be up to $$$\ell$$$. This doesn't really change anything as you can calculate the answer for "up to $$$\ell$$$" and then from it subtract the answer for "up to $$$\ell - 1$$$".

Let $$$\mathrm{dp}[i]$$$ be the number of forests with $$$i$$$ vertices where the largest connected component has size up to $$$\ell$$$ and every degree is up to 3. Suppose we have such a forest. We are now going to add to it another tree with $$$k$$$ vertices. There are $$$f(k)$$$ ways to choose a tree. But how many ways are there to add this new tree to the forest? Keep in mind that the indices for this new tree can be "interleaved" with the old forest. E.g. vertices 1 and 3 could be in the old forest and vertices 2 and 4 in the new one. To avoid double-counting, we will assume that the vertex with index $$$i + k$$$ belongs to the new tree. Among the other $$$i + k - 1$$$ vertices, we choose $$$i$$$ of them to assign to the old forest and $$$k - 1$$$ to assign to the new. Therefore, $$$\mathrm{dp}[i]$$$ contributes $$$f(k) \binom{k + i - 1}{i}$$$ times to $$$\mathrm{dp}[i + k]$$$.

In total, the complexity will be $$$O(n\ell)$$$.

Clicking on "Continue" or "Start" in the problem list results in a white screen (the server returns empty content).

This came at a really bad time...

Hi everyone!

Sponsored by

After a successful camp last February (announcement, wrap-up), we are happy to announce that Osijek camp will be returning on 16.-24. September 2023 — just in time to prepare for the World Finals in November as well as several regional contests throughout the fall. The camp is hosted by the Department of Mathematics at J. J. Strossmayer University of Osijek and is brought to you by the organizing team of adamant, -is-this-fft- and ajovanov.

The camp is inspired by various competitive programming camps that we attended during our active years in ICPC, and is aimed to help college students prepare for ICPC regional contests and finals. The camp will consist of 7 ICPC-style contests and 2 days off.

Details

Participation fee for onsite participants is 150€ per person. It does not include regular meals, travel or accommodation. Some further details about location, travel and food options can be found on the website.

If you want to participate, but are unable to come onsite, we offer a reduced fee of 100€ per person for online participation. It is also possible to reduce fees individually if you are unable to attend some of the contests. This will be handled on a case-by-case basis.

We support and empathize with those affected by the ongoing war in Ukraine, therefore we offer a 100€ discount for affected individuals and teams affiliated with Ukrainian institutions. In other words, the fees would be 50€ and 0€ per person for onsite and online participation correspondingly.

The expected starting time for the contests is 10am CEST. For online participants, it is still a preferred starting time, but we will make accommodations for other starting times.

Most of our contests are fresh and developed for this camp. A small number of contests may be based on previous contests that have not been released to the general public. If you have seen some problems of a contest before, you can't participate on that day (and your participation fee will be reduced accordingly). We will privately contact participants who might be affected. Based on feedback, we will have a silence period until the end of November 2023, during which camp materials will not be released to the public. Therefore, we ask participants to not discuss the problems in public until that date.

Participants

If you are interested in participating, please fill the form here.

We ask you to register before September 8 if you want to participate online and before September 2 if you want to participate onsite.

Also, if your university or organization has a lively ICPC community that may be interested in attending the camp, and you have some contacts of people in charge (e.g. coaches) we would highly appreciate if you could fill the form here, so that we can send an invitation. Thanks!

Problemsetters

We'd like to thank and praise the authors of the contests in the camp, including:

• jeroenodb — Codeforces International Grandmaster, Computational geometry enjoyer. NWERC 2021 and 2022 bronze medalist.
• fwitt — POI silver medalist.
• Adam_GS — BOI 2023 winner, EJOI 2021 gold medalist, Codeforces International Grandmaster, problemsetter for OCPC 2023 winter.
• Asymmetry — IOI silver medalist, CEOI and BOI gold and two times POI gold medalist. CERC 2022 gold medalist.
• ppavic — triple IOI gold medalist.
• dorijanlendvaj — double IOI gold medalist, Codeforces Legendary Grandmaster.
• jtnydv25 — author of over 50 problems.
• Claris — ICPC 2017 and 2018 world finalist.
• -is-this-fft- — ICPC 2019 world finalist, Google Hash Code 2020 finalist.

...and others. We would also like to thank Um_nik and nor for their help with reviewing problem proposals.

You can find more details about contest rules and technical setup on the website.

Sponsors

Last but not least, we would like to say special thanks to our sponsors, who make the camp possible. If you are interested in sponsoring next editions of the camp or have any questions, please feel free to reach out at ocpc (at) mathos (dot) hr.

Finally, we would also like to thank Codeforces for guidance and promoting this announcement to the main page, eolymp for providing us an online judge for the contests and the Department of Mathematics at J. J. Strossmayer University of Osijek for all their organizational support and providing us a physical location to conduct the camp.

Hi everyone!

After a successful camp in February, we are excited to announce that Osijek camp will be returning this September. Precise dates and registration details will be announced later, but for now, we are looking for contests and problemsetters.

To apply, contact us at ocpc (at) mathos (dot) hr or contact me (-is-this-fft-) or adamant directly. Specific compensation might depend on how successful we are with sponsors and participation fees. As a reference point, last time, we offered 2000€ per contest. Note that the compensation is subject to Croatian income tax (around 25%).

You don't need to have enough ideas for a full problemset yet, but you should have a somewhat good idea of what your contest is going to be, i.e. you should have at least 6-7 problem ideas already. The most important criterion for us is whether your contest fits the camp in terms of style and difficulty. The camp is aimed at the highest level of competition, thus the difficulty should be comparable or harder than typical ICPC regional contests. However, it is good if the difficulty distribution between problems is spread out: do not hesitate to add a few very easy or super-hard problems.

Any specific deadlines and things you would want me to do?

We would expect the problem set to be finalized in terms of problem ideas a month before that, and be mostly ready (prepared on Polygon) around a week before the camp. We will also expect that you present a tutorial after the contest, or make a PDF doc or presentation with some written details, so that we can explain it to participants. We will likely accept contest proposals on first come, first served basis, so it's better to confirm your commitment as soon as you're sure that you want to set a contest.

Can I propose a contest if I am also a camp participant?

Yes, absolutely! In fact, we encourage you to. If you are a camp participant and prepare a contest, your team will not participate on that day, but will otherwise take part in the camp normally. We will also charge no admission fee from your team if you author a contest.

What if I have some interesting ideas, but no time to prepare them?

We recommend you to find a co-author for your contest, who may help you with preparation. Feel free to reach out to us, we can discuss some options. Please bear in mind that since a significant part of the work involved in authoring a contest is preparing the tests, the compensation might be reduced for such proposals.

Can I re-use problems or contests that appeared somewhere else before?

Generally, we prefer problems that are original, or have very little public exposure. In principle, we can still consider your contest if it has some problems from low profile local or private competitions that already happened, but we would need to minimize the possibility that our participants were exposed to them. We might also reduce the compensation for the contest, if you already was compensated for it before.

Can I re-use the problems after I used them in the camp?

We recognize that it is natural for an author to desire for greater exposure for their problems, and we believe that it is a nice thing to give back to the community by making the contests more accessible. As such, we do not want to restrict you from re-using or publishing your problems after the camp has concluded.

However, based on the feedback from the previous camp, we will have a "silence period" after the camp, during which camp materials won't be released to the public. Thus, we ask you to refrain from publishing the problems at least until the end of November 2023.

If I was a YouTuber, this would be the place where I fill the entire screen with screenshots of people asking me to make this. Anyway, not so long ago I gave a lecture on FFT and now peltorator is giving away free money, so let's bring this meme to completion.

In this blog, I am going to cover the basic theory and (competitive programming related) applications of FFT. There is a long list of generalizations and weird applications and implementation details that make it faster. Maybe at some point I'll write about them. For now, let's stick to the basics.

The problem. Given two arrays $$$a$$$ and $$$b$$$, both of length $$$n$$$. You want to quickly and efficiently calculate another array $$$c$$$ (of length $$$2n - 1$$$), defined by the following formula.

Solve it in $$$O(n \log n)$$$.

First of all, why should you care? Because this kind of expression comes up in combinatorics all the time. Let's say you want to count something. It's not uncommon to see a problem where you can just write down the formula for it and notice that it is exactly in this form.

FFT is what I like to call a very black-boxable algorithm. That is, in roughly 95% of the FFT problems I have solved, the only thing you need to know about FFT is that FFT is the key component in an algorithm that solves the problem above. You just need to know that it exists, have some experience to recognize that and then rip someone else's super-fast library off of judge.yosupo.jp.

But if you are still curious to learn how it works, keep reading...

When solving problems in competitive programming, it is almost never a good idea to use the following inbuilt C++ functions. You will be hacked or fail a pretest or worse, a systest.

Why? Because they use floating-point numbers. They are designed to be used with a floating-point input and a floating-point output. The issue is that on a floating-point number, the result may not be exact. Worse, floating-point numbers may not be able to accurately encode the integer.

To calculate $$$\lfloor \frac{a}{b} \rfloor$$$ for positive integers $$$a$$$ and $$$b$$$:

• Don't use floor((double) a / (double) b) or similar.
• Do use a / b. It will round down.
• Warning: be careful with negative numbers. The answer depends on whether we should round down or towards 0.

To calculate $$$\lceil \frac{a}{b} \rceil$$$ for positive integers $$$a$$$ and $$$b$$$:

• Don't use ceil((double) a / (double) b) or similar.
• Do use (a + b - 1) / b.
• Warning: the same caveat goes for negative numbers as before.

To calculate $$$\lfloor \sqrt{a} \rfloor$$$ for a nonnegative integer $$$a$$$:

• Don't use sqrt(a) or similar.
• Do use binary search to calculate the square root.

// works for at least up to (2**31 — 1)**2
long long int_sqrt (long long x) {
  long long ans = 0;
  for (ll k = 1LL << 30; k != 0; k /= 2) {
    if ((ans + k) * (ans + k) <= x) {
      ans += k;
    }
  }
  return ans;
}

To calculate $$$a^b$$$ for nonnegative integers $$$a$$$ and $$$b$$$:

• Don't use pow(a, b) or similar.
• Do use the naive algorithm. If you really want to do this and $$$a^b$$$ fits in a long long, then it will take no more than 64 steps, unless $$$a = 0$$$ or $$$a = 1$$$, in which case you can just return $$$a$$$.

To calculate $$$\lfloor \log_2 (a) \rfloor$$$ for a positive integer $$$a$$$:

• Don't use log2(a) or similar.
• Do use __lg or an approach based on __builtin_clz or __builtin_clzll. The "clz" stands for "count leading zeroes" and it does exactly what it says — on the binary representation of the number. If you have access to C++20, there is also the bit_width library function.
• Warning: __builtin_clz(0) and __builtin_clzll(0) are undefined behavior. Also all these functions starting with __ are specific to GCC and you're technically not meant to use them, but it's fine in competitive programming.

Exceptions

The only major exception is if floating-point numbers are an inherent part of your solution. Most commonly, this happens in problems where the output is itself a floating-point number (especially geometry problems, sometimes probability). There are also some algorithms where you need to work with floating-point numbers even if the input and output are integer (FFT, possibly some LP).

But even in these cases, it's always a good idea to do as much as possible with integers and move to floats as late as possible.

I got WA with one compiler, accepted with another

Most likely it has to do with 64-bit versus 32-bit. Also the widths of the various floating-point types vary. It's possible that in some circumstances your solution is actually correct. However, rely on this only if you know what you're doing.

Perhaps this will be helpful to some. The reason I'm writing this is that these words are used often, and a lot of people understand them the wrong way. This means that if you read some advice containing these words and misunderstand them, you will walk away with a wrong idea.

• Constructive. Refers to problems where a significant part of the solution is about coming up with a pattern that satisfies some properties, e.g. a grid coloring or a graph. A blatant example is this. "Constructive" does not mean the same as "ad hoc", nor does it mean "a problem where no well-known algorithm is needed", nor "a problem where you have to make observations".
• Doubt. You have a doubt when you are not sure about something. That is, you have a pretty good idea, but something seems strange or a little off. If you have no clue, then it is not a doubt.
• Observation. An observation is a friendlier synonym for words like "theorem", "lemma" and "proposition". It is a (usually relatively short) chain of reasoning leading to a conclusion. "Observing" does not in general mean looking at input/output pairs and noticing patterns.
• Plagiarism, plagiarize. Refers to the act of copying itself, not to its detection. For example, "I solved this problem, my friend plagiarized it from me" is correct, "my friend copied my solution and got plagiarized" is not.
• Plague. A disease. Doesn't have much to do with plagiarism.
• Solution, solve. These kind of have two meanings. Almost every problem in CP has two parts: first, you think, and when you have thought something up, you code. "Solving" primarily refers to the former and only secondarily to the latter. When people tell you to solve more problems, they mostly mean that you have to think more, not implement more. Reading an editorial and then implement the idea they give there is not "solving".
• Subquadratic complexity. Refers to any complexity strictly less than $$$n^2$$$ (formally, any complexity in $$$o(n^2)$$$). This includes complexities in $$$\Theta(1)$$$, $$$\Theta(\log n)$$$, $$$\Theta(n)$$$ etc., not only things like $$$\Theta(n^{1.999})$$$.
• Trivial. Something that does not require any special insight beyond what is already given. It does not necessarily mean "easy" or "simple". For example, it would be valid to say that something is "a trivial FFT problem" if the application of FFT is fairly straightforward. This statement doesn't imply that the problem would be easy for everyone, including beginners who have never even heard of FFT. In a similar fashion, a long calculation is often called trivial if it is all pretty much mechanical.

For no reason in particular I'm curious about this, for both spring and fall (or winter and summer) semesters. There seems to be a lot of regional variation.

Here is a Google Form I made.

Please note that I'm interested in specific answers, i.e. not "in the spring" but rather "from April 31 to May 15".

Introduction

When it comes to "problem-solving techniques", there are roughly 3 levels:

1. Concrete algorithms (Kruskal's algorithm, Li-Chao tree, fast Fourier transform)
2. General patterns (dynamic programming, greedy, square-root decomposition)
3. Meta-strategies ("how do I even go about solving this problem?")

There is some grey area, but in general this classification works well.

Many tutorials have been written about ideas that fall into 1 or 2. But very little has been written about the third category. On the catalog, I think the only blogs that really qualify are this and this. There is also this valuable comment. As to why there is so little written, I think I can identify two reasons.

• Most strong contestants don't really consciously think about these. After solving a problem with FFT, it's hard not to know you used FFT. If you used DP, even if you did it without thinking that it's DP, it's not hard to recognize that you used DP later anyway. But about things in the third category... it's hard to recall how exactly your thought process went. Furthermore, at least I have never really learned (i.e. read about and understood) anything from that category. Rather my thought process has developed from a lot of practice and experience.
• When writing about algorithms, it is easy to know you are right. You just prove it. But now we are veering into a more uncomfortable realm, where it is harder to understand what is correct or what is even useful. It is not as bad as writing about psychology, but still. Even with this blog, as I'm writing this, I think "does it even make sense?".
• It is not clear if writing blogs of this type actually helps anyone. I still maintain that in your ability to solve problems, the most important thing that you have control over is experience and seeking substitutes for that (algorithms to come up with algorithms, reading other people's thought processes) etc don't work. However there are many people who in theory should have a lot of experience but whose results don't reflect that.

It's far too much for me to write and describe exactly how my thought process works, and I'm not at all convinced that this would be useful for anyone. But I think I've identified something that beginners regularly get wrong, so I'll try my best to explain that.

Part 1: [Tutorial] My way of understanding Dinitz's ("Dinic's") algorithm
Part 2: [Tutorial] Minimum cost (maximum) flow
Part 3: [Tutorial] More about minimum cost flows: potentials and Dinitz

Introduction

As mentioned in the introduction of part 2, there is something in out ICPC notebook called "min cost dinic". This cycle (no pun intended) of blogs was initially meant to be just one blog explaining it all, but in time it developed into something much longer. The general idea here doesn't appear to be particularly widely discussed, but it is certainly not novel either; TopCoder, for example, calls it the primal-dual algorithm (why is it called that? That's a story for another time, but it has to do with LP duality.)

Picking up from where we left off, there are still two things to talk about:

• Where does Dinitz come in?
• Something called "potentials".

Even more generally, recall the "universal max-flow algorithm template" from part 1.

Algorithm 1. Given a flow network $$$(G, c, s, t)$$$.

• Initialize $$$f$$$ by setting $$$f(e) \gets 0$$$ for all edges. This is a valid flow.
• While $$$t$$$ is reachable from $$$s$$$ in $$$G_f$$$:
• • Find some flow $$$\Delta f$$$ in $$$G_f$$$.
• • Let $$$f \gets f + \Delta f$$$.
• Return $$$f$$$.

Our aim is to prove the correctness of the following generalization.

Algorithm 2. Given a flow network $$$(G, c, a, s, t)$$$ without negative cycles.

• Initialize $$$f$$$ by setting $$$f(e) \gets 0$$$ for all edges.
• While $$$t$$$ is reachable from $$$s$$$ in $$$G_f$$$:
• • Let $$$S$$$ be the shortest-paths subgraph of $$$G_f$$$.
• • Find some flow $$$\Delta f$$$ in $$$S$$$.
• • Let $$$f \gets f + \Delta f$$$.
• Return $$$f$$$.

A special case of this is if we use "maximum" instead of "some".

Again thanks to adamant and brunovsky for reviewing, as the two blogs used to be just one.

I tried to remove the "constructive algorithms" tag from 1704F - Colouring Game because the way I see it, there is nothing "constructive" about that problem. Within a minute, it reappears.

The first impression one might have is that I got into an "edit war" with someone who adds it back. However, I tried it 3 different times during the day (each time multiple times) and it has reappeared quickly every time. I don't believe that out of the few hundred people who have tag edit access on that problem, out of whom only a fraction care about the tags, out of whom only a fraction think the problem is "constructive", someone would instantly notice that the tag was gone and re-add it every time.

There is the possibility that it is done by a bot, but it seems unlikely that someone would write a bot like that seeing as it serves no purpose and is not that trivial to do.

The most likely interpretation still seems to be that removing the tag is actually broken. My theory is that the server caches that the tag is supposed to be removed but never actually removes it from the database, so when the cache is invalidated or reloaded, the tag reappears.

Some more experiments:

• I can add and remove new tags.
• I asked someone else to add a bogus tag to a problem. I was able to remove that.
• I asked other people to remove the tag. It reappeared (which should prove that I'm not "shadow-banned")
• I added a bogus tag to F and let it sit there for an hour or so (the fact that it remained should prove that no human is re-adding the tags: anyone like that would also remove "schedules"). I was able to remove that.

In my opinion, no problem in that contest is "constructive". D might be under a very generous interpretation.

Part 1: [Tutorial] My way of understanding Dinitz's ("Dinic's") algorithm
Part 2: [Tutorial] Minimum cost (maximum) flow
Part 3: [Tutorial] More about minimum cost flows: potentials and Dinitz

Introduction

There is a section in our ICPC notebook from 2019 called "min cost dinic". This blog started as an attempt to dissect what was written in there and understand why it works. In time, I needed to refer to many general ideas about flow, so it developed into a more general treatment of (min-cost) flow problems and spawned an entire separate blog about maximum flow and Dinitz. Even after splitting the blog, this blog was still too long, so I split it yet again. This blog will deal with the basic ideas of minimum cost flow; there will be a part 3, where I will generalize to a Dinitz-like algorithm and also talk a bit about something called potentials.

This blog is somewhat more technical and formal than I would ideally write, but there is a reason: there are things that one might overlook if they were not careful, and it is easy to gloss over something important. I remember well some misconceptions I used to have about flow back in the day. These algorithms are "fragile" — I don't mean that in a negative way, but they exist because a number of interesting facts come together, and being too informal may mean that we don't fully appreciate just how incredible it is.

Definition 1. Given a flow network $$$(G, c, s, t)$$$ and a cost function $$$a \colon\, E \to \mathbb{R}$$$ (in the following I will abbreviate this to "given a flow network $$$(G, c, a, s, t)$$$") the cost of a flow $$$f$$$ in $$$G$$$ is

The minimum cost maximum flow problem is to find a flow $$$f$$$ in $$$G$$$ such that the value of the flow is maximized, and among all possible solutions with maximum value, to find the one with minimum cost.

The aim of this blog is to prove the correctness of the "classical" minimum cost maximum flow algorithm (I have no idea if it has a name...):

Algorithm 2. Given a flow network $$$(G, c, a, s, t)$$$ without negative cycles.

• Initialize $$$f$$$ by setting $$$f(e) \gets 0$$$ for all edges.
• While $$$t$$$ is reachable from $$$s$$$ in $$$G_f$$$:
• • Let $$$P$$$ be a shortest path from $$$s$$$ to $$$t$$$.
• • Let $$$\gamma$$$ be the minimum capacity among the edges of $$$P$$$ in $$$G_f$$$.
• • Define $$$\Delta f$$$ by putting $$$\gamma > 0$$$ flow on every edge in $$$P$$$.
• • Let $$$f \gets f + \Delta f$$$.
• Return $$$f$$$.

Here and in the following, "shortest path" always means shortest with respect to edge costs (and not number of edges like in Edmonds-Karp).

Thanks to adamant and brunovsky for reviewing this blog.

Part 1: [Tutorial] My way of understanding Dinitz's ("Dinic's") algorithm
Part 2: [Tutorial] Minimum cost (maximum) flow
Part 3: [Tutorial] More about minimum cost flows: potentials and Dinitz

Introduction

My philosophy on writing blogs is that I only write blogs when I feel that I have something new and interesting to contribute. This is usually not the algorithm itself, of course, but it can be that I recently found or heard of a new perspective or I figured out a way to explain something in a new way. This is in contrast to my dear colleagues at GeeksForGeeks who write the most low-effort (and often wrong) tutorial on everything and then sit at the top of Google results using their somehow world-class SEO.

This is one such case. I have an idea how to explain Dinitz's algorithm in a way I haven't heard of before (but it is not very hard to come up with, so this is not a claim to originality). In addition, this blog is a multi-parter, and in my next blog it is very convenient to start from the notions I establish here today.

The approach I am going to take is explaining the idea from a perspective of "the space of all possible changes". At any given step of the algorithm, we have a flow. We can choose a way to change the flow from this "space" and apply the change. If we detect there is no possible increasing change to the flow, the algorithm is terminated. The space of changes is such that any valid flow can be reached from any valid flow by applying just one change. This idea is almost geometrical and can in fact be thought of as wandering around within a convex shape in high-dimensional space.

I believe that this viewpoint gives a broader and more natural understanding of the algorithm and the "big picture" compared to more narrow explanations that look like "well we have flow and sometimes we add reverse edges and mumble mumble blocking flow". In addition this grounding allows us to see Dinitz as a direct improvement on Edmonds-Karp instead of them being merely vaguely reminiscent of one another.

Why?

Weak pretests discourage guessing.

There are many contestants who only have a faint idea of why their solution works at all. The problem style of recent years has contributed to this. If the solution boils down to "check this elegant condition, answer YES or NO based on that", then it is very much possible to solve problems by guessing. Especially with full feedback.

Remember 1375C - Element Extermination? The solution is to check if $$$a_1 < a_n$$$. Tons of people under the contest announcement were excited to explain that this is how to solve the problem. Only a few could explain why it worked.

This is also a situation where it is easy for a high-rated author or coordinator to deceive themselves. If you already know such a solution, then it may seem very easy. The implementation is easy and if there is a clean observation you have to check, making that observation seems easy in hindsight. And the large number of solves in the contest "confirms" that it is easy. But in fact, the problem is only easy to guess, not easy to solve.

In the good old days it was not seen as a big violation if pretests were weak. It was normal. Right now weak pretests cause an uproar because people are not expecting it. If weak pretests were the norm, it would not be such an issue.

Make weak pretests the norm again. It will improve the quality of standings. Thanks.