Yo Um_nik, I've a feeling that you'll really like this round!

Two Divisions with intersection of 3 problems

codechef discussion page just looks like spam.

That is the way the cc admins decided it to be. It was supposed to be like a stackoverflow for cp.Thats why people can freely ask whatever newbie level problem they want to ask. Thats why it doesn't have downvote system.

According to me, codechef discussion forum is one of the best, where people at least don't do partiality and don't just downvote without even reading the post, like here in codeforces. It's just like- If you are Newbie on cf -"You don't have right to ask questions here, it is only meant for high rated coders, who ask meaningful questions".
A simple doubt here by some beginner gets downvoted. Even doubts remain unanswered for days or weeks. At least on codechef, someone is always there who answers doubts, however basic it may be or at least provide the resources to study.

Idk why mike wants to spoil all the fun.

Btw Anton said he authored cc contest because he wanted to boost his friend's career. Lets hope his friend has a lot of geniosity friends who would like to boost his career.

P.S. — You will need two rated contest for div 1 rating.

I am afraid I am not planning to write more Codechef contests in the nearest future, but I would still encourage you to join. I feel like Codechef is changing for better, with 300iq and Ashishgup in the team :) (Not mentioning the rest)

Reminder 2 — Contest starts in 30 minutes.

I had a fairly clean argument for it although I didn't understand why the equivalent condition works in the end:

Build a graph, let $$$w_{uv}=1$$$ if $$$P_u > P_v$$$ else 0.

Let $$$a_u \in [0,1]$$$ be the assignment of index $$$u$$$.

Want assignment such that $$$\sum w_{uv}(1-a_u)(1-a_v) - \sum w_{uv} a_u a_v = 0$$$.

This simplifies to: $$$\sum w_{uv}(1-a_u) = \sum w_{uv}(a_v)$$$.

Which is equivalent to whether there is a partitioning where the sum of outdegrees in each partition is equal, which is easily done with knapsack.

Exactly my story as well.

I used this idea in contest. Consider two subsequences $$$A$$$ and $$$B$$$ that form $$$p$$$. Then there are three types of inversions in the original array:

• Inversions between elements in $$$A$$$
• Inversions between elements in $$$B$$$
• Inversions between an element in $$$A$$$ and an element in $$$B$$$.

Let the number of inversions of the first kind, second kind, and third kind be $$$x, y, z$$$. We want to find $$$A, B$$$ such that $$$x = y$$$, or $$$x+z = y+z$$$, or $$$2(x+z)=2(y+z)$$$. Note that the left side is simply twice the number of inversions in the original array that use an element in $$$A$$$, and the right side is twice the number of inversions using an element in $$$B$$$. Let's design a new array $$$x[i]$$$ such that $$$x[i]$$$ is the number of inversions $$$p[i]$$$ is involved in. Then $$$2(x+z)$$$ is the sum of $$$x[i]$$$ for all elements in $$$A$$$, and $$$2(y+z)$$$ is the sum of $$$x[i]$$$ for elements in $$$B$$$. We can easily compute $$$x[i]$$$. Thus we want to split $$$x[i]$$$ into to parts with equal sum. We can do this with knapsack DP in $$$\mathcal O(n^3)$$$. Note that this also gives us a way to recover how to split the array.

Submission link