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:

Setters: Aryan Aryan_G Garg, Akshit akshitm16 Monga, Prasant prasant21 Kumar, Allen Zhang, Md Nadeem HelloWorld Shaikh, Vitaly Bugman Demidenko, Daanish Mahajan, Evgeny 74TrAkToR Karpovich

Tester & Editorialist: Taranpreet Discombobulated Singh

Statement Verifier: Jakub Xellos Safin

Contest Admin: Radoslav radoslav11 Dimitrov

Head Admin: Alex Um_nik Danilyuk

Video Editorialists: Chirayu Chirayu Jain, Prachi agarwal19 Agarwal, Darshan darshancool25 Lokhande, Yashodhan Molotov Agnihotri, Shivam Bohra, Radoslav radoslav11 Dimitrov, Aryan Agarwala, Meet mithh_gemphir Singh Gambhir, Rajarshi RestingRajarshi Basu

Mandarin Translator: Qingchuan UoA_ZQC Zhang

Russian Translator: Fedor Fedosik Korobeinikov

Bengali Translator: Sakib SakibAbrar Abrar

Vietnamese Translator: Team VNOI

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

As a problem setter ...

As a commentator...

As Tester and Editorialist ...

As another problem setter...

Pls do something about cheaters , Codechef contests are being ruined by cheaters ... And cheaters are rising in numbers rapidly :(

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.

+1

These Codechef short contests always clashes with my sleeping schedule.

You ruined your sleep schedule practicing spikes with KAGEYAMA :)

Codechef short contests always have a weird contest timing.

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?

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

You can only submit solutions in div3.

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

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.

Reminder — the contest starts in an hour.

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]

Please read the problem statement again. :)

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.

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

What strict actions are you suggesting? Should we kill them?

We should make them listen to the 10 hour version of the nyan cat theme song

cheaters should be fired with AK-47.

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.

How about codechef suspending their account...

But what about the starving children in Africa? The comment you responed to has nothing to do with cheaters.

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.

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

I solved using WolframAlpha lol.

Legit OrZ!!

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 )

I got AC in the last 3 mins after 12 wrong submissions :P.

We were Lucky that the contest got extended by 15 min

When do Codechef ratings typically get released (like Codeforces ratings is ~4 hours post contest, what about Codechef)?

I just saw that Too Much Xor has just 111 submissions but why this question is not included in div 1???

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

Thank you so much!

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

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 :(

how to solve battle royale

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 :)

sample test cases provided by CodeChef are always very lame and sometimes they do not even explain them.

is there editorial of GRAND and CLAMPWAY? I have no idea besides centroid decomposition which takes O(nlog^2 n).

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.

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.

Not sure about "easily solved" part. I think it's nice even after the reduction.

thanks for all!!! I'll try to upsolve it.

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

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.

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