Привет, Codeforces!
Я рад пригласить вас на мой Codeforces Round 904 (Div. 2), который пройдет в 22.10.2023 10:05 (Московское время). Он будет рейтинговым для всех участников, чей рейтинг будет ниже 2100.
Задачи были придуманы и подготовлены 74TrAkToR. Хочу поблагодарить всех, кто оказал бесценную помощь в подготовке этого раунда:
- Координатора irkstepanov за отличное общение и помощь с подготовкой.
- Тестеров Golovanov399, tibinyte, Silver_Fox, azureglow, eeeDA, coder8080, valeriu, XaRDKoDblCH, cristi_tanase, pshat, Vladosiya, DIvanCode, nnv-nick, priyanshu.p за качественное тестирование раунда и важные советы.
- AlFlen за идею одной из задач и два прекрасных года вместе!
- Всех членов жюри командной олимпиады ЧеРеКоШ, ведь именно из задач этой олимпиады и составлен раунд.
- MikeMirzayanov за прекрасные системы Codeforces и Polygon.
На раунде вам нужно будет решить 5 задач. У вас будет 2 часа на их решение.
Разбалловка: $$$500-1000-1750-2500-3000$$$
Желаем всем удачи и высокого рейтинга!
UPD: Разбор
As a tester, omg round by coordinator.
Why multiple contests on same date ?
Because based on contests
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 div2 rounds on the same day?
Deleted
They are based on contests
pshat orz
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!
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.
Это какое-то новое правило, что див2 можно писать только с 1600?
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?
Hoping to become CM in this contest!Only 9 ratings!
It's time to rage(100%)
Yeah I'm fan of Mob Psycho 100
Mob is in my pfp, when he rages(100%)
Hope to become Expert
GL & HF
OK, let's stop
This is my first contest. Can i join it?
Yes
More suitable for Chinese baby constitution
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?
bruteforce 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".
pE too hard, can someone help me :(( thanks
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..
pE too hard :(( can someone help me, thanks
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
ansandlstshould have beenlong longThank you, got AC
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 ?
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.
Very trash Problem E with 0 thought but +inf boring implementation.
Ratings updated preliminary, it will be recalculated after removing the cheaters.
Is it rated？