As Tester and Editorialist ...

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.

You ruined your sleep schedule practicing spikes with KAGEYAMA :)

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

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

Please read the problem statement again. :)

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

I solved using WolframAlpha lol.

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

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

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

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

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:

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