Привет, Codeforces!
Я рад пригласить вас на мой Codeforces Round 830 (Div. 2), который пройдет в 23.10.2022 13:05 (Московское время). Он будет рейтинговым для всех участников, чей рейтинг будет ниже 2100 до 23.10.2022 10:50 (Московское время).
Задачи были придуманы и подготовлены 74TrAkToR. Хочу поблагодарить всех, кто оказал бесценную помощь в подготовке этого раунда:
- Координатора Artyom123 за отличное общение и помощь с подготовкой.
- Тестеров gisp_zjz, Pointy, aaaaawa, 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, MagicalFlower за качественное тестирование раунда и важные советы.
- А также тестеров, которые тестировали командную олимпиаду ЧеРеКОШ — именно из задач этой олимпиады и был составлен раунд: orz, DIvanCode, CAMOBAP31.
- MikeMirzayanov за прекрасные системы Codeforces и Polygon.
На раунде вам нужно будет решить 5 задач, некоторые из которых имеют подзадачи. У вас будет 2 часа на их решение.
Разбалловка будет объявлена ближе к началу раунда.
Желаем всем удачи и высокого рейтинга!
UPD: Разбалловка: $$$750-750-(1000-1000)-(1250-1250)-3000$$$
UPD: Разбор
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?
Yeah I am practicing good problems you idiot
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)
JEE Advanced vibes.
no way, two rounds in a row
The judger will be so happy during the triple system test:)
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 day
I 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?
74TrAkToR while creating this round :)
haha))
hahaha
Но это экскаватор
BULBUlYATOR :)
Ahahah, fr
hahaaa..
Hope to become specialist by doing this contest.
Question: what if I show a 2100-crossing performance during the earlier Round #829 and then participate in this Round #830? Will #830 get unrated for me after #829 rating 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 :)
From 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?
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.
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
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
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.
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?
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:
instead of
АХАХАХААХ
74TrAkToR кидай скрин раунда в тг, закину косарь минимум))
http://t.me/lastoneebot
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)
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?
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
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
моргенштееееерн)
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?