It’s finally time for one of the biggest events in the competitive programming world. The SnackDown ‘21 Grand Finale is here.
The entire Grand Finale event is scheduled to be completed in two days — January 8 (Saturday), and January 9 (Sunday).
For the Finalists
All the information has been shared over email, but summarising — The Grand Finale will be spread over two days and will be a closed event accessible only to the finalists, and a few invited guests. The SnackDown 2021 Final contest will be held on Jan 9th between 6:30 — 10:30 PM (IST).
For the last time for this SnackDown, meet the panelists!
- Contest Admins: Anton antontrygubO_o Trygub and Yahor 244mhq Dubovik
- Head Admin: Alex Um_nik Danilyuk
- Testers: Ashley errorgorn Khoo and Andrew ecnerwala He
- Setters: Federico dario2994 Glaudo, Anton antontrygubO_o Trygub, Yahor 244mhq Dubovik, Yash PoPularPlusPlus Thakker, Arul flamestorm Kolla
- Statement Verifier: Ashley errorgorn Khoo
For the Community
For those who would like to have a taste of the SnackDown Final problems, we also have the SnackDown Final Parallel Unrated Contest scheduled for January 9, 2022, 6:30 PM — 10:30 PM (IST). The problems will be the same as the Finale. Since the main Finals will be a restricted session, the rank list can be viewed here. Note that the rank list will be frozen for the last hour, and will be resolved in the post-contest ceremony on YouTube.
The Grand Finale Closing & Crowning Ceremony
The SnackDown ‘21 Finale closing ceremony will start on Jan 9th at 10.30 PM IST. It will be hosted by Kamil Debowski and Ashish Gupta, who will be analyzing the contest problems and the strategies and performances of the participants. This is also where you can witness the moment of truth, the SnackDown ‘21 Grand Finale winner announcement! Everyone is cordially invited to the event, and we request you to set your reminders here.
as a tester, i overslept the elimination round
as a setter, i have tried to make interesting and beautiful problems and recommend to give this contest
Up, the contest starts in 30 minutes.
.
i think codechef should keep this leaderboard for regular standing too. it looks quite nice and able to see all problems at once makes a big difference . i think it will be much better than normal standing page in codechef rounds
You mean displaying all the problems in the leaderboard without needing to scroll, right?
yes
Sure. Thank you for the feedback. We are already revamping the rankings page, will try to accommodate this too. :)
Would it be difficult to also show timestamps of submissions for each problem on the leaderboard? This information is useful during contests, because it allows to roughly guess how much time people (from someone's friend list) typically spend on each problem.
And after a contest, being able to sort submissions by execution time would be also very useful. I'm sometimes interested in checking the most performance optimized submission, but the CodeChef UI doesn't seem to provide an easy way to find it.
The contest has finished, we hope you liked the problems!. We enjoyed seeing the finalists compete fiercely up to the very last minute!
If you are interested, there is a wonderful final ceremony (with some comments on the contest by none other than antontrygubO_o and Um_nik, and with the revelation of the final ranking) hosted by Errichto and Ashishgup.
Ashish Gupta cohosted it
Congratulations Rewinding!, tourist! and Benq!
I really enjoyed the problems. It was the best onsite final problemset in 2021. Thank you!
dario2994 could you mind sharing some tricky cases for Climbing?
I am very happy to read that.
Here is a list of 1000 small tests (they are not tricky, but they are many): in and out.
Achtung: The editorial of CLIMBINGRANK will appear only after the first AC.
Congrats to Benq who is the first solver of CLIMBINGRANK!
Thank you for the contest! I enjoyed thinking about every problem.
A good easy problem.
I like the $$$O(n \log A)$$$ solution, and I actually almost implemented it (but I used a set instead of maintaining stack maxima). It's fine that solutions with an extra $$$\log$$$ factor passed too.
The first problem that made me think I was missing something obvious, given how quickly many people were solving it. Turned out I failed to recognize Stirling numbers :) The problem is far from obvious anyway, though.
A fun story: my first impression was "I must have solved this problem at AtCoder". I tried searching for it, but only found AGC052 D. Given that the problem is similar (but is asking for "equal LIS" instead of "equal number of records"), and the writer of both problems is antontrygubO_o, I thought "ok, I guess this is the problem I am looking for, it just looks similar, but it's a different problem" and stopped searching. Turns out I should have dug deeper to find AGC028 E.
The second problem that made me think I was missing something obvious. I spent a lot of time thinking about various applications of Minkowski sums, but none of them helped to solve the problem even for $$$k \le 10^3$$$, let alone $$$k \le 10^6$$$. In the last hour, I figured out the reordering trick: we can reorder the stolen items so that the sum on every prefix of length $$$i$$$ is close to $$$w \cdot \frac{i}{k}$$$. It was easy enough from there.
I came up with a slow DP solution pretty early into the contest (before solving my 3rd problem), but only figured out how to reduce its complexity during the last hour. It's fun to have a problem asking for a floating-point answer (which actually allows to speed up the solution too) instead of the exact answer modulo whatever, at least once in a while.
Given the contest situation, I basically discarded this problem, I only came up with a simple $$$O(n^4)$$$ solution. Looks fun to think about, though.
For ANDOFMAXES we originally wanted only $$$O(n \log C)$$$, but closer to the contest it turned out that we can't separate it well enough from $$$O(n \log n \log C)$$$ but we wanted to have a second problem before "hard part" so we decided to lower the limitations to let $$$O(n \log n \log C)$$$ to pass freely.
Thanks for the contest. I really enjoyed solving the first 4 problems.
In the contest, I implemented $$$O(n * (logn + logC))$$$ soln for
ANDOFMAXES
and it's a bit different from the soln given in the editorial. Probably others would have implemented it as well but since solns aren't public I will write it here for the sake of completeness.Given a fixed mask $$$M$$$ and let's define $$$dp[L][R][freeLeft][freeRight]$$$ as maximum no of subarrays we can divide subarray $$$A[L....R]$$$ such that AND of all maximums is a supermask of $$$m$$$, we are free to leave prefix if $$$freeLeft$$$ is true and we are free to leave a suffix if $$$freeRight$$$ is true.
The main idea is we query for the maximum in that range and if it's the subset of $$$M$$$ then it splits the range into 2 parts and we are allowed to skip prefix in one part and a suffix in another part, which would correspond to the subarray to which this maximum belongs.
If it isn't the supermask of $$$M$$$ then we will have to include this index in prefix or suffix which we are going to skip.
We want to know if $$$dp[1][n][false][false] \geq k$$$ for fixed mask $$$M$$$.
We can find range maximums using RMQ in O(1).
To find the value of particular $$$dp[L][R][freeLeft][freeRight]$$$ we first query for maximum in $$$A[L...R]$$$ let the index of maximum value be $$$I$$$.
If $$$A_{I}$$$ is supermask of $$$M$$$ then $$$dp[L][R][freeLeft][freeRight] = dp[L][I-1][freeLeft][true] + 1 + dp[I+1][R][true][freeRight]$$$
Otherwise,
$$$dp[L][R][freeLeft][freeRight]$$$ is -
$$$max(dp[L][I-1][freeLeft][freeRight],dp[I+1][R][freeLeft][freeRight])$$$ if both $$$freeLeft$$$ and $$$freeRight$$$ are true,
$$$dp[L][I-1][freeLeft][freeRight]$$$ if $$$freeRight$$$ is true,
$$$dp[I+1][R][freeLeft][freeRight]$$$ if $$$freeLeft$$$ is true,
$$$-INF$$$ otherwise.
It can be seen that these have $$$O(n)$$$ states if implemented recursively.
There would be $$$O(logC)$$$ candidature $$$M$$$ and checking for each one takes $$$O(n)$$$ time. Overall $$$O(n logC)$$$.
Building RMQ would take $$$O(n log n)$$$.
My submission
"solns aren't public"
Sorry, missed that. All submissions should be public now.