### antontrygubO_o's blog

By antontrygubO_o, 6 months ago, translation,

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!

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

• +203

 » 6 months ago, # |   +207 as a tester, i overslept the elimination round
 » 6 months ago, # |   0 as a setter, i have tried to make interesting and beautiful problems and recommend to give this contest
 » 6 months ago, # |   +31 Up, the contest starts in 30 minutes.
 » 6 months ago, # | ← Rev. 2 →   -30 .
 » 6 months ago, # |   0 WHere can I find the live leaderboard??
•  » » 6 months ago, # ^ |   0
 » 6 months ago, # | ← Rev. 2 →   0 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
•  » » 6 months ago, # ^ |   +15 You mean displaying all the problems in the leaderboard without needing to scroll, right?
•  » » » 6 months ago, # ^ |   0 yes
•  » » » » 6 months ago, # ^ |   0 Sure. Thank you for the feedback. We are already revamping the rankings page, will try to accommodate this too. :)
•  » » » » » 6 months ago, # ^ |   +13 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.
 » 6 months ago, # | ← Rev. 2 →   +95 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.
•  » » 6 months ago, # ^ |   +26 Ashish Gupta cohosted it
 » 6 months ago, # |   +39 Congratulations slime!, tourist! and Benq!
 » 6 months ago, # |   +82 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?
•  » » 6 months ago, # ^ |   +64 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.
•  » » » 6 months ago, # ^ | ← Rev. 2 →   -84 So that you can use that AC solution as an editorial lmao
•  » » » 6 months ago, # ^ |   +106 Congrats to Benq who is the first solver of CLIMBINGRANK!
 » 6 months ago, # |   +181 Thank you for the contest! I enjoyed thinking about every problem. ONESGUESSA good easy problem. ANDOFMAXESI 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. PERMRANGESThe 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. EQPRFMAXSPLTA 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. ROBBERYPLANThe 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. BAKERYI 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. CLIMBINGRANKGiven 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.
•  » » 6 months ago, # ^ |   +26 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.
•  » » 6 months ago, # ^ | ← Rev. 3 →   +8 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. SpoilerGiven 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). SpoilerTo 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
•  » » » 6 months ago, # ^ |   +2 "solns aren't public"Sorry, missed that. All submissions should be public now.
•  » » » » 6 months ago, # ^ |   -7 What is your take on this :: 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
 » 6 months ago, # |   0 Congratulations to the winners!Since, snackdown is over, can I know when can I receive my Amazon-coupon and T-shirt? I received a mail back on 16th November regarding the coupon and T-shirt. I had also filled the form, but I didn't listen anything back from codechef since. I won them through the referral leaderboard system.Thank You. CodeChef_admin suraj_sharma