By radoslav11, history, 6 weeks ago,

We invite you to participate in CodeChef’s June Cook-Off, this Sunday, 20th June, 9:30 PM — 12 AM IST.

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.

Joining us on the problem setting panel are:

Prizes:

The winners will receive CodeChef laddus with which they can claim cool CodeChef goodies. Know more here.

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.

Hope to see you participating. Good Luck!

Update: Problem POLYRT has been rejudged so that it also accepts solutions that considered the answer modulo $10^9+7$. We once again apologise for the inconvenience caused by the wrong statement.

• +49

 » 6 weeks ago, # |   +57 As a problem setter ...
•  » » 6 weeks ago, # ^ |   -16 As a commentator...
•  » » 6 weeks ago, # ^ |   +62 As Tester and Editorialist ...
•  » » » 6 weeks ago, # ^ | ← Rev. 2 →   +10 As another problem setter...
 » 6 weeks ago, # |   +5 Pls do something about cheaters , Codechef contests are being ruined by cheaters ... And cheaters are rising in numbers rapidly :(
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   +11 As a programmer, I can say that don't think about cheater because they are not limited to codechef only, they are continuously doing same thing with other platform too and discussing on cheater is like wasting of time because we or any problem setter or any tester can't do anything to stop them completely. So forgot those thing just participate and enjoy every contest.
•  » » » 6 weeks ago, # ^ |   0 +1
 » 6 weeks ago, # |   +16 These Codechef short contests always clashes with my sleeping schedule.
•  » » 6 weeks ago, # ^ |   +1 You ruined your sleep schedule practicing spikes with KAGEYAMA :)
 » 6 weeks ago, # |   +2 Codechef short contests always have a weird contest timing.
 » 6 weeks ago, # |   +4 I saw there are 3 divisions in Codechef, since I never participated I am Div. 3, does that mean I can only see the easy problems from the contest?
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   +7 Some problems from other divisions will also be visible to you and you are allowed to submit them too. However, you won't receive any points for those problems.If you scroll down the contest problems page, you will find a list of problems from other divisions which you are allowed to submit
•  » » 6 weeks ago, # ^ |   -8 You can only submit solutions in div3.
•  » » 6 weeks ago, # ^ |   +7 I just want to share my opinion that having 3 different divisions happening at the same time is a bit too much. Codeforces holds div3 rounds separately from Div2 and div1's because in that way you dont make more experienced newcomer miss the more challenging problems
•  » » » 6 weeks ago, # ^ |   +7 I mean it'll take you like 2 contests to reach div 1 probably, and it's not like you can't do the problems afterwards. Codeforces also holds div1 / div2 contests where experienced newcomers will have to participate in div2, so I don't see how that's any different.
 » 6 weeks ago, # |   +6 Reminder — the contest starts in an hour.
 » 6 weeks ago, # | ← Rev. 3 →   -18 In problem Binary String On steroids there is no mention about d. I have asked in the markdown but still did not received an answer. [Edit : Can we chose any value of k?] [Edit 2: I am sorry I got it]
•  » » 6 weeks ago, # ^ |   +8 Please read the problem statement again. :)
 » 6 weeks ago, # | ← Rev. 2 →   +8 There has been an announcement regarding the statement for POLYRT. Apologies for the inconvenience.Announcement:The statement of problem POLYRT had a mistake. You need to print the final answer without taking it modulo 10^9+7. The statement would be updated to reflect the change. Apologies for the inconvenience.
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 But what about the cheater the whole happiness of contest is gone this is all because of these cheater why don't codechef take strict action to stop these type of things. If these type of things happen in only 2.5 to 3 hours then think about the codechef long challenges
•  » » » 6 weeks ago, # ^ |   +117 What strict actions are you suggesting? Should we kill them?
•  » » » » 6 weeks ago, # ^ |   +1 We should make them listen to the 10 hour version of the nyan cat theme song
•  » » » » 6 weeks ago, # ^ |   +23 cheaters should be fired with AK-47.
•  » » » » 6 weeks ago, # ^ |   +3 You know better than me what you can do to stop these types things. Afterall you are my senior and have more experience than me.
•  » » » » 6 weeks ago, # ^ |   +3 How about codechef suspending their account...
•  » » » 6 weeks ago, # ^ |   +10 But what about the starving children in Africa? The comment you responed to has nothing to do with cheaters.
 » 6 weeks ago, # |   +7 Please do something about the cheaters I have left the contest in the mid, Just once type cookoff solutions on youtube or telegram there are many many solutions available. There is no such point in giving live contests on CodeChef as the ratings always drop. First, it was only in the long challenge but now it has started in the short contests as well. Please do something about it.
 » 6 weeks ago, # |   +8 How to solve Problem :Polynomial Roots https://www.codechef.com/COOK130B/problems/POLYRT. I tried to factorize the expression but didn't came with anything useful.If someone did please share his/her approach
•  » » 6 weeks ago, # ^ |   +25 I solved using WolframAlpha lol.
•  » » » 6 weeks ago, # ^ |   0 Legit OrZ!!
 » 6 weeks ago, # |   +7 Thanks For the Contest Easy Logicwise (I only saw 1st 3 ) but not that simple to code . My Accepted Code for TOOXOR was submitted in the last 5 seconds after 4 back to back attempts . This was for me a perfect fight till end example to remember . Kudos to Codechef Server and And Problem Setters (I wish I will be one of them in future )
•  » » 6 weeks ago, # ^ |   +4 I got AC in the last 3 mins after 12 wrong submissions :P.
•  » » » 6 weeks ago, # ^ |   +6 We were Lucky that the contest got extended by 15 min
 » 6 weeks ago, # |   0 When do Codechef ratings typically get released (like Codeforces ratings is ~4 hours post contest, what about Codechef)?
 » 6 weeks ago, # |   +5 I just saw that Too Much Xor has just 111 submissions but why this question is not included in div 1???
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 Too Much XOR is probably my favorite question I've attempted in the last month (aside from EGOI Day 2 P3).It was also in Div 3
•  » » » 6 weeks ago, # ^ |   +12 Thank you so much!
•  » » 6 weeks ago, # ^ |   0 If only 111 people managed to solve it, does anybody knows why my rank came out to be around 1300 [After solving WAV2 and TOOXOR].
•  » » » 6 weeks ago, # ^ |   0 Did you solved Binary String on Steroids BNSONSTR ??.In Codechef Each problem has equaL points and penalty is sum of all penalties of individual problem. Maybe that's why it is :(
 » 6 weeks ago, # |   +12 how to solve battle royale
 » 6 weeks ago, # | ← Rev. 2 →   +4 Wow.. well done..! As a participant, I just want to give my feedback and suggestions abt this contest. There should be something in the sample test cases to call them sample test cases. If all the examples are just trivial cases like for n=1 or n=2, there's no need to even include any example at all. The input output format is enough to understand what I need to do. Just one test file in the verdict.. How should I know if I'm failing on some edge case or the whole logic is wrong.. I don't even get to see the test cases after the contest is done. At least 2 test files will be highly appreciated. I don't like problems with a lot of corner cases :)
•  » » 6 weeks ago, # ^ |   +3 sample test cases provided by CodeChef are always very lame and sometimes they do not even explain them.
 » 6 weeks ago, # |   0 is there editorial of GRAND and CLAMPWAY? I have no idea besides centroid decomposition which takes O(nlog^2 n).
•  » » 6 weeks ago, # ^ |   +10 I as I know it will be.CLAMPWAY hint in short: build following tree — iterate vertices in ascending order, connect vertex to neighboring components whom contains neighbors with less id. And second tree but in descending order.Now clamp way in origin tree is ancestor-predecessor pair in both builded trees.
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   +13 CLAMPWAY:Consider that we're adding the vertices in increasing order of their value and we start "activating" them. Now when we activate some vertex $v$, we can notice that if it was the endpoint of a path (the max one), the min endpoint would've been in the connected component of $v$ (connected component in terms of activated vertices). This forms a tree structure (we can use union find to build it), such that $u$ is an ancestor $v$ iff when $u$ is the max endpoint, $v$ is a valid choice as a min endpoint.We'll do the same but in reverse — i.e. build another tree but by adding vertices in decreasing order of their value. Now the answer is the number of pairs of vertices $(u, v)$ such that $u$ is a root of $v$ in the first tree, and $v$ is a root of $u$ in the second one. This can be easily solved in $O(n \log n)$ with a fenwick tree + DFS.Update: Easily solvable part with fenwick + DFSCreate the DFS/Euler order over one of the trees. Now $u$ is an ancestor of $v$ iff $s(u) \leq s(v) \leq e(u)$, where $s(u)$ and $e(u)$ are respectively the start and end positions of $u$. Let's run a DFS in the second tree and maintain a fenwick tree. When we are at some node $u$, we first add the sum of the range $\langle s(u), e(u) \rangle$ in the fenwick tree to the answer and then we'll add +1 to $s(u)$. After that we run the DFS on the children and once we're done we subtract this +1. This way, the ancestry constraint for one of the trees is encoded using the fenwick, while we use the DFS for the other one.
•  » » » 6 weeks ago, # ^ |   +28 Not sure about "easily solved" part. I think it's nice even after the reduction.
•  » » » » 6 weeks ago, # ^ |   0 thanks for all!!! I'll try to upsolve it.
•  » » 6 weeks ago, # ^ | ← Rev. 5 →   +13 For GRAND the solution we had goes along these lines:There is a trivial $O(n^2 k)$ DP solution — dp[position][number of decreases] with $O(n)$ transitions per state. The first part is some case analysis of the transitions. If the state is dp[ $i$ ][ $c$ ], then we don't need transitions from some $j < i$ when: $a_j < a_i$ and there is some $p$ such that $j < p < i$ and $a_j < a_p < a_i$, because we can insert $p$ between $i$ and $j$. $a_j > a_i$ and there is some $p$ such that $j < p < i$ and ($a_j < a_p$ or $a_p < a_i$), because we can again insert $p$. Because the input is random, this gives us a $O(\log n)$ transitions per state and $O(n k \log n)$ solution. To remove the $k$ from the complexity, we need to notice that you don't need to maintain the whole DP table. Instead, we can just maintain a wide diagonal — for some $i$ we will only maintain dp[ $i$ ][ $c$ ] where $\frac{ik}{n} - B \leq c \leq \frac{ik}{n} + B$. It was enough to choose $B = 140$.
•  » » » 6 weeks ago, # ^ |   +20 Or, at least, among thousands of tests we generated, we never encountered a test where $B=140$ is not enough. Since codechef had a very small number of tests, $B=70$ is enough to get AC, I think. $B=300$ passes easily.
 » 6 weeks ago, # |   +23 Why the time limit in the problem "BNSONSTR" was 1 sec. It's not like O(n^2) solutions will pass if you keep it to 2 sec. Because of the strict time limit, I was getting tle using "#define int long long".