We invite you to participate in either CodeChef’s November Cook-Off or SnackDown Pre-Elimination, this Sunday, 21st November, rated for all. Cook-Off’s Div-1 and SnackDown Pre-Elimination will have the same problems.
Time: 9 PM — 12 AM IST
On the problem setting panel are:
Setters: Utkarsh Utkarsh.25dec Gupta, Surya evilbuggy Prakash, Federico dario2994 Glaudo, Jeevan JeevanJyot Jyot Singh, Manuj Nanthan
Testers: Anton antontrygubO_o Trygub, Yahor 244mhq Dubovik
Statement Verifier: Anton antontrygubO_o Trygub, Yahor 244mhq Dubovik
Contest Admins: Anton antontrygubO_o Trygub, Ashish Ashishgup Gupta
Mandarin Translator: Qingchuan qingczha Zhang
Russian Translator: Kostia lkosten Yarmash
Vietnamese Translator: Team VNOI
Users who have qualified to participate in the SnackDown Pre-Elimination cannot participate in the Cook-Off. The Pre-Elimination will be rated for all users participating in it.
The Div-1 Cook-Off and Pre-Elimination ranklists will be merged to determine the winners of the cash/Amazon voucher prizes. Prizes for Cook-Off and Lunchtime Div-2 and Div-3 have been stopped from this month.
Plagiarism checks are being done on all the Snackdown rounds, and will be announced within a week, after which the Pre-Elimination ranklist will be finalized. Cheaters caught will be permanently banned from the platform.
The video editorials of the problems will be available on our YouTube channel as soon as the contest ends. Subscribe to get notifications about our new editorials.
Also, 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!
Why both contests at same time? Is there any reason?
simply , because they have shortage of problems for div-1 and pre-elimination round.
How many testers you want Admin : Yes
Testers:NO
reference previous contest
Plagiarism checks are being done on all the Snackdown rounds, and will be announced within a week, after which the Pre-Elimination ranklist will be finalized. Cheaters caught will be permanently banned from the platform.This puts a smile on my face.
Can we say that Snackdown was a bait from CodeChef for the cheaters? Let's see what will happen!
... background: where is my popcorn? ...
Shouldn't plag should be checked in cook-off also if the problem set for both of them is nearly same.?? Literally everyone's solution for div2 D is exact same
But if I tell you the reality, the cheaters have changed their code just a little bit such as func name or added some extra lines and they are not being taken into consideration. If you don't believe me then go to the slippers problem and check the successful submission check the last 100 and more than 90 have the same code just a bit changes
Prizes removed from div2 and div3 and I wasn't able to win once.
I won one but didn't got anything yet.
The Pre-Elimination will be rated for all users participating in it....Then if i attend only on pre-elimination then i rated as global round of all div, sir ? CodeChef_admin
How many will qualify for elimination?
top 500 + [80 slots for global children, indian children + girls]
Isn't "+ girls" unfair?
Are the 4 problems shown in the contest in a seperate category part of snackdown?(it should consist of div2,div3 only problems)
Is there a soln to DECSUBK that works in $$$O(n ^ 3)$$$ or similar or are they just troll constraints? I got AC with an $$$O(n \cdot logn)$$$ solution but I can't think of any simpler idea with worse complexity.
Brute forcing the solution by checking for each index the minimum number possible on that position will work in O(n^3 log(n))
My $$$O(n^3log(n))$$$ solution was to greedily assign the elements from $$$1$$$ to $$$n$$$, checking if it's possible by seeing if the minimum possible longest non-decreasing subsequence length is $$$<= k$$$. If [min possible] <= k <= [max possible], k must be achievable.
My soln was $$$O(n^3*logn)$$$ and it aced in
0.34s. I found LIS of $$$O(n^2)$$$ sequences in $$$O(n*logn)$$$.I did it in O(n^3).For every element in the sorted array I made an LIS array and checked at which position can the current element be inserted so as to not exceed LIS by k.
What's your solution?
Lets make some observations:
If an element $$$i$$$ appears $$$x_i$$$ times, the length of the longest non-decreasing subsequence is at least $$$x_i$$$. So the answer doesn't exist if there exists some $$$x_i \gt k$$$.
The length of the longest non-decreasing subsequence of an array made up of $$$k$$$ strictly decreasing segments is at most $$$k$$$.
If for each element $$$i$$$, we place its $$$x_i$$$ occurrences in $$$x_i$$$ contiguous segments $$$[l_i, l_i + x_i - 1]$$$, such that $$$l_i \lt l_j$$$ if and only if $$$i \lt j$$$ and all $$$k$$$ segments are non-empty, the length of the longest non-decreasing sequence is exactly $$$k$$$.
To produce the lexicographically smallest non-decreasing sequence in this manner, it is optimal to make as many of these segments (from left to right) as possible have exactly one number, and for this number to be as small as possible.
This yields a simple greedy where if we have placed the occurrences of the first $$$i - 1$$$ elements in the first $$$j$$$ segments till now, it is optimal to place the element $$$i$$$ in the range $$$[j, j + x_i - 1]$$$ or $$$[k - x_i + 1, k]$$$ if $$$j + x_i - 1 \gt k$$$.
This can be implemented using a map or array of the number of times an element appears in O(n logn) or O(n) respectively.
.
Why is pre-elim round rated? I've qualified, but at what cost T_T
++
CodeChef_admin Will the top 500 of this round get T-shirts?
Same question.But I think in this round 580 people will be qualified and 80 of them will not get a t-shirt as the rule states top 500 contestants of eliminations will get t-shirts.
NO, this was pre Elimination round. This is mentioned on the prizes page.
Top 500+80 will qualify for the elimination. So the top 500 out of those 580 will get T-shirt!! Does not seem right for me
I hate GUESSROW.
IMHO hiding this information is too unfair.
I ran my solution locally with different seeds, it used in average 590-620 queries per test, then I chose the best seed for my interaction (which was probably as good to any other interactor as any other seed) and submitted, assuming that there are not a lot of tests and I can force it to pass in an expectedly finite number of attempts; it only took one.
Yes, so your situation is OK. For me, who was not very clever, it was something like 600-650, and it was impossible to tell appropriately from the information available from the statement when to stop improving the solution.
Hating the problem seems a bit too much (though your opinion was shared by the coordinator...) but what you say about the number of tests is correct. It would have been better to say the number of tests explicitly.
In SLIPPERS only after third wrong attempt I've realized that there is a second sample test, don't do that.
I have realized that after seeing your comment, LOL
I also didn't notice it.I think they should give explanation only after giving all the samples.
I do agree, sadly codechef interface does not allow for it.
https://github.com/jmerle/competitive-companion was the only reason I realised there is 2nd sample.
I realized it after seeing your comment and made 6 WA's which could have been avoided.
Let me join your club of "super-attentive-and-scrupulous-coders". To be honest, I don't understand why they couldn't place the samples together, before or after the explanation.
Why $$$M=1$$$ in MEGAMU2...
Was it a special case for your code? I am asking because it was not special for the official solution, so I don't see what's wrong with it.
I can say for myself, that I noticed that the sequences where $$$\mu$$$ is nonzero can be described as follows:
Then I calculated some dp, and I had to handle $$$M = 1$$$ manually to calculate the number of valid $$$p$$$-s.
Thank you, now I see the point (I knew about this solution, but I completely forgot about it when writing the above comment).
That is exactly what I did. Thanks for the explanation.
Hello everyone. After the round was over I have started to examine some problem "Slippers" solutions and they were all suspicious identical. Judge yourself:
Submission #1
Submission #2
Submission #3
Submission #4
unfortunately, almost all the submissions were like this.
I have noticed suspiciously big jump in number of AC for SLIPPERS approximately half of hour before end of contest. Then after contest was finished I decided to check couple SLIPPERS solutions which were made in the last half of hour and ACed from the first try and a lot of them (1,2,3,4) are identical. So indeed there was some leaked solution, unfortunately. Fingers crossed for CodeChef's MOSS system.
Another interesting finding is that masoom_41 placed 305 with a single problem solved. Is it some weird platform glitch?
Most likely he ACed one of 4 problems before they were removed. /cc CodeChef_admin
Upd: His cc profiles says 2 acs
SNCKPE21: ODDSEVENS, PRDTPAINbutODDSEVENSwas non scorable in snackdown.Thanks for reporting this. Yes, it was a glitch with just this 1 user due to the non-scorable problem being removed during the contest. It has been fixed.
how to solve slippers.
Thanks for the contest, very nice problemset.
For GOODRANKING, I did some randomization and it passed: https://www.codechef.com/viewsolution/54143464. Not sure why though, my check function works in O(n^2) in worst case, so overall worst case time complexity should be O(n^3).
UPD : Code works even without randomization. No idea how xD
Very nice contest, specifically the part authored by dario2994. Much better than I expected from CodeChef. Hopefully the elimination/finals will be as nice.
Thanks :)
BTW how the rating update works? Div.1+pre-elimination merged ranklist or separate ranklist?
Can anyone tell me why ternary search on $$$j$$$ doesn't work in first problem
or tell me if there is something wrong in my ternary search implementation
I used ternary search as the search space just always have one max value
and it is somewhere in middle of the subarray and either side of that point the answer will decrease
almost 2 hours I just tried to figure out some case where it doesn't work
then finally I changed my solution to just binary search for nearest value to (max value + min value)/2 of subarray
and got AC
Thanks to nishuz
It's probably because the elements are not necessarily distinct.
Can you elaborate ?? or provide a case where non-unique elements can cause problem
In one of my test cases I tried with two same elements but answer with AC code and ternary search code is same
122
4198 64681 64681 170354 184105 260755 266089 276941 291007 308476 403089 507632 634491 671956 696025 701559 840269 841495 847153 913970 916987 994161
THANK YOU!! very much for providing that test case
Learnt a bit more about about ternary search today
I modified my code so that there are only distinct values when I ternary search
If anyone interested in ternary search solution Code
during the 25 last minutes of the contest, there are about 400+ accepted solution for "Guests like slippers".
most of them are the first submission, i.e. no penalty.
that's great ! hope the next round will also be fantastic like this ! everyone knows suddenly how to programming...
A lot of courage bro!!!! A lot of courage. :O
I'll just leave this here:
indeed a nice idea, ranking should be frozen at 1:58.
Really enjoyed solving D, the observation was cute and felt rewarding (though I'm not sure if I had the intended solution).
Video Editorial for A,B,C Div.1
When will the ratings get updated?
I think it is completely unreasonable to expect fast rating updates AND thorough plagiarism checking.
CodeChef_admin I have seen that my rank in SnackDown Pre-Elimination jumped up by ~40 positions and that the rating were updated. Does it mean that plagiarism checks were done already? And if so — why all solutions from my and 3 out of 4 solutions from DoIGetConribution's comment weren't removed and authors weren't banned from appropriate contest and from platform at all?
CodeChef_admin I investigated submissions history of this one guy from DoIGetConribution's comment who was removed and I guess I know what's going on. You guys have removed from the scoreboard participants who have submitted solution for both SnackDown Pre-Elimination and November Cook-Off and preliminarily updated ratings but plagiarism checks are still pending/in progress. Is it correct?
That is correct.
Its more than a week ...... How much time more codechef take to ban cheaters...
CodeChef_admin my rank in snackdown pre elimination was 905 and rating was updated according to it but now my rank is 715, still the rating is the same. Is it expected or it will be fixed?
It is expected. Ratings will be recalculated for all contests only after a few more months when all plagiarism checks have been done.
CodeChef_admin Are Plagiarism checks for all rounds of Snackdown done ?and when can we get final list of users participating in elimination round?
Do 6 months count as "few"?