Hello, Codeforces!

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

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

- Coordinator irkstepanov for excellent communication and help with preparation.
- Testers Golovanov399, tibinyte, Silver_Fox, Illumina, eeeDA, coder8080, valeriu, XaRDKoDblCH, cristi_tanase, pshat, Vladosiya, DIvanCode, nnv-nick, priyanshu.p for high-quality testing and valuable advices.
- AlFlen for the idea of one of the tasks and two wonderful years together!
- All members of the jury of the team Olympiad CheReKoSH, because the round is made up of the tasks of this Olympiad.
- MikeMirzayanov for amazing Codeforces and Polygon platforms

During the round you will need to solve **5 problems**. You will have **2 hours** to solve them.

Score distribution: $$$500-1000-1750-2500-3000$$$

We wish you good luck and high rating!

**UPD**: Editorial

As a tester, omg round by coordinator.

Why multiple contests on same date ?

Because based on contests

Why are ratings 1600-2099 so lucky they can participate in two Div.2 competitions.

The problems are very good. Hope you will love solving them. (:3 first time testing)

I'll never forget exciting rounds coordinated by you. Hope the round will be fine.

Looking at the score distribution this seems like a speed run. Gonna register with the motto Don't participate if you can't dominate.

Looks like the difficulty of problem D is going to be harder than usual

What do these points mean? is there any correlation between points and problem rating?

Generally I have seen Prblm D to be at max of 2000 points, so keeping points high will most probably mean higher difficulty

But why two Div. 2 rounds on the same day?

They are based on contests

pshat orz

Only five questions and the score distributin is also high why so?

you forgot NOTE THE UNUSUAL STARTING TIME in bold to make people aware

Why is the registration for Codeforces Round 905 (Div. 2) saying "Rating should be between 1,600 and 2,099 in order to register for the contest"?

I think it's better if you write in the post that only >1600 can register and get rated

This is Round 904. Rated for everyone below 2100. You are talking about Round 905

Yeah but even the registration page of Round 904 says that I'm registering out of competition... probably it's not mentioned properly in the announcement, or it's a bug.

Just noticed now, confusing :")

Seems like Codeforces Round 905 (Div. 2) gonna be blue-purple war!

I really like this timing.

Why is it said here that the competition will be for rated participants with a rating of no more than 2100, but at registration this is a rated competition for participants with a rating from 1600 to 2099

It is very strange. I hope they fix that.

I guess at CFR904 and 905, there will be chaos because of the back-to-back rounds and tricky format of CFR905. So I suggest some unusual rules for them:

When the registration for division 905 will be open? Usually I get an email with invitation.

Go to the contest page and register.

Why there was said in the announcement that "this round will be rated for all the participants with rating strictly less than 2100.", but there was said in the register page different "You are registering "out of competition", reason: rating should be between 1,600 and 2,099 in order to register for the contest"? I'm getting confused, can anyone help me to figure out it?

There was a mistake on my side setting up the round. Now everyone below 2100 should be able to register as usual. I'm sorry for the inconvenience. We'll automatically change the status of already registered and having rating below 2100 to official contestants before the round, you don't need to do anything.

Thanks for your work!

The rating changes for a round are sometimes cancelled and then recalculated, which takes about 1 day.

Round 905 starts just 2 hours after round 904 ends. Consider the following situation.

You participate in round 904, your rating changes, and then you participate in the corresponding division of round 905. After a few hours, rating changes for round 904 are cancelled and recalculated, causing your division to change and meaning you haven't participated in your division of round 905.

The chance of this happening is very small, and it's interesting to know what would happen in this case.

Why there are so 2 contests on the same day?

you should guess it bro the reason's really written in both announcements

I registered in both 904 (in div 2) and 905 (in div 3). In case, for 904 my rating increased to be >=1600 and rating update happens before start of contest 905 but after registration end time. So in this scenario, will my registration in 905 as div 3 still be considered valid even if my rating now becomes >= 1600. Wont it create any confusion?

(13-21) — 9 days 0 contest. (22) — 1 day 4 contest!

Why there are 4 contests in one day, and for the next week there's no contests?

would love to have more rounds like this that are not late in the night(in my country) :)

Hoping to become CM in this contest!Only 9 ratings!

So climbed up within such a small time frame. Highly talented

It's time to

rage(100%)SpoilerYeah I'm fan of Mob Psycho 100

SpoilerMob is in my pfp, when he

rages(100%)SpoilerHope to become Expert

SpoilerGL & HFSpoilerOK, let's stop

Please note the non-standard start time for the roundThis is my first contest. Can i join it?

Yes

Dangerous round 3rd & 4th questions will be difficult as the points are very high and 1st question is of 500 points which is more than some earlier rounds. ( Means div 2 B === this round A)

More suitable for Chinese baby constitution

So intersting

Hats off to US contestants who will join at 00:05 am and 04:00 am today.

Nice start to a Sunday afternoon (╥﹏╥)

How to solve problem C?

Spoilerbruteforce for every point as it is maxpoint after compression

Can you please elaborate the solution for Problem :C ..

lets fix some point P, and make a[P] max, how we can guarantee that it will be max? to do it we can use only segments which are l[i] <= P <= r[i], then find min and max for this.

we need to do it for every important point, we can find this important points after compression l and r. but it is O(n^2) which is too slow

lets add and remove segments greedily, and to do -1, 1 operation with lazy segment tree, and find min max also with it, so complexity will be O(nlogn) because we add every segment only once and remove also only once

upd: actually using Lazy segment tree is overkill

suppose some point is the point with the maximal value(call it p1), then only segments that pass this point are relevant. because for any other point that may be the minimal point(call it p2), segments that only pass p2 are obviously necessary to delete, and for those who passes p1&p2 at the same time, we won't have to delete them, since they dont affect with the outcome of v(p1)-v(p2).

Maximum number of overlapping segments that don't end in $$$m$$$, or maximum number of overlapping segments that don't start in $$$1$$$. I have 5 lemmas to prove this, and it passed system tests.

First sort segments by increasing left border. Then go through them, maintaining a priority queue of the right borders to determine when a segment goes out of consideration. We can observe that if the mth square or the 1st square is not covered, then the min is 0. Otherwise the min is the minimum segments covering the 1st or mth square. The max is the amount of segments currently considered. Code

No need for segment tree or priority queue. Assume that in the optimal covering, the min point is left of the max point. Then we might as well take the min point to be as left as possible, or index 1, because there is no reason to add segments left of the min point. Therefore, we just use all the segments that don't cover index 1 and do an inverse prefix sum to find the max. Same argument for the min point is right of the max point. Take the max of both and that is your answer.

How to solve problem D?

Use the principle of inclusion-exclusion on gcd. This can be done using Mobius function. Time complexity will be O(nlog^2n) I think.

You can count "bad pairs" instead of "good pairs".

I found $$$D$$$ so much easier for $$$2500$$$ points. If $$$a_k$$$ divides $$$a_i$$$ and $$$a_j$$$, this means it must divide $$$gcd(a_i,a_j)$$$. So, iterate over $$$gcd(a_i,a_j)$$$, Let $$$gcd(a_i,a_j) = m$$$, find $$$num[m]$$$, denoting number of pairs having $$$gcd = m$$$, can be found easily using recurrence $$$num[m] = cnt[m]\cdot(cnt[m]-1)/2 - \displaystyle \sum_{r=2}^{\lfloor{n/m}\rfloor} num[r \cdot m]$$$, where $$$cnt[m]$$$ is the number of indices $$$j$$$ such that $$$a_j$$$ is a multiple of $$$m$$$ in $$$O(n \cdot logn)$$$.

Now, after fixing $$$m$$$, we just need to check if some index $$$k$$$ exists such that $$$m$$$ is a multiple of $$$a_k$$$ or not. This can also be checked easily.

You can also do it using mobius inversion

I agree, I think there should be another problem to fill in the gap between D and E.

D had pretty less no of solves, its a div2 anyways i think it was fine

yes, D is basically gcd convolution exercise..

WA on test #3,Would someone like to give me the hack data?

Problem B: https://ideone.com/GV1ZXe why wrong answer on pretest (4) ?

You should use 64-bit integers

Why

There can be up to O(n^2) operation needed, i.e. your

`ans`

and`lst`

should have been`long long`

Thank you, got AC

How to solve B? Spent lot of time but couldn't think of correct approach. Any hint?

check for total number of 0 and ones in the string for testcase keep a vector to keep the position of one and zeros and use those index to calculate your swapping

Thanks for the reply, I read you comment and even looked at your code, I simply cannot wrap my head around this. I took a similar approach during contest, could you tell me where I went wrong? 229186836

I looked at your code but I am very sorry that I cant debug it, as you may see in my profile that I am not a high-rated coder, and theres some thing in your code like forn, fat(n) that I cant understand. Better if you can watch the editorial after the round is declared finished officialy. Goodluck :-)

Thanks for the effort. I was able to solve it after reading the editorial. 229404262

pE too hard :((( can someone help me, thanks

C was very similar to this problem: link

It's almost the same Dammnn!

is there a non brute force solution for A if k>10 ?

I am a beginner but problems A and B were very interesting. Enjoyed solving it

Couldnt debug C in time I just need 5 more minute :((

Made a screencast for this round: link. Very unedited and just made on a whim.

Got A-D and was almost done implementing E. Probably would've got E if I didn't spend so much time explaining stuff. Lmk any suggestions.

Thanks guys for the contest!

Now let's get ready to continue with Codeforces Round #905!

Can anyone please show me why my code goes wrong

Very trash Problem E with 0 thought but +inf boring implementation.

trash contest. The passage is poorly written and difficult to understand, with many omissions.

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

so i recently got a notification that ive been caught for plagiarism, I am absolutely shattered after seeing it. I am assure you that i wouldnt use cheap tricks to increase my ratings, to prove that i had a common source published before the contest

int findClosestRecursive(vector arr, int left, int right, int target) { // base case: when there is only one element in the array if (left == right) { return arr[left]; }

} this part was taken from a popular coding website geek for geeks i never knew this would be such a problem

It was a nice round! Congrats to all participants!