Hello, Codeforces!

I invite you to participate in Codeforces Round 876 (Div. 2), which will be held on Jun/03/2023 17:35 (Moscow time).

The round will be rated for participants with rating lower than 2100. Participants with higher rating can participate in round unofficially.

You will be given 5 problems and 2 hours to solve them. I recommend you to read all problems. One of the problems will be interactive, so please read guide for interactive problems before the contest.

All problems are authored by me.

I would like to thank:

- Renatyss for helping with preparation and discussing the problems.
- IgorI for great round coordination.
- bashkort, Allvik06, Ormlis, satyam343, maomao90, Dominater069, Yuu, Kirill020708, asafiul, iliya_mon, sdyakonov, tallbee23, Asgat, AquaMoon for testing the round and providing useful feedback.
- MikeMirzayanov for Codeforces and Polygon platforms.

Score distribution: 500 — 1000 — 1500 — 2250 — 2750.

Good luck to all participants!

Editorial has been published.

Winners:

Unofficial winners:

First-to-solve:

- A. M_bolshakov — 0:01.
- B. Never_Lose — 0:05.
- C. SSRS_ — 0:10.
- D. BucketPotato — 0:18.
- E. BeyondHeaven — 0:22.

Auto comment: topic has been updated by valerikk (previous revision, new revision, compare).finally a healthier contest than me

As a tester, I really loved the problems! Don't miss an opportunity to take part in a contest written by the IOI 2023 Winner ;)

As a participant, I will participate. Hoping for great problems.

code force

bashkort asafiul orz!!

hopefully +delta

5 problems round after a long time, will enjoy this round!

as a tester, the problems were great. Recommend participating.

As a participant, May my feeble mortal senses endure the eldritch revelations that await, as I delve deeper into the abyss of understanding.

Good luck to everyone participating!!! Also on a random note, what song have you been listening to lately?

Link listening to this while giving contests is really helping me to focus.

Link I prefer this one.

link Just enjoy

Link

I enjoy contests which have only 5 problems with no subtasks

As a tester, ahmet23 orz!..

Dominater069 orz

As a purple tester, round is very good!)

Thanks Codeforces for another contest!

As a tester orz

Codeforces contests help me overcome the exams period.

As not a tester, i didn't tested.

Yes Sir.

No Sir.

Ok Sir.

I hope standard problem in this round !

Hope to reach specialist again

Best of luck brother. As a beginner my first goal is to reach Pupil

best of luck bro

Yuu Orz

yeah!! the interactive problems are fun to solve.

How to unregister for a contest ?

you will find a cross symbol beside your name

My first unrated Div 2! Excited!

hopefully reach cyan

orz sir

As a cyan,Hopefully reach expert!

Thanks Codeforces

Good luck to all participants. Wishing you a positive delta!

Waiting....

Score distribution when?

I don't know when will be my "Promotion to CM" round!!

As a participant, Hoping for a great round.

Hope no adhoc forces

Ormlis Orz

Score distribution gives speedforces vibes.

Really Hope the interactive problem Is D or E

Its been long time since we encountered Good Binary Search problem. Hoping to get one.

As a participant, I will participate and try the best for great problems today.

As a participant, I will participate. Hoping for great problems.

not one programming problem in sight. all stupid adhocs.

Rank 400 and Rank 2500 both solved same number of problem:)Problem D:

should be

That's

PLEASE FOR THE LOVE OF GOD STOP SPEEDFORCES!

MAKE ACTUAL CONTESTS!!

Nobody makes speedforces contests intentionally.

From the score distribution it looks like it was intended.

Time limit for B was very strict... Am I the only one who had troubles with TL in B?

If you sort the array and then transverse it properly, I do not think you should have TL issues in B. What have you tried?

I did that. But then I was counting number of already seen types with map. I should have used a cnt vector, which in fact passed. I mean, just by changing map to vector it passed. Maybe with TL = 2s there would be no issue at all

I believe you just need to select, for each distinct a_i, the a_i lamps with higher b_i, since all lamps with lower a_i will break before the a_i lamps break. This can be done in a single loop. (since we are sorting asc by a_i, then desc by b_i)

(my submissions was worse than that, I was keeping track of how many X lamps were currently on. As long as you save, along a_i,b_i, another field to identify you have turned on the ith lamp. And then using another iterator variable, to check each breaking lamp, and decrease from X if it was turned on)

Failed test 5. So sad :(

Is it possible to solve B using priority queue by pushing pair<index, pair<a , b> > into it in an ascending order . Any ideas ??

Maybe, but you don't really need to make it that complicated,better to use the simple solution

A: For each 0<=i<=n, there are at least ceil(i/k) ones on the prefix with length i, and ceil((n-i)/k) ones on the corresponding suffix, therefore ans>=ceil(i/k)+ceil((n-i)/k). We can solve the problem by brute force for 0<=i<=n.

B: Let's denote S[k]={1<=i<=n: a[i]==k}. For each integer k, we can get points from at most k lamps in S[k], because all lamps in S[k] will break simultaneously, and there we can turn on no more than k lamps in S[k] before they break. So we can classify lamps by a[i], and choose min(k,S[k].size()) lamps with maximum b[i], then we can get an upper bound of the answer. In fact, this answer is also a lower bound: If we turn on the chosen lamps by the non-decreasing order of a[i], because lamps with lower a[i] will break strictly before lamps with higher a[i], they will not make lamps with higher a[i] break before turned on, so we can get points from all chosen lamps. Therefore we can solve the problem in O(n).

C: By induction we can prove that the last element of a is 0.

ProofAfter the first operation, a={0}. Assume after the (i-1)-th operation, a[i-1]=0. Then in the i-th operation, if we choose p=i-1, then we will insert 0 at the back of the array, so a[i]=0. If p<i-1, then we will insert 0 before a[i-1], and it will not be flipped, so a[i-1] will become a[i] in the new array, therefore a[i]=0 after the operation.

So if b[n]=1, there's no solution. Otherwise we can construct a solution: First we let ans be an empty list. Then we read b[i] reversely: Let i be the largest index such that b[i]=1 and b[i+1]=0, we can assume there's an operation with p=i+1, so we append i+1 to ans and filp elements on [1, i]. If there's no such i, we end this process, append zeros to make ans.size()==n and reverse it as the answer.

D: Let [L1, R1], [L2, R2], ..., [Lm, Rm] be the ranges of indexes which has been moved in operations, then other indexes must form an increasing subsequence, and we must add a 0-ball in each [Li, Ri]. Therefore, we can solve an another problem: We can remove at most k subarrays from c[i] to make it increasing, minimize the number of elements removed. We can solve this problem by naive O(n^3) dp.

E: For any subset of {1, 2, ..., n}, we denote it S1 and it's complement S2, if sum(i in S1)(a[i])=sum(i in S2)(a[i]), then the second player can win the game: If the first player choose i in S1, the second player choose j in S2, and vice versa. We can see by this strategy sum(S1) will always be equal to sum(S2), so the first player has valid move in S1 --> sum(S1)>0 --> sum(S2)>0 --> the second player has valid move in S2. Therefore, the second always has valid move before the first player lose the game. If there're no such S1 with this property, the first player will always win: Assume for all subset S1 we have sum(S1)!=sum(S2) before a turn, and assume indexes chosen in this turn are i, j, WLOG assume a[i]>=a[j]. Then if there sum(S1)==sum(S2) after this turn, if i belong to S1, then we can assume j belong to S2(because a[i]>=a[j] before this turn, we have a[j]==0 after this turn, so move it from S1 to S2 will not change sum(S1)-sum(S2)), then we have sum(S1)==sum(S2) before this turn, which is a contradiction, so for all subset S1 we have sum(S1)!=sum(S2) after this turn. If the first player lose the game, when there's 2 positive elements in a[i], assume they are i1, i2, then we have a[i1]==a[i2] so that first player has no valid move in next turn. But in this case if we let S1={i1} then sum(S1)==a[i1]==a[i2]==sum(S2), which is a contradiction, so the first will always win the game.

My solution for A is: ((n-2) / k) + 2.

Can you please explain the reason, like how you came to this conclusion?

you will always need an element at the first and last position after that you can divide the inner n-2 elements into partitions of size k and insert an element in each and you should always have an answer.

This helps, thanks a lot!

Very fast editorial...

I liked problem $$$D$$$. First, its obvious that the sequence of colors of those non-zero color balls on which we don't perform an operation must be an increasing sequence. After that its $$$O(n^3)$$$ dp.

I could see that we only have to perform operations on elements not present in the increasing subsequence, how did you minimize it using dp tho?

Just see the general structure of a solution. If $$$X$$$ denotes the non zero color element on which I perform operation and $$$Y$$$ denotes the non zero color element on which I don't perform operation, then if my non-zero array of balls looks like this,

$$$XXXYYXXYYYXXY$$$

Then, I can insert a single zero color ball on every segment of $$$X$$$. (Here I require at least $$$3$$$ zero color balls and cost is $$$7$$$ units because I'm moving $$$7$$$ non zero color balls). Also another constraint is that sequence of $$$Y$$$ must form an increasing color sequence. So, that's why we can define $$$dp[i][j]$$$ as the min cost required such that there are exactly $$$j$$$ segments of $$$X$$$ (so at least $$$j$$$ balls of zero color required) and an operation is performed over the $$$i^{th}$$$ non zero color ball.

Transitions:

$$$dp[i][j] = min(dp[i][j],dp[w][j-1] + i-w-1) \forall w < i-1 $$$ and $$$c[w] < c[i]$$$

That's because if I'm performing operation on $$$i^{th}$$$ non zero color element, then the last element $$$w$$$ on which I perform operation, its color must be less than $$$c[i]$$$ also, since $$$w<i-1$$$ there is a segment of non zero length which requires a ball of zero color to be placed inside it.

$$$dp[i][j] = min(dp[i][j],dp[i-1][j])$$$ if $$$c[i-1] \le c[i] $$$ This case is trivial.

Hi Shivansh ShivanshJ Jaiswal,

what to do when we have multiple LIS ?

Can you please see the below comment and give your insights ?

https://mirror.codeforces.com/blog/entry/116963?#comment-1034277

OMG i solved the last problem of the round for the first time

what's funny is that i was writing the code like "ok i obviously wont finish in time, right"

Never give up!!! great round, although really speedforcish, luckily not for me

Amazing! Yeah it was speedforces till problem A, B, C. From D onwards the problems were nice.

Cool problems! Really, for me, A, B, C are tasks where you have to think instead of looking at the tests and finding a correlation, like in the previous recent rounds.

how to do C?

Read B for a long time, more than half of the time thought ai is three states, ha ha ha ha

ADHOCforces

HELP in Problem CI was able to recognize that if last element was "1", then it was impossible thus "NO" is the ans. But was not able to get "b" array. Please guide.Try doing it backwards. Start from array b and reach empty array by only deleting 0 and flip

You are correct. Now assuming that A, is basically a series of one '0', each followed by zero or more '1's, when scanned from right to left, try to handle each group of '0' led by zero or more '1's seperately (from right to left).

It is obvious that b can not have 1 in the end so answer for that is "NO" otherwise "YES". => Break the Array in the form of 1..10..0. Solve for each part.

You try to make the array from the back eg

`1 1 0`

so try to form from the back. first, we insert at the 0th index`(0)`

then again at the 0th index`(00)`

now at the 2nd index`(110)`

. if we have all zeros then we add every 0 at 0 index. What happens when we have consecutive 1's like k ones Eg:-`(1 1 1 1 1 0)`

we have 5 ones here we can first add 0 at 0th index`(0)`

and for 5 ones we add 4 zeros at 0th index`(0 0 0 0 0)`

now to form consecutive 1's add 0 at 4th index (1 1 1 1 1 0)`In short we traverse from the back, if we have 0 then we print 0 if we have k consecutive ones we print k — 1 0's and 1 k.

My Solution

what's the point of setting the memory limit for problem D to 256MB ?!

seg tree

The description of question A is not very clear, especially in the selection condition, the sample is not mentioned. It is the same as not. I hope the meaning of this kind of question can be clear in the future

Cant Pass PreTest 1 then comment??

Maybe because my mother tongue is not English, I did not understand question A, but I have AC questions B and C

imo E is easier than D but I just need one more minute so submit it...

Can someone explain to me how D is solved by $$$O(n^3)$$$ dp? I know that the non-zero color balls which we don't perform an operation form an increasing sequence, but I never thought about $$$O(n^3)$$$ dp.

Also, maybe someone can give me a little E idea?

a little idea for E — notice that after the end of the game each a[i] can be represented as (a[i1]-(a[i2]-a[i3]-...-a[ik])), and second player wins when after the game the sum of all a[i]=0, so if we write each a[i] as above the sum of all things must be 0

Thanks! It's very helpful!

You're welcome!

You can view my comment here: https://mirror.codeforces.com/blog/entry/116898#comment-1034203 (for problem D dp explaination)

:)

OK, thanks!

Why my O(n^3) dp solution for problem D got TLE? 208344465

`n + 5 > MAXN`

Thank you! That's was so bad.

In test 4 $$$n = 500$$$

In the first loop uses $$$n + 5 = 505$$$, which is greater than $$$MAXN = 502$$$

Sorry for my poor English

I already got an answer, but anyway thank you!

Although my solution of E is wrong, why did I get penalties because I got WA/RE on pretest 2 which's a sample?

Here's one of my submissions. This code can pass the samples locally, so is there something wrong with the verdict?

Sadly, you don't get penalty only on pretest 1. Even if there are many of them.

My O(nlogn) Python solution for problem B gave me TL. Could someone help me identify how I could have made it pass?

Use fast I/O:

https://mirror.codeforces.com/contest/1839/submission/208349299

Runs in 265ms

Oh, never thought about it. Thanks a ton!

It ran in 639ms with Python3 (no idea why)

One thing I don't "like" is the "A[a].append(b)", since it causes reallocation of the array. I do not think this is really significant in this scenario, though.

Thanks for sharing the Python3 runtime.

I too think that list append should not consume significant time.

Why I got RTE on Main Test 5? 208322908 Can anyone please explain? I can't find the error.

While making a comparator make sure there is no

`=`

operator in it.WOW! Thanks for the insight.

My feedback: a round is susually concidered unbalanced when you can get 2300 performance while only solving ABCD. This round, you could get 2300 performance for solving ABC.

When will the Editorial for contest will be released ?

Not able to solve D, waiting for the approach in editorial.

Thank you for rejudging my submission for QD multiple times :)

I got a bunch of TLEs and then finally ACed with 1965ms :)))))

(BTW, is it my problem or is my solution not intended? The time limit seems a bit strict for O(n^3))

Congrats on your awesome 1st place finish!

Although the first 4 problems are not fun to solve... but problem E is beautiful!

I'm really happy with how I did in this contest, but I honestly had no idea that an O(N^3) solution for D would pass. I've been using C++ and Python interchangeably, but I guess I've been using Python for too long if I thought that would be too slow :)

Thanks to the writer and testers.

I like the tasks but half of problem D was figuring out what the statement is trying to say

Can any one please help during contest on second question submission it is showing error

exit code: -1073741819 (STATUS_ACCESS_VIOLATION), checker exit code: 0, verdict: RUNTIME_ERRORYour text to link here... please helpe??

Never use a

`=`

in your comparator for some reason it gives segmentation fault.Enjoyed all the problems.

Ratings updated preliminary, it will be recalculated after removing the cheaters.

from collections import defaultdict from collections import Counter from itertools import combinations from itertools import permutations import heapq import math import bisect

def presum(arr): d = [] sum1 = 0 n = len(arr) for i in range(0,n): sum1 += arr[i] d.append(sum1)

def factorial(mod):

def lst1(): return list(map(int,input().split()))

def map1(): return map(int,input().split())

def int1(): return int(input())

t = int1()

while t!=0:

B)Lamps I solved this in the contest in PyPy 3 interpreter which is supposed to be faster than Python 3.8 interpreter and after the contest was over i just changed the interpreter to Python 3.8 and It was Accepted . This Solution gave Time Limited Exceeded on testcase 3 on PyPy 3 and Accepted Verdit on Python 3.8 . I Cant Understand why this happened but my solution was correct during the contest

For dictionaries sometimes PyPy may be slower:

https://doc.pypy.org/en/latest/cpython_differences.html#performance-differences

Amazing contest. Problems were excellent. Thanks for the round valerikk

https://www.youtube.com/watch?v=u9QHyBszuq8

isn't the 6th example in the A wrong?

Why do you think it is wrong? $$$[1,0,0,0,1,0,0,0,1]$$$ is good, you can't use less ones than that.

i/k = 5/5 = 1 != 2 Or i didn't understand the problem '_'

the question said that

at-least[i/k] elements should be 1 in the first i elements and in the last i elements.Why doesn't this round have 12 hours hacking phase, or am I misunderstanding something?

That is only for educational/div3 or 4 rounds.

My solution gave TLE on Test Case 3 on Pypy 3 interpreter during the contest and gave the Accepted Verdict on Python 3.8 when I upsolved the contest.I didnt even change a single word when sumbitting on Pyth3.8 Pls tell me the issue

Use FastIO for fast input-output.

Thanks! Loved E a lot!

A good round with a fast editorial. Great work!

C was fun. Good problems. Enjoyed it

Problem D be like :

... so the ball is a male

Matt Walsh in shambles

I was unable to solve even a single problem. Even in other division 2 contest I could only solve 1 question. Please help me, how do I improve.

The presets in B are weakly designed, can't even catch a simple runtime.

Can someone please explain why this submission gives RE on test 5 of problem B? I looked at some previous comments and this happened when they used "=" sign in comparator, but I have not done that also.

As a participant I thought this set of questions was really good, but it was too difficult for me to translate the questions

Thank you to everyone who helped with this round! I found C, D, and E all very enjoyable (maybe E is a bit easier than normal but that is not necessarily a bad thing in my opinion, since it's not easy enough to decrease the fun i had :P )

"Attention!

Your solution 208345312 for the problem 1839C significantly coincides with solutions ..." and after that there were the names of thousand other id's the problem was trivial and others may have thought in the same manner please consider my standings in this round. plz @MikeMirzayanov

emm,I am told that the solution conflicts with others, in what way should I prove that this is a coincidence?

"Your solution 208343807 for the problem 1839E significantly coincides with solutions ...",I think for this problem,the only thing that can be different is the design of the dp state.Please consider mu standing in this round.plz MikeMirzayanov

this blog plz https://blog.csdn.net/chen134225/article/details/82463078

MikeMirzayanov IgorL Renatyss Few minutes back I received a mail and message regarding similarity between my code for the problem C of this contest... and there is a huge list of people in the mail... and basically i have used my own template and way of solving and writing the code.... and the approach is to solve from end of the vector in reverse way..... Using i,j,k,ans,v as variable/ function names is common in programming... so that part is gonna coincide with most of the people in coding domain. logic for the problem is quite straightforward so that is most likely going to be similar... and things i have used from my template... Neither I have taken the code, nor given to anyone and i coded it on my offline Sublime compiler only... so please do justice and reward me for the problems i had solved ( and please don't punish me for an offence that i have not committed) My submission: 208340229 Please help me out!!

Received a mail that my solution for submission 208345585 RajAdwaita 1839C - Insert Zero and Invert Prefix matches other people's submission, would like to inform you that I had written the code by myself and used a boilerplate template, kindly requesting you look into the matter. I have worked out the problem, and have no idea how this solution is similar to someone else's. The other submissions do look different, thus I request a re-evaluation of this code base.

I am writing this comment to inform you that I got a mail from codeforces regarding similarity of my submission (https://mirror.codeforces.com/contest/1839/submission/208340133). But as you can see in the solution, the code that is similar to other solutions is not even used in the main code(in the actual logic). Actual logic uses completely different approach. Please look into the matter and do the needful as soon as possible.

hello

Dear @MikeMirzayanov, I am writing this to tell you that recently I received a mail stating that my submission 208342344 is matching with submissions of others. I use my own template for writing code and my logic derived is almost similar to the editorial posted it is only the matter of fact that some of my steps are matching with other codes, other than that there is no common part . I request you to please rejudge my submission and give my ratings back.

MikeMirzayanov valerikk I just received a notification that my submissions 208343510 & 208343216 coincide with other's submissions, and are displayed to be skipped,

but along with them my other submission 208331417 has also been skipped and it doesn't even coincide with anyone. Please unflag this submission.And also, there were the names of thousands of other IDs followed by it, the problem was trivial, and others may have thought in the same manner please consider my standings in this round.Dear MikeMirzayanov I recieved a mail regarding my solution for 1839C - Вставить ноль и инвертировать префикс which is 208330178 , is similar to some other people . I sincerely request to please reconsider , as I made the intuition and solution completely myself on pen and paper . The Xor trick in this question is something I was very happy to crack and once u get the intuition , the code was quite simple . I have been doing codeforces for quite a long time , I enjoy giving more and more contests and this is definetly a mere coincidence and the problem code was quite straight forward. Also u can see my previous submissions to many problems , it can clearly been seen that it is my my own code with similar intuition to others. Please dont skip my solutions as my happiness was at peak solving the 3rd question in this contest.

Dear MikeMirzayanov , I am writing this to tell you that recently I received a mail stating that my submission for 1839C - Insert Zero and Invert Prefix which is 208345137 is matching with submissions of others.

I want to let you know that my code snippet is the same as of previous submissions and also the logic behind question C is purely intuitive and I got it after a wrong submission. I opened codeforces today but got shocked to see the rating changes. I also read the message which says that it is matching with some other solution. If my submissions are skipped then how can I be in the standings, MikeMirzayanov Please check it.