We are very glad to invite you to participate in SnackDown Elimination round! It will be **rated** for all participants.

60 participants will qualify for the finals from the Elimination round. They include:

- The top 25 participants from the Elimination round.
- Additional top 2 school participants
- Additional top 2 female participants
- Additional 31 Indian participants, including:
- 10 top Indian participants
- The next 15 Indian participants from the Elimination Round qualify provided they solve at least 2 problems.
- 3 top Indian School participants
- 3 top Indian Female participants

Those, who haven't advanced, are invited to participate in the Parallel rounds, which will be held for all divisions. All three rounds are **rated** too.

**Please note that the duration was initially written as 5 hours by mistake, it will actually be 3 hours. The Finals duration will also be less than 5 hours.**

Joining us on the problem setting panel are:

- Contest Admins: Yahor 244mhq Dubovik and Anton antontrygubO_o Trygub
- Head Admin: Alex Um_nik Danilyuk
- Testers: Utkarsh Utkarsh.25dec Gupta (only for Div2 and Div3 problems), Tejas tejas10p Pandey (only for Div2 and Div3 problems), Yahor 244mhq Dubovik, Alex Um_nik Danilyuk, Anton antontrygubO_o Trygub
- Setters:
- Elimination: Federico dario2994 Glaudo, Fedor Mediocrity Korobeinikov, Anton antontrygubO_o Trygub, Alex Um_nik Danilyuk
- Additional Div3-Div2 problems: Nandeesh nandyboy Gupta, Utkarsh Utkarsh.25dec Gupta, Daanish Mahajan, Soumyadeep soumyadeep_pal_21 Pal, Surya evilbuggy Prakash, Srikkanth srikkanthr R, Mradul bhatnagar.mradul Bhatnagar

- Statement Verifier: Nishank IceKnight1093 Suresh (only for Div2 and Div3 problems), Yahor 244mhq Dubovik, Anton antontrygubO_o Trygub
- Editorialist: Taranpreet taran_1407 Singh (only for Div2 and Div3 problems)

Users who have qualified to participate in the SnackDown Elimination should not participate in the Parallel rounds.

The Div-1 Parallel round and the Elimination ranklists will be merged to determine the winners of the cash/Amazon voucher prizes.

If you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here.

Hope to see you participating. Good luck and have fun!

Regardless of how much one may/should care for CodeChef ratings, I still believe

official participantsshould not be involuntarily rated for any special competition like this.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.

We can always break the norm.

Forcingsomeone to be rated is nothealthy competitionby any means as the other reply suggests. AtCoder already making strides in this, since you can even gain GP30 points unrated now. I don't see how 5 star LGM's in the finals is anadvantagefor anyone either.The primary focus for these rounds should always be to qualify to the next ones and I'd personally find it more enjoyable if ratings weren't involved.

Sorry, I don't really understand your position. How exactly would competition be more enjoyable for you if ratings weren't involved? You wouldn't be interested in solving as many problems as possible anymore? Imo, "healthy" competition is when everyone is trying to do his best.

In first rounds of Hackerrank and Codejam, where the qualifying criteria is just to get some minimum number of points/get some rank>=2000, a lot of participants just fullfill that minimum criteria and don't even try to do later problems (I also don't). There is no point in trying to solve them, nothing is at stakes, the only reason to do it is out of interest. I personally always feel like those harder problems are just wasted. They don't matter for competition at all. How is that good? I don't want last problems in Snackdown to be wasted (as I personally believe that they are too good for this), I want participants to be motivated to solve them, making contest rated is a good way to do this.

About AtCoder: the main goal of introducing Rated/Unrated system there, from this blog, was to solve the issue that "you can leave the contest without submission to keep your rating. This implies you may get underrated because of those who didn't submit." So it's main goal in some sense is to "force" you to be rated if you decided to join, not to provide an opportunity for those who are afraid to lose their precious rating to participate.

And unrated (<1200) users were eligible for GP30 points even before this change.

I agree good problems can be

wastedif there's a high cut-off for qualifications and participants lose interest after somewhat guaranteeing a spot midway. I'm also sure plenty of people would prefer to be rated as well and I'm glad that's happening. But what AtCoder is currently doing isforcingus to make a choice beforehand, and I'd like to have that choice.Of course, I'm always trying to solve

as many problemsin a contest, which helps in improving ratings. But these rounds already have increased rewards as incentives. Hence not having to worry about potential rating drops (as cowardly/stupid as that sounds) can make it more enjoyable for some of us.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.

Yet in reality the only thing that was "encouraged" was cheating and even more cheating. With ratings at stake a considerable number of participants sought the illegal way out, and I really doubt that all of them have been caught.

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

Difficult to understand the reason behind making official round rated for all.CodeChef_admin Can you please clear it out ? It would've been great.

Phew, I saw a few days ago that it was 5 hours and was a bit scared.

One question for CodeChef_admin. Many cheaters have been caught and evicted from SnackDown. Are they allowed to participate in the upcoming parallel rounds?

For example, this 7-star wannabe got successfully promoted to 4-stars thanks to cheating in the SnackDown Pre-Elimination round. Yes, this person isn't listed in the Pre-Elimination scoreboard anymore. But are people like this going to keep their stars and have another chance to cheat?

aren't they permanently banned?

Yes, they are supposed to be permanently banned. But if CodeChef's bureaucratic machinery is acting slow and cheaters' accounts are not really suspended yet, then the cheaters may use this opportunity to slam the door on their way out (by cheating the hell out of the today's parallel rated contest). That's what I wanted to confirm.

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.

that's one hell of contest coordinators...

Up! And good luck to the participants.

p.s. This issue with samples is still present, be aware of it.

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.

Contest starts in 1 hour.

SpoilerThanks radoslav11

Random Convex Hullhttps://codeforces.com/blog/entry/59314?#comment-429094

Can you explain approach for B?

Consider a segment $$$(x[i], y[u])$$$, $$$(x[j], y[v])$$$, count the number of ways s.t. the segment is a side of convex hull.

Since all the costs are less than $$$D$$$, our first priority should be to minimize the sum of $$$|i - j|$$$, so the optimal path must look like a loop between $$$1$$$ and $$$N$$$ where we visit each intermediate vertex either in the forward direction from $$$1$$$ to $$$N$$$, or in the backwards direction from $$$N$$$ to $$$1$$$. We do dynamic programming where $$$dp[last][i]$$$ is the minimum distance from $$$1$$$ to $$$i$$$ with the last skipped vertex being $$$last$$$. This dp will also include some of the costs of the backwards edges. So when we transition to some other vertex $$$j$$$, there are two cases:

Doing this dp naively is $$$\mathcal O(n^3)$$$, but the second case can be sped up to $$$\mathcal O(1)$$$ transition by maintaining the suffix minimum.

You can also just do forward dp with 2 transitions only. From $$$dp[last][i]$$$ you can go to $$$dp[last][i+1]$$$ or $$$dp[i][i+1]$$$.

Can you give a proof as to why should we first prioritize to minimize the sum of |i-j| only and not cij. I got it logically, but would be glad to know if there is some proof behind it!

There's a proof in the official editorial (along with a much simpler DP than mine).

contests like these show how pathetic i am at cp

adios ratings

I could have gone to sleep after first 30 mins and not affected my ranking at all...

I solved A,B,D,almost E but can't get AC on max palindrome problem(C in starting), can anyone give me what constructive will give AC on this problem.

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.

Where is the tutorial?

I liked ONECHANGE for the similarity with bin packing, MINMAXSWAP for the usefulness of studying this, and your consistent style of creating various LIS problems :)

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

How to solve

`Sorting Segments`

for any k<=n ?Why will ratings be updated after December Long Challenge(which ends on 13th)?Isn't that rated only div3.

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.

To get T-Shirt I have filled up the form (also ranked below 500). Should I have to do anything else except waiting?

I̶ ̶w̶o̶u̶l̶d̶ ̶s̶a̶y̶ ̶j̶u̶s̶t̶ ̶f̶i̶l̶l̶ ̶t̶h̶e̶ ̶f̶o̶r̶m̶ ̶i̶f̶ ̶y̶o̶u̶ ̶h̶a̶v̶e̶ ̶g̶o̶t̶ ̶t̶h̶e̶ ̶l̶i̶n̶k̶ ̶i̶n̶ ̶t̶h̶e̶ ̶e̶m̶a̶i̶l̶.̶ ̶T̶h̶e̶r̶e̶ ̶i̶s̶ ̶n̶o̶ ̶h̶a̶r̶m̶ ̶i̶n̶ ̶d̶o̶i̶n̶g̶ ̶i̶t̶.̶ ̶A̶l̶t̶h̶o̶u̶g̶h̶ ̶t̶h̶e̶i̶r̶ ̶w̶e̶b̶s̶i̶t̶e̶ ̶s̶a̶i̶d̶ ̶t̶o̶p̶ ̶5̶0̶0̶ ̶i̶n̶ ̶p̶r̶e̶-̶e̶l̶i̶m̶i̶n̶a̶t̶i̶o̶n̶ ̶I̶ ̶f̶e̶e̶l̶ ̶l̶i̶k̶e̶ ̶i̶t̶s̶ ̶5̶8̶0̶ ̶(̶e̶v̶e̶r̶y̶o̶n̶e̶ ̶w̶h̶o̶ ̶w̶a̶s̶ ̶r̶e̶g̶i̶s̶t̶e̶r̶e̶d̶ ̶f̶o̶r̶ ̶t̶h̶e̶ ̶e̶l̶i̶m̶i̶n̶a̶t̶i̶o̶n̶ ̶r̶o̶u̶n̶d̶)̶.̶ ̶A̶l̶t̶h̶o̶u̶g̶h̶ ̶~̶C̶o̶d̶e̶C̶h̶e̶f̶_̶a̶d̶m̶i̶n̶,̶2̶0̶2̶1̶-̶1̶2̶-̶0̶5̶ ̶w̶o̶u̶l̶d̶ ̶b̶e̶ ̶a̶b̶l̶e̶ ̶t̶o̶ ̶b̶e̶t̶t̶e̶r̶ ̶c̶l̶a̶r̶i̶f̶y̶ ̶i̶t̶.̶

My mistake. I wrongly remembered last time it was top 300 in pre elimination round. So I just assumed this time also its pre elimination round.

wow now learned another reason to dislike long term contest (first one was cheating issue.). You guys please consider to shorten this div3 contests durations.

CodeChef_admin now there is another contest for div2 and div3 users, and it is being conducted on 11th Dec, i.e., before the rating updates of long challenge and parallel snackdown contest. Now, what if someone from div1 will become div2 after rating updates parallel snackdown contest? He will be unrated for this starters round. Please take this contest after the rating changes of these 2 contests or else update the ratings of starters round in the last before confirming the final ratings in these 2 rounds.

11th Dec is also a bad time for a CodeChef contest, because there are already Codeforces and AtCoder contests scheduled for this date. Why do we have relatively longish boring pauses between contests and then suddenly crazy clustering on the same day?

When there are overlapping contests, this is the process followed:

The ratings have to be calculated in the order of the starting times of the contests. So the contest which started first has its rating calculated first, even if it ends later. Hence, in this case, the Long contest’s rating will have to be calculated first, then the Elimination rounds, and then START19. And because of this, the ratings of the short contests can also be calculated only after the Long contest ends.

This leads to one ambiguous case, which happens when the division of a user changes after the rating change of a contest which started earlier. This is taken care of by considering a user’s division for a particular contest to be division in which they were, when the contest actually started; and not what their division is when the ratings for this contest is actually calculated.

So for eg. suppose a user was in Div-3 when the Long contest started, but after the Long contest ends, and the ratings for the Long are calculated, they go up to Div-2. But when they took part in the short contests, their rating was still in Div-3. So they would still considered to be in Div-3 for those contests when the rating is calculated for those short contests. Likewise, if someone in Div-2 took part in the Elimination and in the Starters, but after the Long ends, their Elimination rating change took them to Div-1. But they would still be considered to be in Div-2 for the Starters, and hence the Starters would be rated for them, even though it is unrated for Div-1.

The main issue of course is that participants have to wait for their rating changes, till the Long contest ends. We are looking into ways to change our system so as to overcome this over the next few months.

tl;dr:Don’t worry about any of this, and just participate in the contests. If while participating, the system tells you that the contest is rated for you, it will be rated. If it says that it is unrated, it will be unrated. Irrespective of what happens to your division after the previous rating changes are calculated.This method is still not fully correct. For Div1 users who will drop to Div2 after the elimination round, starters will be unrated for them. But this is wrong, they should have got the chance in starters to improve their ratings. Best thing would be to update the rating for Div1 users atleast or just shift the starters contest by 3-4 days.

"This method is still not fully correct."

You are absolutely right. No one claimed that the method is ideal. We literally said that we are looking to improve it.

"Best thing would be to update the rating for Div1 users atleast"

As was explained above, that is not possible to do in the current rating system.

"just shift the starters contest by 3-4 days"

We have another contest scheduled in 4 days, and other contests after that. Postponing a contest indefinitely just because a few users will miss one chance at changing their rating is not something we want to do. Coders in the low Div-1 rating range will probably enjoy the Starters even if it is unrated for them, and we hope they value the participation for its own sake rather than just an obsession with rating.

I have got a doubt! Let's say X's rating was

`1900`

when the`Elimination Parallel`

started and obviously the same when he attended`STARTERS`

. X performs equally good in both the contests and should gain`+100`

for each of them. So will X's rating become`2100`

? CodeChef_adminIn TSP, can someone please explain why the optimal route looks like $$$1 < a_1 < a_2 < ... < n > b_1 > b_2 > ... > 1$$$?

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

Exercise for the reader (recommended to try before proceeding)While mathematically we have eliminated $$$i$$$, logically how does this make sense?

HintsHint 1The path is a cycle.

Hint 2What happens if we try cyclically rotating the list of our movements (move from $$$x$$$ to $$$x - 1$$$ or $$$x + 1$$$)?

Now suppose I extended the problem to say that you can visit the town

ORjust 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

Just a doubt if the path is something like

Now |i-j| in A is 3 and in B is 5. But if we think all Cij in A costs D-1 and in B costs 0. The total cost will be 6D-3 and 5D in A and B respectively.

I know these are not cycles and if we connect the last edge results will be different. But I want to know why for path and for cycle this is functioning differently??

Sorter Prodigy

Sorry :|

I think the contest is good on paper, but several issues made me dislike the contest.

For D, the solution concept was good, but the 12-second limit discourages the intended solution and the AC statistics shows that the TL was indeed tight. The problem is easy anyway, and I'm pretty sure that many people just thought the solution and didn't wrote it since it looks like a suboptimal solution.

I don't know why there were no limits like 20 distinct characters. The intended solution is simply not fast enough to hide the solution concept. In that case you should either accept the fact or give more generous TL.

C's limit gives me similar feeling, but at least the accepted solutions runs lenient enough, so I have no issues with it.

E has an interesting solution, but I knew the problem Benq linked, so it took me 3 minutes to google and copy-paste AC solution.

About D, we discussed if the best option was:

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 think I can somewhat agree with your statement but only if the TL was like at least 20 seconds. I guess your solutions were not radically faster than the participants, so say your solutions were running somewhere near 50%~75% of time limits. In that case, contestants getting AC or not is upon the jury's ability, not their ability: It depends on whether the intended solution went through strong tests that consider every detail (including caches), and if the servers are on CodeChef are fast enough.

In general, If you ask more to the contestants (e.g giving <3x TL), you need more duties to prove that your solutions are "different" from the pitfalls you created. I think the nature of the solution makes you somewhat free from the cache-related discussion, but the arguments should be based on evidence, not feelings.

If you are interested: this comment best summarizes what I think with strict TLs.

I agree with you more or less on everything.

Sadly, the option "25 seconds time limit" is borderline unfeasible and I think it is why we did not consider it (honestly, I did not even thought about it) and in any case also such option has drawbacks. Overall, I still believe that the choice we took was absolutely reasonable.

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.

I have a doubt based on MAXPALI, after testing it out with a few test cases on small numbers, I observed that when a palindrome $$$s_1s_2s_3......s_n$$$ on performing a circular shift (say removing some x letters at the front and appending it at the back) and forcing it to be a palindrome, makes

`all letters equal when x is not a divisor of n`

and when x is a divisor of n, it takes the form same as in the editorial. Could someone help me prove this / give a counter-test case for this fact?