I recently submitted a contest proposal for the first time. The proposal section and Mike's blog are pretty clear about the process. You send your proposal, the CF coordinators comment and give you feedback, maybe ask for some changes, and if it looks good, they work with you to get it hosted.

However, there were some things I had absolutely no idea about. Such as how long it usually takes to get a response, how likely it is to actually get a response, how long it would take to host it, would they only listen if I had a high rating, how much work I would have to do, etc.

There's contests written by new authors all the time, which means there's a lot of success cases. However, most of them don't talk about how it went when they proposed it. I only found this exception. On the other hand, there's also failed cases where the contest proposer is ignored and ends up being upset with the coordinators, such as this one.

I think it would be nice to have more information about the contest proposal experience. And it should be unbiased information, which considers everyone's point of view, not only users with a negative experience. I think the best way to accomplish this is to give everyone the chance to tell their story. That's why I created a very simple form where people can tell how their first proposal went. Please share your experience! It would be super useful and encouraging for users who are submitting for the first time.

Consider the following:

• The form is 100% anonymous.
• This form is for anyone who has proposed a contest, even if it wasn't hosted.
• If you've proposed more than one contest, please answer the questions regarding your first one.
• This is a good faith initiative for the CF community, please don't ruin it with fake answers or spam.

Contest Proposal Form

If this blog isn't ignored, I'll update it later with information regarding the results of the form. In such case, I'd represent the information in charts and statistics to make it very clear what one should expect after submitting their first proposal.

The more people fill it, the better the resulting information. If you have a story to tell, please share it! The form is short and doesn't take longer than 2 minutes to answer.

If you think of another question that might be useful, let me know and I'll include it in the form.

I was working on problem 1221G - Graph And Numbers, which required calculating the amount of independent sets on a graph of at most $$$40$$$ nodes. I came up with a heuristic algorithm, which I know is exponential, but I also know it's pretty good in practice, which explains the AC 65276338. First some definitions:

My solution is reduced to the following function:

This approach is correct, because the amount of independent sets for a graph split on several components, it is sufficient to multiply the answers of each component. For a connected graph, there are two possible cases: $$$x$$$ is not included in the set ($$$x$$$ is the node with greatest cardinality) or $$$x$$$ is included the set. For the first case, delete $$$x$$$ and all its edges from the graph and solve recursively. For the second case, all nodes adjacent to $$$x$$$ must not be included in the set, so delete $$$x$$$ and all of its adjacent nodes, and solve recursively.

This is a backtracking solution. It's fast because it always deletes as much edges as possible when the graph is connected, making the graph become either empty or disconnected very fast. Whereas when it's disconnected, it solves each component independently, and then multiplies the results, instead of recursively solving all possibilities.

Even though I know this solution does well in practice, I'm still very curious for its actual time complexity. Here's where I need help, I don't even know how to find the worst-case scenario. Any ideas?

Hey guys, this quick problem popped into my head:

You are given a DAG, where each node has an integer value (which may be negative). You can choose an arbitrary subset of nodes, as long as this constraint holds: if you pick a node, you also have to pick all nodes reachable from that node. Obtain the maximum possible value sum.

It feels like an NP problem to me, but I couldn't prove it. Anyone heard about it? Any ideas on how to solve it?

Last round involved a randomized solution for problem E, and some pretests were aimed against std's rand() function. This caused a big dispute among contestants. It was questioned whether doing this type of tests was fair or necessary, since passing them depended merely on specific language knowledge, not actual problem-solving skills. Contest coordinators counter-argued that participants would've gotten hacked if it hadn't been for these pretests. They also stated that it's one's responsibility to know their favorite language when using it on a round.

The fact is, this controversy was really caused by a technical property within C++ (and codeforces, partly), which many people had no clue existed. This is just an example of the fact that languages and their functioning in CF will sometimes have non-intuitive and unexpected properties, which may screw our performance in a contest. In other words, we are constantly exposed to bumping into another of these hidden behaviors, making the mentioned round hardly the last time something like this can happen.

That's why I thought: We should have a list of the main language-specific issues that could annoy us during contests. Just a brief enumeration of not-so-fun facts about languages, such that, if not known, could break our solutions or get us hacked. Making a brief list available for the community, and exposing it to participants before a round could prevent a lot of trouble. If a problem could make you bump into one of these weird language issues, contest coordinators could safely assume we know about them and not get into a moral debate whether it's fair to include tests against it. Also, contestants would be safe from losing rating to specific language knowledge. In other words, we could prevent issues like the last round's with the least amount of effort.

This blog is an attempt to build up this list once and for all! It should include as much facts as possible, so I'm calling out for your help. If you've had trouble on a problem because of issues in the language, I invite you to help out contributing and write it as a comment. I'll update it in the list as soon as possible. You'd be helping out and preventing other people from going through the same annoying experience! I've included the very few facts I know about for now. It's not much, which is why anything you can share is useful!

Unhackable List

C++

Java

Python

In today's contest, problems C and D were very similar because they required iterating an array based on ranges of equal values. After the contest ended, I opened other participants' solutions and saw long, complicated codes, when both problems were actually simple. Therefore I decided to share a very easy technique I like to use in these situations. I wasn't sure about writing this blog, since I believed this method was too obvious. But after seeing that many people struggled today, I decided it may turn out helpful.

Take the classic problem of string compression: Given a string str, return a vector V of pairs (letter, frequency) that represents the string. For example "aaacbbab" would yield [(a, 3), (c, 1), (b, 2), (a, 1), (b, 1)].

vector<pair<char, int>> compress(const string &str){
    vector<pair<char, int>> ret;
    for(int i = 0, j = 0; i < str.size(); i = j){
        for(; j < str.size() && str[i] == str[j]; j++);
        
        //range operation:
        
        ret.push_back(make_pair(str[i], j - i));
    }
    return ret;
}

The key of this method is that it encapsulates the range calculation, so that you just need to adapt the "range operation" indicated in the function. Note that the size of the actual range is j — i (furthermore, the range is [i, j) ) and the value of the range is str[i]. These two observations sound trivial, but you can really take advantage of them. Here is how this method works for problem C of today:

typedef long long ll;
ll getMaxSum(int n, int k, int *a, const string &s){
    ll sum = 0;
    for(int i = 0, j = 0; i < n; i = j){
        priority_queue<int> pq;
        for(; j < n && s[i] == s[j]; j++) pq.push(a[j]);
        //range operation:
        for(int r = 0; pq.size() && r < k; r++) {sum += pq.top(); pq.pop();}
    }
    return sum;
}

Here is the same technique applied on problem D:

int getX(int n, const vector<vector<char>> &A){
    int ans = 0;
    for(int u = 0; u < n; u++)
        for(int i = 0, j = 0; i < n; i = j){
            for(; j < n && A[u][i] == A[u][j]; j++);
            //range operation:
            ans = __gcd(ans, j - i);
        }
    for(int u = 0; u < n; u++){
        for(int i = 0, j = 0; i < n; i = j){
            for(; j < n && A[i][u] == A[j][u]; j++);
            //range operation:
            ans = __gcd(ans, j - i);
        }
    }
    return ans;
}

Again, the advantage of this technique is that it separates the "range operation" nicely, so you only have to focus on the problem logic, and not in details of the actual range distinctions. I hope you find it useful.

I've been digging into sports programming for about two years now, and recently I have been thinking about dedicating time to contribute to the competitive community in my university (and maybe in CF as well!) by creating and organizing contests. However, I also want to keep on improving my skills and performance on competitions. I am somewhat worried that problem setting and testing will consume too much of my time and not let me grow personally. Or maybe I'm wrong and organizing contests can actually help a coordinator stay sharp in his/her skills? I just wanted to ask problem setters, testers, and users who have been involved in contest coordination in general, about your personal experience and opinion. Do you merely wish to give back to the competitive community? Or do you think it actually helps you improve personally? Or is contest setting and participating simply independent? Any advice you want to share is appreciated!

In recent rounds, I have noticed plenty unsatisfied contestants (specially from div 2), criticizing the problems, the difficulties, and/or the pretests. Some complaints are about problems being too easy, too hard, too "troll", that Codeforces is now "Mathforces", etc. I have been specially surprised by some participants accusing testers for hard problems, when they actually have nothing to do with it. I think most problem setters are already used to this type of behavior. However I still wanted to spend some time on this post and share my opinion about these angry comments.

First, I want to make clear that I am not against giving feedback to the rounds. I actually think it is one of the best ways to improve and grow as a competitive programming community. I also understand that it is easy to react angrily at the setters after a bad performance. I myself have gotten upset after several contests, and felt the need to blame the people who prepared the round. However, I believe most of us participants don't consider some important issues before posting these raging comments. First of all of course, we should appreciate all the work done behind a contest (which is done entirely out of contribution). But I have specially come to notice a principle that is frequently ignored as well: problem diversity.

As a competitive programmer wanting to improve, I've seen that one of the best ways to increase your skills is to solve types of problems which you are not used to solve. Just repeating tasks you already know how to do will help you very little. Now, Codeforces rounds can be suggested by almost any user in the world, so shouldn't we expect that sometimes the problems will be a little different to what we are accustomed to? Another observation I made is that most of the top rated users from the platform usually perform well in a consistent basis. So isn't that evidence that mastering competitive programming involves being able to solve different types of problems? I just think it is a good idea to use the contests we initially don't like as an opportunity to become more talented, and to acquire the ability to solve similar tasks in the future.

Again, this is merely my opinion about contest criticism. I am inviting you to consider this simple concept: problem diversity. Leaving aside angry comments and trying to extend your knowledge has really helped me grow as a competitive programmer, and I am sure that can be the case for anyone else as well.

Has anyone been able to open the problemset?

I have now bumped into several geometry problems that require clockwise 2D point sorting relative to a specific center, here is an example. The key to solving this task is to implement a comparator function, with this header:

bool operator<(const Point &a, const Point &b);

The function should return true iff Point a goes before Point b in counter-clockwise order (with a defined center-point). If we correctly implement this function, we can do countless things, such as sorting points, handling sets and maps of points, applying binary search, etc.

I have researched and found out there is not really a simple, short, easy-to-remember implementation for this function out there. That's why I decided to share mine in this blog.

First of all, you obviously need a Point template. If you aren't familiar with this, read this blog.

I only included dot product and z-coordinate of cross product, since that's the only two functions we will be needing.

struct Point{
    ll x, y;
    Point(){}
    Point(ll x, ll y): x(x), y(y){}
};

ll operator%(const Point &a, const Point &b){//z-coordinate of cross product
    return a.x * b.y - a.y * b.x;
}
ll operator*(const Point &a, const Point &b){//dot product
    return a.x * b.x + a.y * b.y;

These functions are basic in geometry. Now, without loss of generality, suppose our center is the origin (0, 0) (if not, just make points relative to your center). We also need a starting reference, since points could be all around the center. Let's call this point u, and suppose it's value is (0, 1) (again, without loss of generality).

This is what you need:

const Point u(0, 1);
bool A(const Point &p){
    return u % p > 0 || (u % p == 0 && u * p > 0);
}
bool operator<(const Point &a, const Point &b){
    return (A(a) == A(b) && a % b > 0) || (A(a) && !A(b));
}

That's it. Those two one-liners will work correctly for any two points different than the origin.

Hope it was helpful. Happy coding!

I was reading about tree isomorphism and came across this paper. It explains an amazing algorithm developed by Aho, Hopcroft and Ullman which finds out if two rooted trees are isomorphic in linear time. I have searched for this problem on several online judges in order to test my implementation, but have had no success. If anyone has seen a problem that requires this algorithm could he/she be so kind to share the link?

Any help is appreciated :)