There can be an option for the participants to choose whether this contest should be rated or unrated for them as we had in today's atcoder beginner contest.

Just look at any official contest.

Codeforces Technocup (or any other such contests) are rated if its of 2/3 hrs even if they has just 25 participants. Probably technocup finals dont have 25 participants but if you dig in you will find. VK Cup used to rated even if it was team contest. VK Cups were the reasons why Mike looked at math for how to make teams contests rated. What formulas should be used.

Same for Atcoder WTF which had just 8 participants. Same for Topcoder TCO rounds. Finals even have just 8 participants.

Its a norm across all important websites rather than just codechef doing it.

One side advantage of this is there would be 5 star rated lgm finalists rather unrated finalists.

Many of 5-star and 6-star rated people from CodeChef originally earned their stars in long contests and they don't expect to perform well in a shorter 3 hour contest, thus risking their stars. Also many people reached their top rating in a single lucky shot months/years ago and stopped participating in rated contests since then.

Having rated SnackDown rounds forced all these people to actually defend their titles rather than resting on their laurels (if they wanted to make a shot at t-shirts and other prizes). I think that this is good, because this encourages healthy competition.

Off-topic, but you have a good choice in profile pictures!

aren't they permanently banned?

Yes, they can participate in the Parallel rounds tonight. But the ~2100 users caught will be perma-banned before the ratings are updated for this round.

This issue has an easy temporary workaround until it gets fixed permanently. See 2 samples here

Just add explanations of all samples as explanation (with paragraphs starting with "In the first sample", "In the second sample"....) in the last sample.

Can you explain approach for B?

If N=2 print "ab"

If N is divisible by 4, print "abba" N/4 times

Otherwise, let p be the minimum divisor of N greater than 2. Then you need to output any palindrome of length p repeated N/p times.

I like you because you give some feedback on the contest!

p.s. In general it is a bit sad that there is more or less zero discussion after the contest. I am not talking only about this contest, but in general about contests for strong contestants (e.g., yesterday's agc).

There was a parallel rated contest for Div-3, so that anyway can't be made rated. As for the other contests, if we calculate the ratings now, a Div-2 user could fall to Div-3, and then participate in the Dec Long, which causes issues. And even in Dec Long, there are separate Div-2 and Div-1 unrated contests, which will again cause issues if people change divisions because of tonight's contest (not just rating-related issues).

We are trying to move to a system where these issues are minimized, but for now, we'll just have to wait till the Dec Long gets over.

The editorial has a hard proof to why it works, but doesn't explain the intuition behind it so I will try to provide that intuition.

Since $$$c_{i, j} \lt D$$$, increasing $$$\sum |i - j|$$$ to reduce $$$\sum c_{i, j}$$$ never improves the answer. So we want to find permutations $$$p_1, p_2, \ldots p_n$$$ of $$$[1, n]$$$ with the minimum value of $$$\sum\limits_{i = 1}^{n} |p_i - p_{i + 1}|$$$ and among all such paths find the one with the minimum value of $$$\sum\limits_{i = 1}^{n} c_{p_i, p_{i + 1}}$$$.

So what is the minimal value of $$$\sum\limits_{i = 1}^{n} |p_i - p_{i + 1}|$$$? To answer that lets consider a slightly more natural problem. We have $$$n$$$ towns placed in a line, the $$$i$$$-th is at a position $$$i$$$. What is the minimum distance we will have to move to visit all towns and return to the starting town if we can start at any town.

Logically we want to avoid re-visiting towns as much as possible. So starting from a town $$$i$$$ we want to go all the way left to town $$$1$$$, then all the way right to town $$$n$$$ and come back to town $$$i$$$. Which has a cost of $$$|i - 1| + |1 - n| + |n - i|$$$ $$$=$$$ $$$(i - 1) + (n - 1) + (n - i)$$$ $$$=$$$ $$$2 \cdot (n - 1)$$$. Amazingly it doesn't depend on $$$i$$$ at all, so we can start from any town and get an optimal answer. So starting from town $$$1$$$ we could go to $$$n$$$ and come back to $$$1$$$.

Now suppose I extended the problem to say that you can visit the town OR just walk by it, but if you visit town $$$j$$$ after last having visited town $$$i$$$ you pay an additional cost of $$$c_{i, j}$$$. Minimize this cost for any path visiting all towns (and returning to the starting town) with distance $$$2 \cdot (n - 1)$$$.

If we start at town $$$1$$$ we will pass by each town twice, once while going from $$$1$$$ to $$$n$$$ and once while going back from $$$n$$$ to $$$1$$$. So we have to decide which set of towns we visit on the path from $$$1$$$ to $$$n$$$ and which we visit on the path from $$$n$$$ to $$$1$$$. So our answer will be of the form $$$1 \lt a_1 \lt a_2 \lt \ldots \lt n \gt b_1 \gt b_2 \gt \ldots \gt 1$$$ where $$$a$$$ and $$$b$$$ contain all elements from $$$[2, n - 1]$$$ in total and no element occurs in both.

Some minor observations for ease of implementation after this are:

• Since $$$i$$$ -> $$$j$$$ and $$$j$$$ -> $$$i$$$ have equal cost, we can split the cycle into two paths $$$1 \lt a_1 \lt a_2 \lt \ldots \lt n$$$ and $$$1 \lt \ldots \lt b_2 \lt b_1 \lt n$$$ from $$$1$$$ to $$$n$$$.

• Now we can calculate $$$dp[\text{last town in a}][\text{last town in b}] = \text{cost}$$$. The last town placed must have been the last town of one of these paths, so the next town to place is just $$$max(\text{last town in a}, \text{last town in b}) + 1$$$.

So now this can now be implemented in $$$O(n ^ 2)$$$ with a fairly easy dp — Solution

Sorry :|

About D, we discussed if the best option was:

1. Add the constraint "20 distint characters" (this was the original version of the problem).
2. Add the banner "Notice the unusual time limit".
3. Do nothing.

The main reason to exclude 1. is "it hints the solution more than a huge time limit". The main reason to exclude 2. is "a finalist should be able to check the time limit". Hence we went for 3., but we understand the issues related with it.

Regarding "the time limit is tight". I did not prepare the problem but I implemented many $$$O(n2^n)$$$ solutions (all those I could come up with) and all of them needed less than $$$9$$$ seconds (I was writing them unoptimized on purpose). That is why I agreed with the time limit and, to be honest, I don't regret the choice.

Regarding "many people just thought the solution and didn't write it since it looks like a suboptimal solution". In my opinion (but I know that not everyone agrees with this), it is a valuable skill to be able to tell whether a solution can get accepted or not.

I was preparing D, and I was pushing for 26 characters. I made a conscious decision to abandon TL > x2 unoptimised model solution rule because there are not many different ways to implement submask dp, so all reasonable solutions should be closely the same (unless they are optimised a bit). As dario2994 said, he implemented several reasonable ways, all of them were under 9 seconds, also I asked all the authors to implement "a solution like they would do it in contest", and all of them were in the 6-10 range. AC statistics shows that indeed most of the solutions fall in the 6-10 range, which we were going for. I have no regrets. To sum it up: yes, this problem doesn't follow your rules for setting TL, no, I don't think it was a bad decision.

For C I can't agree with you on any level, not only we allowed $$$O(n^6)$$$ solutions, we also set TL as x3 from $$$O(n^6)$$$ solution, I can't see any reason to call this TL tight.

The situation with E is not good, we apologise.