We invite you to participate in CodeChef’s Starters144, this Wednesday, 24th July.

It will be rated for all and is my last contest as contest admin.

Time: 8:00 PM — 10:00 PM IST

Joining us on the problem setting panel are:

Setter: Satyam satyam343 Kumar Roy.

Text Editorialist: Nishank IceKnight1093 Suresh.

Statement Verifier: Kanhaiya notsoloud1 Mohan.

Contest Admin: Satyam satyam343 Kumar Roy.

**On the difficulty**

The Division 1 problemset features problems with **difficulties from div2A to div1E**. We expect the contest to be interesting enough for LGMs as well.

Written editorials will be available for all on discuss.codechef.com. Pro users can find the editorials directly on the problem pages after the contest. The video editorials of the problems will be available only to Pro users.

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. Hope to see you participating.

Good Luck!

finally satyam343 round

Counting is fun once again !

satyam343 Orz

try to make it more balanced. Last few contests there is huge gap between the difficulty level of 2nd and 3rd question.

OMG ORZ satyam343 I AM YOUR BIGGEST FAN

He is blue

satyam343 orz

Yayy!! rated for all :)

Orz satyam343

Hey, for the sake of humanity, please stop providing solutions to the cheaters.

satyam343 orz

As a div1 participant, why am i restricted from the contest?

Remainder: Contest starts in less than 60 minutes.

MINIMISEINV is a repeated problem from codechef,if you google the problem statement ,you will reach the editorial here . What's even more funny and shocking is that satyam343 tested this problem and provided the solution as seen in the editorial page.

Nice last contest.

this question unrated then?

Bruh,

The contest should definitely be unrated then.

It is indeed funny, I did not remember it.

`Nice last contest.`

. Just to be clear it was my last contest on CodeChef (:Counting would no more be fun (╥﹏╥)

Previous problem needs O(n) time complexity but today's problem intended solution is O(n*k). So easier and harder version of same problem based on constraints.

//

that's $$$O(n^3)$$$ as $$$n * ones * (n - ones)$$$ is of the order $$$n^3$$$

in minimum inversion problem why it's not optimal to make some prefix $$$000...$$$ and suffix $$$...111$$$

It is optimal, you just have to determine how long of a prefix to set to $$$000...$$$ and how long of a suffix to set to $$$111...$$$. You can do this by brute forcing it in $$$O(n^2)$$$.

i tried both $$$O(n)$$$ and $$$O(n^2)$$$ both gave WA2 is there any edge case?

in the problem

Minimise Inversions, I did remove the leading zeros and trailing onesthen count the number of 0's and 1's in the remaining string

if the number of 0's is greater than 1's, then I will flip the first

Koneselse, I will flip the last

Kzerosdoes anyone have a test case which my approach doesn't work with it ?

I made this approach, but gives me WA on test 2 :(

"interesting enough for LGMs as well" should not mean there is a tedious problem and the contest duration is too short, I suppose.

I'm so poor to able to read only 4 problems, sorry. CNTISFN343 is nice though, thanks!

`there is a tedious problem`

I assume you are referring to TREESAREFUN.

I used euler tour to count the number of intersecting pairs. I really liked the idea. So I discussed it with one of the testers. He liked it too.

I didn't find the implementation tedious, although it is a bit tricky. The tester had a similar implementation, so I didn't get the impression that it's a tedious problem.

Here is my implementation for reference.

I thought BANGER was pretty nice too. That is why I thought the contest should be interesting for LGMs.

I should have kept the contest to be of 150 minutes though.

Glad that you liked CNTISFN343.

Can you describe the solution for problem BANGER?

All editorials of CodeChef can be found at https://discuss.codechef.com/c/editorial/5. This is totally free of charge. The only part that is premium is the fact they appear directly on the problem page.

Let us see how to find $$$Score(b)$$$ quickly.

We can see that optimal $$$c$$$ should be $$$[1, 1, \ldots 1, 2, 3, \ldots k]$$$.

Now there should an index $$$i$$$ such that $$$c_i = b_i$$$. Otherwise $$$[1, 1, \ldots 1, 2, 3, \ldots k+1]$$$ could have been a valid $$$c$$$ too. Now it is clear that we only care the largest index $$$i$$$ such that $$$c_i = b_i$$$. So the number of distinct elements in this case is $$$b_i + m - i$$$.

This leads us to the observation that $$$Score(b) = m - \max(0, \max_{i=1}^{|b|} i-b_i)$$$.

Now we have to solve original problem.

Let us just have an array $$$d$$$ such that $$$d_i = \max(0, i-a_i)$$$.

Suppose $$$l_i = \max_{p=1}^{i} d_i$$$.

Now if $$$Score(a[j,i])$$$ is.

1. $$$i-j+1$$$ if $$$l_i < j$$$.

2. $$$i-l_i$$$ if $$$l_i \ge j_i$$$.

$$$l_{i+1} = \max(l_i,d_{i+1})$$$.

So we can see that we just care about how array $$$l$$$ looks after each update.

Let's divide the array $$$d$$$ into $$$sqrt(n)$$$ blocks.

Say we are in some block, and it covers indices from $$$x$$$ to $$$y$$$. After the update, either $$$l_i$$$ $$$x \le i \le y$$$, will be changed to $$$l_{x-1}$$$, other there will be an index $$$z$$$ such that all $$$l_i$$$ $$$x \le i \le z$$$ will be changed to $$$l_{x-1}$$$, and subarray $$$l[z+1,y]$$$ will be unchanged.

So we can update the answer for each block in $$$O(t)$$$, where $$$O(t)$$$ is the time taken to find the smallest index $$$v$$$ greater than $$$x-1$$$ such that $$$d_v > l_{x-1}$$$. In editorial mentioned above, editorialist described the $$$O(logn)$$$ way to find $$$v$$$.

It is possible to find $$$v$$$ in $$$O(1)$$$. It is possible to have a ds which supports update in $$$O(sqrtn)$$$ and query in $$$O(1)$$$.

Now only one thing is left.

How to find $$$\sum_{i=x}^{z} \sum_{j=1}^{i} Score(a[j,i])$$$, given that $$$l_x = l_{x+1} \ldots l_y$$$. It can be found in $$$O(1)$$$.

Here is my $$$O(n sqrt(n))$$$ implementation for reference.

Thanks for the comment. Yes, about TREESAREFUN for me.

The word "tedious" might not for suitable for what I meant, sorry, but I meant the total work needed for AC instead of the final code length. Maybe I should have said just time-consuming (comparing with the time to feel it is solvable in $$$O(N \cdot \mathrm{poly}(\log(N)))$$$ time). I finished implementing and I guess mine is not too far from yours.

Most importantly, the solution involves some amount of case work (right?) while the sample output is essentially $$$0,0,0,1$$$, so we normally have a tough debugging time.

Having weak samples is an option but in that way I guess 150 minutes were just about right for the first 6 problems (considering the speed of today's top participants).

after how much time rank gets updated?

How to solve Largest K if it was of subsegment instead of subsequence.

Why my strategy for MINIMISEINV is wrong.

I am trying to calcuate flipping which number will most optimal each time (by checking the delta for each char).

CodeHow to solve "minimum inversion" problem if it is mentioned

exactly kflip need to be done?We do exactly k flips only in cases where our suffix array is constant(from n-1 to 1) and same when our prefix array is increasing ,so I think we can maintain another array temp to store indices where increment occurs according to same logic as at most k and just count and if index<k then return 0.

getting wrong answer in Minimise Inversions code why getting wrong answer