By CodeChef_admin, history, 2 months ago,

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:

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!

• +66

 » 2 months ago, # |   -25 Why both contests at same time? Is there any reason?
•  » » 2 months ago, # ^ |   +13 simply , because they have shortage of problems for div-1 and pre-elimination round.
 » 2 months ago, # |   -23 How many testers you want Admin : YesTesters:NOreference previous contest
 » 2 months ago, # |   +88 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.
•  » » 2 months ago, # ^ |   +34 Can we say that Snackdown was a bait from CodeChef for the cheaters? Let's see what will happen!... background: where is my popcorn? ...
•  » » 2 months ago, # ^ |   +8 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
•  » » 2 months ago, # ^ |   +3 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
 » 2 months ago, # |   +24 Prizes removed from div2 and div3 and I wasn't able to win once.
•  » » 2 months ago, # ^ |   0 I won one but didn't got anything yet.
 » 2 months ago, # | ← Rev. 2 →   -19 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
 » 2 months ago, # |   +1 How many will qualify for elimination?
•  » » 2 months ago, # ^ |   0 top 500 + [80 slots for global children, indian children + girls]
•  » » » 2 months ago, # ^ |   -62 Isn't "+ girls" unfair?
•  » » » » 2 months ago, # ^ |   -42 no, its totally fair. girls in India don't know much coding, or are very smart so they need special prizes for them just to make them feel comfortable.Otherwise, direct competition with boys will destroy their self esteem.
•  » » » 2 months ago, # ^ |   -14 and how will they know who are children and girls??
 » 2 months ago, # |   -6 Reminder: Contest starts in ~45 minutes.
 » 2 months ago, # |   +20 Are the 4 problems shown in the contest in a seperate category part of snackdown?(it should consist of div2,div3 only problems)
•  » » 2 months ago, # ^ |   0 Those 4 problems are not a part of the contest. The "Non-scorable" heading was missing. They were totally removed after the first couple of minutes. Apologies for the confusion.
 » 2 months ago, # | ← Rev. 4 →   -40 Maybe not
 » 2 months ago, # |   +8 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.
•  » » 2 months ago, # ^ |   +25 Brute forcing the solution by checking for each index the minimum number possible on that position will work in O(n^3 log(n))
•  » » 2 months ago, # ^ |   +22 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.
•  » » 2 months ago, # ^ |   +15 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)$.
•  » » 2 months ago, # ^ |   +4 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.
•  » » 2 months ago, # ^ |   +24 What's your solution?
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +32 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. Code#include #define int long long using pii=std::pair; using namespace std; const int maxn = 205; int t, n, k, a[maxn]; int32_t main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> t; for(int cases = 0; cases < t; cases++) { cin >> n >> k; map cnt; for(int i = 0; i < n; i++) { cin >> a[i]; cnt[a[i]]++; } int maxcnt = 0; for(auto x : cnt) maxcnt = max(maxcnt, x.second); if(maxcnt > k) { cout << "-1\n"; continue; } vector parts[k]; int at = 0; for(auto x : cnt) { at = min(at, k - x.second); for(int j = 0; j < x.second; j++) parts[at + j].push_back(x.first); at += x.second; } vector res; for(int i = 0; i < k; i++) { reverse(parts[i].begin(), parts[i].end()); res.insert(res.end(), parts[i].begin(), parts[i].end()); } for(auto x : res) cout << x << " "; cout << "\n"; } return 0; } 
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 .
 » 2 months ago, # |   +188 Why is pre-elim round rated? I've qualified, but at what cost T_T
•  » » 2 months ago, # ^ |   +49 ++
 » 2 months ago, # |   +13 CodeChef_admin Will the top 500 of this round get T-shirts?
•  » » 2 months ago, # ^ |   +8 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.
•  » » 2 months ago, # ^ |   +8 NO, this was pre Elimination round. This is mentioned on the prizes page. Top 500 participants from the Elimination round will get a cool SnackDown t-shirt.
•  » » » 2 months ago, # ^ |   +18 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
 » 2 months ago, # |   +93 I hate GUESSROW.IMHO hiding this information is too unfair.
•  » » 2 months ago, # ^ |   +6 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.
•  » » » 2 months ago, # ^ |   0 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.
•  » » 2 months ago, # ^ |   +21 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.
 » 2 months ago, # |   +169 In SLIPPERS only after third wrong attempt I've realized that there is a second sample test, don't do that.
•  » » 2 months ago, # ^ |   +34 I have realized that after seeing your comment, LOL
•  » » 2 months ago, # ^ |   +39 I also didn't notice it.I think they should give explanation only after giving all the samples.
•  » » » 2 months ago, # ^ |   +8 I do agree, sadly codechef interface does not allow for it.
•  » » 2 months ago, # ^ |   +18 https://github.com/jmerle/competitive-companion was the only reason I realised there is 2nd sample.
•  » » 2 months ago, # ^ |   +14 I realized it after seeing your comment and made 6 WA's which could have been avoided.
•  » » 2 months ago, # ^ |   -10 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.
 » 2 months ago, # |   +13 Why $M=1$ in MEGAMU2...
•  » » 2 months ago, # ^ |   +11 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.
•  » » » 2 months ago, # ^ |   +10 I can say for myself, that I noticed that the sequences where $\mu$ is nonzero can be described as follows: Delete all zeroes. Let the part before first element greater than $2$ be $p$, the remaining part be $s$. Delete all ones from $s$. either $p$ is an even number of twos, or $p$ has an odd number of twos before the first one; $s$ consists of blocks of type $(x+1)^+(x)^+$ and $(xx)^+$; $s$ does not have falls by at least two. Then I calculated some dp, and I had to handle $M = 1$ manually to calculate the number of valid $p$-s.
•  » » » » 2 months ago, # ^ |   +8 Thank you, now I see the point (I knew about this solution, but I completely forgot about it when writing the above comment).
•  » » » » 2 months ago, # ^ |   0 That is exactly what I did. Thanks for the explanation.
 » 2 months ago, # |   +33 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 #1Submission #2Submission #3Submission #4unfortunately, almost all the submissions were like this.
•  » » 2 months ago, # ^ |   +15 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.
•  » » » 2 months ago, # ^ |   0 Another interesting finding is that masoom_41 placed 305 with a single problem solved. Is it some weird platform glitch?
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   +7 Most likely he ACed one of 4 problems before they were removed. /cc CodeChef_adminUpd: His cc profiles says 2 acs SNCKPE21: ODDSEVENS, PRDTPAIN but ODDSEVENS was non scorable in snackdown.
•  » » » » » 2 months ago, # ^ |   +3 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.
 » 2 months ago, # |   +30 how to solve slippers. Read GP of IMO J ??? win
 » 2 months ago, # | ← Rev. 4 →   +8 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
 » 2 months ago, # |   +49 Very nice contest, specifically the part authored by dario2994. Much better than I expected from CodeChef. Hopefully the elimination/finals will be as nice.
•  » » 2 months ago, # ^ |   +12 Thanks :)
 » 2 months ago, # |   +29 BTW how the rating update works? Div.1+pre-elimination merged ranklist or separate ranklist?
 » 2 months ago, # | ← Rev. 3 →   0 Doubt clearedCan anyone tell me why ternary search on $j$ doesn't work in first problemor tell me if there is something wrong in my ternary search implementationI used ternary search as the search space just always have one max valueand it is somewhere in middle of the subarray and either side of that point the answer will decrease Code in C++ #define ll long long int n; cin >> n; vector < ll > a(n); for (int i = 0; i < n; i++) cin >> a[i]; ll ans = 0; auto eval = [&](ll i, ll j, ll k) -> ll { return ((i — j) * (j — k)); }; auto ternary_search = [&](vector < ll > &subarr) -> ll { ll k = subarr.front(); // minimum value ll i = subarr.back(); // maximum value // search space is excluding minimum and maximum value ll left = 1, right = (int)subarr.size() — 2, max_possible = LLONG_MIN; while (left <= right) { int elements = right - left + 1; int mid1 = left + (elements / 3); int mid2 = left + ((2 * elements) / 3); assert(left <= mid1 && mid1 <= right); assert(left <= mid2 && mid2 <= right); ll value1 = eval(i, subarr[mid1], k); ll value2 = eval(i, subarr[mid2], k); if (value1 > value2) { max_possible = max(value1, max_possible); right = mid2 — 1; } else if (value1 < value2) { max_possible = max(value2, max_possible); left = mid1 + 1; } else { max_possible = max(value1, max_possible); left = mid1 + 1; right = mid2 - 1; } } return max_possible; }; for (int i = 0; i < n - 2; i++) { vector < ll > subarr{a[i], a[i + 1]}; for (int j = i + 2; j < n; j++) { subarr.push_back(a[j]); // subarray of [i,j] ans += ternary_search(subarr); } } cout << ans << "\n";  almost 2 hours I just tried to figure out some case where it doesn't workthen finally I changed my solution to just binary search for nearest value to (max value + min value)/2 of subarrayand got AC Thanks to nishuz
•  » » 2 months ago, # ^ |   0 It's probably because the elements are not necessarily distinct.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 Can you elaborate ?? or provide a case where non-unique elements can cause problemIn one of my test cases I tried with two same elements but answer with AC code and ternary search code is same Test Case 1224198 64681 64681 170354 184105 260755 266089 276941 291007 308476 403089 507632 634491 671956 696025 701559 840269 841495 847153 913970 916987 994161
•  » » » » 2 months ago, # ^ |   0 Spoiler8 3 4 4 6 8 8 9 9 Correct: 76 Wrong: 72 
•  » » » » » 2 months ago, # ^ |   +3 THANK YOU!! very much for providing that test caseLearnt a bit more about about ternary search todayI modified my code so that there are only distinct values when I ternary searchIf anyone interested in ternary search solution Code
 » 2 months ago, # |   +94 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...
•  » » 2 months ago, # ^ |   +4 A lot of courage bro!!!! A lot of courage. :O
•  » » 2 months ago, # ^ |   +59 I'll just leave this here:
•  » » » 2 months ago, # ^ |   -31 indeed a nice idea, ranking should be frozen at 1:58.
 » 2 months ago, # |   +13 Really enjoyed solving D, the observation was cute and felt rewarding (though I'm not sure if I had the intended solution).
 » 2 months ago, # |   0
 » 2 months ago, # |   +2 When will the ratings get updated?
•  » » 2 months ago, # ^ |   +63 I think it is completely unreasonable to expect fast rating updates AND thorough plagiarism checking.
 » 2 months ago, # |   -18 When will the November Cook-Off rankings will be out? Why it is taking so much more time than usual?
 » 2 months ago, # |   +6 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?
•  » » 2 months ago, # ^ | ← Rev. 3 →   +5 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?
•  » » » 2 months ago, # ^ |   +20 That is correct.
 » 2 months ago, # |   +12 Its more than a week ...... How much time more codechef take to ban cheaters...
 » 7 weeks ago, # |   +16 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?
•  » » 7 weeks ago, # ^ |   +12 It is expected. Ratings will be recalculated for all contests only after a few more months when all plagiarism checks have been done.
•  » » » 7 weeks ago, # ^ |   +1 CodeChef_admin Are Plagiarism checks for all rounds of Snackdown done ?and when can we get final list of users participating in elimination round?