We invite you to participate in CodeChef’s September Lunchtime, this Saturday, 26th September, from 2000 hrs to 2300 hrs IST.

**Please Note — Unusual starting time. The Contest will begin at 2000 hrs instead of 1930hrs**

The contest will feature 5 problems for 3 hours. I am author of all problems. I hope you will like them.

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.

Joining me on the problem setting panel are:

- Tester: Alexander scanhex Morozov
- Statement Verifier: Jakub Xellos Safin
- Editorialist: Colin galen_colin Galen
- Admin: Ildar 300iq Gainullin
- Mandarin Translator: Gedi stzgd Zheng
- Vietnamese Translator: Team VNOI
- Russian Translator: Fedor Fedosik Korobeinikov
- Bengali Translator: Mohammad solaimanope Solaiman
- Hindi Translator: Akash Shrivastava

**Prizes:** The top 10 Indian and top 10 Global school students from ranklist will receive certificates and CodeChef laddus, with which they can claim cool CodeChef goodies. Know more here.

Good luck and have fun!

I am author of all problems.Hmm. The chances of getting a balanced problemset have increased exponentially.

Ad-hoc problems incoming....

Well, I am starting codechef

I honestly think that somebody should tag the GMs and above here, because the expected quality of the contest is pretty damn high, and most people think the contrary!

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

Yes the dignity of codechef will return.

No mention of divisions , will there be same problems in both divisions?

Two Divisions with intersection of 3 problems

would not miss this for the world!!!!

Please move the codechef discussion to codeforces as atcoder does, if possible.

what codechef lacks is community and quality of discussion, 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.

What do u mean stackoverflow, there is downvote system on stackoverflow.and you cannot even comment if u don't have atleast 50 reputation points.

But there should be downvote system, so people won't ask most famous question,"how to begin with cp, or please debug my code"

I said "supposed to be like stackoverflow". I never said it is. XD

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.

Absolutely right

But is that the right thing to do? People must learn at some point that first they should try to search on the internet if someone has already asked the same thing.

That's the right attitude. Quora and stackoverflow both show similar questions(previously asked) to keep users from asking redundant questions. That's why these forums are relatively clean and organized.

But in codechef you will find the same kind of questions asked countless times.

Beginners must first try to debug on their own. But most people come directly and paste their codes and start asking others to debug for them. Codeforces teaches them the right thing to do by downvotes.

Genuine doubts are answered in codeforces whether it was asked by a beginner or a LGM.

Are you planning to write more Codechef contests? If yes, I would take part in Div.2 this time and get enough ratings for future Div.1 contests.

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)

Can you edit your comment and add profile links again, please?

I feel like Codechef is changing for better, with 300iq and Ashishgup in the team :)

Reminder 1 — Contest starts in less than 3 hours.

Reminder 2 — Contest starts in 30 minutes.

In addition to the textual editorials, the hardest 3 problems of Div-1 will be discussed in live sessions on YouTube — 11:30 pm IST today, and at 11pm IST on 27th and 28th. The easiest 4 problems will have pre-recorded video editorials. All the 7 video editorials will be added to this playlist.

How to solve PERMSPL:

I had a fairly clean argument for it although I didn't understand

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

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

After this contest I confirm that I am not constructive!

that was an amazing problemset :)

Great contest, a lot of thinking!

I overcomplicated PERMSPL and ADDONSEG a lot. I solved the former with some randomized solution (trying to get some split for every difference) and I didn't get the ifs right for ADDONSEG even for a subtask. My screencast & commentary https://youtu.be/R9AJxwWptQY

As a video editorialist I enjoyed solving Anton's problems!