Hello, Codeforces!

I am happy to invite you to my Codeforces Round #830 (Div. 2) which will be held at Oct/23/2022 13:05 (Moscow time). **The round will be rated for all the participants with rating strictly less than 2100 before ** Oct/23/2022 10:50 (Moscow time).

The tasks were created and prepared by 74TrAkToR. I would like to thank everyone who helped me a lot with round preparation.

- Coordinator Artyom123 for excellent communication and help with preparation.
- Testers gisp_zjz, Pointy, q-w-q-w-q, feecIe6418, nnv-nick, xiaoziya, Ormlis, huangzirui, Chenyu_Qiu, triple__a, gyh20, low_, voventa, tibinyte, Mr.Robot_28, Qingyu, RUSH_D_CAT, physics0523, Lucina, Rhodoks, Tekor, Milesian, Kalashnikov, Lokeo, mejiamejia, TomiokapEace, Chenyu_Qiu, AquaMoon, flowerletter for high-quality testing and valuable advices.
- As well as the testers who tested the CheReKOSH Team Olympiad — it was from the problems of this Olympiad that the round was composed: orz, DIvanCode, CAMOBAP31.
- MikeMirzayanov for amazing Codeforces and Polygon platforms.

During the round you will need to solve **5 problems, some of which have subtasks**. You will have **2 hours** to solve them.

Score distribution will be announced shortly before the round.

We wish you good luck and high rating!

**UPD:** Score distribution: $$$750-750-(1000-1000)-(1250-1250)-3000$$$

**UPD**: Editorial

Sleepforces

Orz to gyh20 for testing twice :O

Instead of writing your shit on every post , you can consider practice more. Asses everywhere.

Says a newbie

Not a noobie kiddo, have you heard of ALT??

ALTs are prohibited by the codeforces rules

Don't be so ignorant. He actually has a maximal rating of a whopping 1069 on his alt!

So your first comment on codeforces is aimed at trying to roast me (which failed horribly)? Too bad.

No need to roast someone with contribution <0 . Just reminding not to shit everywhere.

Says a person who ranks last place with an "ALT"

This one's is special, aimed at getting rating<0 ;) And one more thing, you should practice some good problems, 400 is a big number for pupil lol .

Trying so hard to solve a problem, eh?

SpoilerHaha.. Good one! haiender288

Yeah I am practicing good problems you idiot

Spoiler

I love chromate00.

Due to CFR #829 (as you know, the round ends 30min before this round), it seems not clear enough.

According to this comment, the round will be rated for all the participants with rating strictly less than 2100

right before CFR #829 starts, and the order of rating calculation is #829 $$$\rightarrow$$$ #830 right? (Let's make it well-defined like the problem statements so that to avoid needless troubles!)there are two contests on the same day! why?

Both rounds are based on on-site contests, so they have to be the same day due to on-site contests being the same day.

As a tester who has not yet had time to participate in the test, the current number of upvotes is 74, orzorzorz.

Feels like those high school exam days where you take Paper 1 and Paper 2 with 30 mins break between each other

Are you talking about IB exams?

As a tester, I want to get valeriu's attention.

At least one contest could be at usual time on that day.

Two contests one after another [DIV2] :)

It's like participating in ICPC but with a 30 min break. Nice way to prepare for ICPC orz

India vs Pakistan (cry emoji)

Literally. Would have been great if they would have shifted at-least one of the two contest during the normal 8:05 pm IST

(Hope emoji)

Missed it!! (cry emoji)

JEE Advanced vibes.

These old days :)

It gives me board exam vibes!! Paper 1 & 2 exam on the same day with 30 minutes gap. Best of luck everyone.

no way, two rounds in a row

The judger will be so happy during the triple system test:)

two contests in a day sounds interesting..

Please note that this contest doesn't start at a usual time. And there is also a contest (#829) on the same day.Hoping to cross 2100! Good luck!

I hope to cross 1600 and become expert! Good luck for you too!

I hope to cross 1400. Good luck to you too

I hope to cross 1200. Good luck everyone

Finally, I can Fall down 2 times a day!

Sir You can also say that

I can go up 2 times a dayI can't take part in the contest because I must go to school tomorrow.I'm very sad.

School on Sunday!!!!

Consicutive two contest! Wasn't it better if second contest will postpone between 23rd and 29th October?

pls shift one contest by 8 pm other wise we will miss india vs pakistan match fully

Hope to become specialist by doing this contest.

Salute to your account

Question:what if I show a2100-crossing performanceduring the earlier Round#829and then participate in this Round#830? Will#830get unrated for me after#829rating adjustments?Carry in post "rated for all the participants with rating strictly less than 2100 before Sunday, October 23, 2022 at ***"

So I think you will rating for both matches anyway

2100-crossing performance indeed :)

SpoilerFrom 3 contests on 3 consecutive days to 3 contest in 1 day, codeforces has gone wild :)

As a tester, my 4th goal this year was achieved.

orzorzorz, you are the only Japanese among my friends on codeforces. Hope we can become good friends in the future.

how can we register 830 now? I cannot find it in contest

use this

Thanks! I just missed the complete list button on my phone somehow.

If my rating become more than 2100 after I take part in the round 829 and then I take part in round 830,will my rating be calculated based on the rating lower than 2100 or more than 2100?

Score Distribution?

Shortly before round

CodeForces using largest common prefix as title for common contests? It went incorrect for today's contests.

The most balanced round I have ever seen, grats!

POV: YOU'VE TAKEN PART IN THE SANEST ROUND ON CODEFORCES EVER.

How to solve c1?

Consider what happens if we remove any element $$$a_i$$$ from the subsegment.

So the value of $$$f(l, r)$$$ can never be increased by removing elements, only the size of the subsegment can be reduced.

C2s solution involves using this to realize the optimal solution will remove at most $$$\log(max(a))$$$ non-zero elements from each side since each element must disable at least 1 bit in the XOR. So you can solve it in $$$O(n \log^2(max(a)))$$$.

I'm not actually sure what the partial solution for C1 uses, maybe fixing each possible left end and binary searching on the right end?

Yes

Why does trying only the first 30 non-zero elements from each side WA (177636235), but 60 gets AC (177636753)? Shouldn't it be the max number of bits in a_i (i.e, 30) since any position contributes a non-negative amount to f(l, r), so we can only remove each bit at least once without reducing the max value.

Picking first 31 non-zero elements is the optimum, not 30 elements.

By number of solves, C1/D1 must be something very obvious. Absolutely lost any shape:)

Felt silly writing a DFS solution for problem A after being stuck for a while but at least it passed lol 177632733

i've implemented sparse table xd

What is the intended solution to B? I bricked on it for way too long before just coding the overkill dp.

1111000000111100 can be written as 1010 (size == 4)

and the answer is just size-1.

1111000000111100 can be written as 1010 (size == 4) [ It will always be of the form 0101010.... or 10101010..... ]

The reason why we can convert this string to this form is that you will never apply a operation on the same group, example 11001100 if you apply operation on index 0, then it will be 00110011. If you apply operation on index 1, then it will be 01001100. But see that it is unnecessary as you can directly apply the next operation on index 2 and not on index 1 after applying operation on index 0.

Once we transform string, We are supposed to iterate on this 1010(example taken from above) and when you notice 1st '1' the answer will be remaining length because we need to invert the remaining. Since this is '1' next will be '0', so you will apply operation on that '0' which will make it '1' and next of it will be changed from '1' to '0' so you have to keep on applying the operation remaining length times

Example

10 answer is 1

01 answer is 0

0101 answer is 2

1010 answer is 3

My solution greedily flipped the first block of 1s it found while iterating and kept a variable for if everything was "flipped" or not

Example:

10011

01100 (flipped = true, find next block of flipped 1s)

00011 (flipped = false)

2 in total

#177620466

Dont know about the intended solution but mine was something like this. You can break the string into blocks as follows: (000..000111...1)[][][] where [] can contain either 0s or 1s. Till the end of (000..000111...1) we don`t do anything then count the number of [] blocks. The answer is this count. The intuition was that no matter what you will have to perform atleast 1 operation to flip a block [].

Can you tell me your dp solution?

ans = number of alternating 0's and 1's starting from 1st one from the left

What was the process for D1? I got stuck thinking about k-mex because it felt like it would time out no matter what lol.

maybe just a brute force

Mine passed the pretests, but I`m skeptical about the system testing. Until the final moment before submitting was not sure if it will pass or not.

My solution that passed pretests was just to memoize answers since the answer for a query can never reduce unless elements are deleted from the set. So next time we can just check from the memoized multiple.

I think this probably becomes $$$O(q \log q)$$$ or something similar which is good enough to get AC, thought I didn't bother analyzing it properly, I just guessed it was something simple looking at the solve count.

UPD: Sorry it was wrong

I did it similarly, for a given K stored the k-mex in a map. Next time if K came up then set k-mex = max(mapped value of K, next largest multiple of k less than the current smallest non-negative element not present), and stored this in the map. But how is the complexity coming up to be O(q*logq) can you explain that?

Edit: Deleted.

During the contest, it was the q/2 case that I was the most worried about because I was also using sets and map. I`m glad the logic came out to be correct and it got accepted. Thanks a lot for the detailed explanation !!!!

Can you explain why the $$$k$$$-mex is updated at most $$$q / k$$$ times for each $$$k$$$? If we have alternating inserts and queries of the form $$$+ k, ? k, + 2k, ? k, + 3k, ? k, \dots$$$, we are updating the $$$k$$$-mex $$$q / 2$$$ times instead of at most $$$q / k$$$.

You're right. The proof is incorrect. I believe the bound is correct though, and we need a more complicated argument. I'll think more and try to post a correct proof soon. But yeah, it's clear that the lower bound holds.

Have you found the correct proof yet?

No, sorry. I spent several hours on it and typed at least three times my ideas, but then they failed. I am happy to post some ideas here if you are interested.

I have asked a group theorist (really smart guy). Hopefully, we'll get a proof (or a counter example) soon.

Oh, I was definitely overthinking it then. Need to not be blind during contests lol

Time limit exceeded on pretest 18, What can I say?

won't use unordered_map any more

ABD-forces

TBH BAD-forces. Not "bad", but based on the number of submissions xD

In C, how to handle bits that are present in exactly 3 elements? Or if there is no need to handle them separately at all?

How to solve D1? By the looks of it seemed like some kind of precomputation as there were strictly no removals??

Spent 30 minutes on A debugging code when I realized my function to calculate if $$$gcd$$$ of an array is equal to $$$1$$$ looks like this:

Silly mistakeinstead of

How to not be blind during contest? Even though ai = 0 is given in sample of both C1 and C2 but I still ignored and wasted too long .

Ffff i forgot that too

Sad

I don't really understand why memorized brute force for D1 run so quickly.

Can anybody prove the time complexity?

Cause if you iterated too much to calculate the answer, it means you added the element just as many times.

Total "for loop" of all queries "?" executes asymptotically around the same number of times as addition of the elements with "+" (maybe by log times better)

Not a strict proof but intuition though

It reminds of range(0, n, 1) + range(0, n, 2) + range(0, n, 3) and this is supposed to be bound to n log n

Probably it is possible to build strict proof around this

I think it is to do with the number of divisors.

Since $$$k|x$$$ and $$$\dfrac xk\le2\times 10^5$$$ i.e. $$$k\ge\dfrac x {2\times10^5}$$$, I guess the number of $$$k$$$ which satisfy these conditions is about $$$1000$$$.

Your value of memoized answer will change only when you insert the memoized answer in set. So the maximum number of times your answer pointer will move in all queries is O(q)

Edit: Deleted.

everyone downvote me please i got into a challange to reache -100 contribution.LMAO:)

A day well spent

The C1 is so intresting! Though I haven't solved it in contest,I really love it .

Can't complain as this round was based on an Olympiad, but would suggest to have fairly easier problem A in upcoming rounds so that all the actual participants are involved in rating calculation.

B < A without a doubt. And I suppose a considerable amount of newbies notice the term "GCD" in the question and just abandon.

codeforces not geometryforces not mathforces not sleepforces not speedforces

Is the rating going to be calculated based on my rating after round 829 or before it?

Stuckforces

This contest went well for me but first one was disaster for me ,feeling very frustrated, feeling like my career & dream is getting finished ,very sad,cp was something that I loved and it gave me some worth when started but seems like things are not going anywhere now

It happens sometimes man, just hold in there. Hope it gets better for you :)

people can have bad contests but the level of inconsistency that I am showing is detrimental, in first contest I did 800 perf and in the second 1600 ;the difference is 2 times, and this has been for long and I think the way I am performing and practicing I am not doing justice to my talent and I am certainly much more than just a cyan ;and my level of skill won't create any real impact or threat in national contests which is frightening; but yes as I can't give up I should quickly find ways to do well in national level & cf

Same bro #829 is not that good for me but #830 is fine

Well, for me a well performed contest may just mean I'm lucky. And many ups and downs of my ratings actually reflect my true level. Maybe you should focus more on what you learned from every contest rather than the ratings.

This round is great.when will be rating change.before rating change becomes quickly than now.i'm looking forward to rating change

FSTed , sad TaT.

The pretest of div1B is too weak...

Problems are great , especially div1D

Ehrm, this is #830, which had Div.2 only. Maybe you are looking for #829 instead?

Ohh sorry I post it at wrong place. But how can I delete it?

It's fine (for now), Codeforces doesn't support deleting comments more than 3 minutes ago, so unfortunately you cant delete the comment

this contest is good

E limit too tight, got -18 and AC during contest

good luck everybody!!! i think this contest will awesome. Hopefully I will reach cyan??

Minor thing: for D, when it says k-MEX is the minimum nonnegative integer, then doesn't 0 work for a lot of the test cases provided?