Привет, Codeforces!
Мы с Vladithur рады представить вам наш Codeforces Round 769 (Div. 2), который пройдет в Jan/30/2022 17:35 (Moscow time). Этот раунд будет рейтинговым для участников, чей рейтинг ниже, чем 2100.
Мы хотим выразить огромную благодарность:
- irkstepanov и KAN за
то, что они не отклоняли наши задачивеликолепную координацию раунда и помощь в подготовке задач. - Ormlis, antontrygubO_o, generic_placeholder_name, Alexdat2000, Dart-Xeyter, wxhtzdy, sohsoh, glebustim, radal, snowysecret, stevancv, maxverr, Scrubpai, Artem1303, RomkaRS и MaxShch за тестирование раунда и полезный фидбэк.
- MikeMirzayanov за крутые платформы Codeforces и Polygon.
У вас будет 2 часа на решение 5 задач, одна из которых поделена на 2 подзадачи.
Разбалловка 500 — 1000 — 1500 — 2000 — (1500 — 1500)
Мы постарались сделать четкие условия и сильные претесты к задачам, и надеемся, что они вам понравятся, и вы поднимите свой рейтинг!
Удачи!
Также мы бы хотели запустить тренд оценивания задач из раунда. Нам кажется, что это даст полезный фидбэк авторам и сделает будущие соревнования еще лучше. Поэтому, пожалуйста, оцените каждую задачу после конца раунда.
UPD: Разбор здесь.
UPD2: Поздравляем победителей!
Div. 1 + Div. 2:
Div. 2:
As a tester, I like all problems!
New alternating thread free contribution ++
Soon, the absolute value of your contribution gonna pass monogon's.
I can say that all the problems are very interesting to solve and the authors have done a great job inventing them.
By the way, does dkirienko help you?
If the answer is "yes" — is it meaning that participant can solve all problems using Python? :)
P.S. Sorry for Russian, the meaning is that Python is excellent :)
Even though the answer is "no", all problems can be solved using Python!
Is the round going to be Starcraft-themed? :P
Unfortunately, no :)
Hope all of you will get good rating after this round .
Of course we have 7"69" : )
By the way, 769 is a prime number. Hope that means prime quality problems ;)
Love the idea of per-problem feedback prompts! Although I wonder why people already started voting — are those testers or trolls? :P
Some of them are testers, and some of them are trolls, I think. But, I really hope they will revote after the round.
I think it would be better if you have given this feedback voting option in editorial blog instead of announcement blog, Anyway it's a great initiative.
I believe there are people like me who rarely open editorials.
They should've just added the voting section after the end of the contest by editing the blog.
And some of them — I believe — has a superpower to foresee the future
trollforces
you should have waited round to end for putting votes, now alot people will vote but forget to re-vote
The people who vote for the Bad problem even before they see the problem are the same people who always ruin beautiful things!
It is sad to see that some people have already voted "a bad problem" . Anyway, I wish everyone good luck for the contest!
As a tester I think there should be a section to ask for contribution.
Hello, I am a beginner who recently joined codeforces. Will there be a division 3 contest anytime soon? Thanks.
You should try participating in div 2 as well. Because div3 is a rarer thing than div2 :)
This is a normal and reasonable question, and I can't understand why there are so many downvotes. I doubt some users just downvote it blindly because there are already some downvotes and it's tempting to add more.
I don't understand why is it possible to evaluate problems before the round, it would be good update later , but why now?
So, may be it is a good idea, but I actually do not see much of a difference, because there will always be trolls, and you will not get rid of them by moving the evaluation to the update or to the editorial. As for decent people, I think they will revote after the round, if at first they chose the wrong option.
nobody reads tags expect me
Hey! I do!
As a tester, I do read tags!
DELETED
I think it doesn't. This contest is held on 30/1 14:35 UTC, while COCI contest #4 is held on 29/1 14:00 UTC. Correct me if I'm wrong.
oh sorry I misread the time thanks for correction
Hope to get +69.
What about The people who vote for the Bad problem even before they see the problem!! what are u doing?!
what if these votes came from the testers?
man just count the number of testers and votes. ez math bro. Also testers should not vote. they give the writers a direct feedback.
I appreciate the idea of collecting the feedback regarding individual problems. But I'm getting the feel that this way of collecting the feedback might lead to a lot of false statistics. The round hasn't started yet and already you can realize some surprising data.
I agree that it may collect false statistics, but regardless, it's a good step forward. Sometimes there are just bad problems, you can't deny that. And, I appreciate the effort of the authors to step forward and give chance for feedback. This says that the authors are careful and I hope we'll finally have some good problems, not just edge-case work.
Indeed it is a pretty nice initiative to provide a platform for some constructive feedback wrt to problem set. I'm just suggesting some points of improvement to ensure some sort of validity in the poll results. Like opening the poll after the contest ends to begin with.
I suggest putting the voting buttons in the editorial. People should provide feedback only after they have seen the solution.
After being inspired by this I think we will have a huge benefit if we can vote for every single problem after we solved it (maybe there can be some rating restriction for example rating >= 1400). Thus, every problem except its rating difficulty will also have a number that corresponds to its pleasure to be solved and whether it's a good or a bad problem. I think this way both problem solvers and authors can take advantage of this.
Great initiative!
new challenge for all contestants........good luck
Interesting delete line.
Which is more easy problem A or problem E?
I am new on codeforces. Plz tell me.
A
A
Good luck!
Wow! The authors of the round have avatars from Starcraft 2. We should participate!
Wowwwwwwwwwwwwwwwwww how can you add the likes?
Here is a post from MikeMirzayanov.
as a !tester , i am here to farm contribution.
You didn't clarify positive or negative contribution :)
I am not sure the categories for evaluating problems are right. Quite often the problems I fail to solve (or fail to solve without reading the editorial) are the most interesting (best?) problems.
Hoping for a contest which do not contain problems like previous Div2 C
ah shit! here we go again
Good timing of the Australian Open Final, has ended 20 minutes before the contest.
Unfortunatly, our compatriot Daniil Medvedev lose :(
Good luck everyone
ALL the best guys..
bitforces.
If I do multiple submissions, and all are passed then my score depends on my first submission or last submission
On the last submission that has passed pretests.
Thanks
great round, loved the problems!
Hint for task C?
There's no point using BIT OR operation more than once.
I have no idea why my solution to B passed pretests :OO
The fact that C=E1 in scoring distribution is strange for me.
back to mathforces :(
also thanks for very not misleading scoring of the last task
More like bitforces?
math includes bit and D was math also
I consider them as very different things and there's very little math in D IMO.
Is C Ad-Hoc?
C is cancer
DELETED
Which of the problems have endless corner cases?
A: The edge cases are literally in the samples.
B: No edges cases needed here since (n — 1) ^ largest bit always works.
C: Not sure if there is a casework soln to this, but my solution just iterates on the value the final element will take and then you just need to check the smallest value $$$\geq a$$$ that is a submask of this element. I don't think anything is casework heavy here.
D: My solution uses one nice observation + range queries, maybe the other solution is case work heavy which is unfortunate since range query structures shouldn't be required for a Div2D.
E1: No case work here, just find distances and calculate the answer using a weird sort of prefix maximums / decreasing suffix maximum.
E2: No clue, didn't solve it, but I doubt you're referring to this problem.
There could be many different solutions for a single problem. If one takes the wrong direction, then that person might be stuck in many corner cases. I'm initially referring to my case solution for C but I'm also talking about things generally.
This is interesting. One of the things I hate about myself is that I find it hard to discard an idea, so I end up checking a lot of cases and overcomplicating problems unnecessarily and most of the time I will fail anyway. Checking the straightforward editorial for C after struggling is beautiful. I don't think the 4 cases about the bit values is something to be considered painful casework. My conclusion is that, most of the time, you should blame yourself. Writing simple solutions is part of practice.
Yes, you are absolutely right. It took me some time to realize the importance of avoiding getting stuck in one direction. In most cases the problem should have a clean solution which doesn't require too many cases.
Why is range queries bad for div2D?
How to solve D without range query data structures?
Btw I really like the monotonic observation. Its such an obvious fact that as we increase the number of elements the gcd will not increase, but it really did not strike me in relation to the problem.
I kept a multiset of ban positions for each indices. For instance, a suffix gcd equals to $$$3$$$ at position $$$5$$$ bans position $$$7$$$.
When we actually update a gcd, we maintain the set. Such updates will not be many as each time at least one of the gcds lose a factor.
I think the key observation is that given a[i], there can be at most around log2(a[i]) distinct gcds among gcd(a[i]), gcd(a[i — 1], a[i]), ..., gcd(a[0], ..., a[i]).
So, combined with the monotonic observation, it's fine to maintain a partitioning of [0, i] into intervals, one for each distinct gcd. So in log2(i) time you can find the earliest position j such that gcd(a[j], ..., a[i]) is equal to its length. I guess you could also binary search but that's unnecessary.
Could you elaborate on how you would generate and maintain such a partitioning though? I can think of a way to do this in $$$O(n \cdot \sqrt{max(a)} + n \cdot \log(max(a)) \cdot \log\log(max(a)))$$$ but this is too slow. I basically can't figure out how to eliminate factorization for newly added factors from $$$a_i$$$.
As there are always $$$O(\log{n})$$$ entries, simple brute force takes $$$O(n\log^2{n})$$$. Code
Oops, I somehow missed the obvious point that similar suffixes cannot become different again, so just directly updating them each turn works.
Thanks for the help.
Here is a correct submission that uses the idea above: https://mirror.codeforces.com/contest/1632/submission/144586184
Sqrt decomp go brr
There were so many submissions by unrated accounts around the same time. Were the solutions of first 4 problem leaked or something ?
bit operation contest. lacked variety of problems...
The contest was a Bit-difficult
I love problem D
the idea of binary search was very neat!
Realized just after the contest that, replacing a for loop with while(bs) will work like magic
Nice problem :)
bitforces
Very cool contest and interesting tasks!!!
Read at this bc I can't delete this comment: https://mirror.codeforces.com/blog/entry/99442#comment-882354
More cheat today.
@ MikeMirzayanov
we need to ban the cheat accounts,this kind of account makes imfair to cp
What's more , I find that most of accounts which submitted their code in 01:59 of E were suspect of cheat.
some similar submissions I found for reference
https://mirror.codeforces.com/contest/1632/submission/144547837 https://mirror.codeforces.com/contest/1632/submission/144547903 https://mirror.codeforces.com/contest/1632/submission/144546752 https://mirror.codeforces.com/contest/1632/submission/144548076 https://mirror.codeforces.com/contest/1632/submission/144547049
all of them entered the top 50, and some of them have cheated for three contests and still do not get banned
edit: all above get banned now so I am going to post more
https://mirror.codeforces.com/contest/1632/submission/144518046 https://mirror.codeforces.com/contest/1632/submission/144518214 https://mirror.codeforces.com/contest/1632/submission/144535677 https://mirror.codeforces.com/contest/1632/submission/144533427 https://mirror.codeforces.com/contest/1632/submission/144533878 https://mirror.codeforces.com/contest/1632/submission/144531757 https://mirror.codeforces.com/contest/1632/submission/144557915
there should be a button for reporting cheat codes
How is this wrong for E1? I maintained an Euler tour and segment tree. If I want to connect node 1 to node x. So max distance here will be max((max distance in the subtree of node x — dis[x] + i), max in the remaining tree excluding the subtree). Finally I take min ans for each x. Can someone pls give a counter example where this fails?
Here is a case where your code will fail(if I have understood it correctly)
9
1 2
2 3
3 4
4 5
5 6
6 7
4 8
8 9
The correct answer for x = 1 is 3, but by yout logic it's 4
Thanks for the test case
Я, конечно, не специалист, НО ВОТ ЭТА ГРУППА УЧАСТНИКОВ КАЖЕТСЯ СОМНИТЕЛЬНОЙ!!!!
abaddon9379992 zandira332 gubkabiba1312 vityakrishka69 copatoch777 salozida41234 artiom_barbary12 svingerchoper utopia_show1234 triada_tropik oposite_of_mom govorunishka f5robot2 popka_golovka312 gregory_pergant urod_marod Bad_google octopus3141 slivok_show GIMRAN__MOTHER aggressive_kid doggy_style22 popje popu_mit_nado chaba toster11 e3utpak friend01 andrewopsss chaba011 gaiday goodluck01 rot_ogorod Jazzer01 artem011 ignat0505 Naabordazh petro1990 sergserg marygot Artsiom27 joker03 opacha iozzw barlonix SerGoGo NastyaNestea Artemis011 Dastaqq ioz401 vareev calger catorey Voytenko gaspersq GenaNa Tema.ka tapertex nikitosss katushaaa jalora
Is this even possible to create a solution for D that exceeds time limit?
I guess add all primes in the array
In question B ,if we take input 6,then according to editorial solution answer will be {3 2 1 0 4 5} but the optimal ans is {2 3 1 0 4 5}.
The problem asks us to minimize the maximum xor among pairs of adjacent elements. Both
3 2 1 0 4 5and2 3 1 0 4 5have the same maximum xor of0 ^ 4 = 4, so I don't think it really matters.Got it, Thanks
Good contest
During the contest when I was solving problem c, I got the intuition that we can solve this in a total of three steps in these sequence 1. either increase a or b by some amount. 2. take the OR. 3. increase the b to match the value with the second step value. Although I was not able to prove it during the contest. I submitted it just based on some gut feeling. So I just want to know is this the case with other people too? or do you guys first prove your solution and then submit it?
MikeMirzayanov I'm not really sure where to put this, but I received these two messages:
Attention!
Your solution 144568353 for the problem 1632D significantly coincides with solutions Weierstrass/144555583, codebuster_10/144561876, 876pol/144568353, Winterfrost/144569022, xiaoququsd/144572170, Kanheyalal/144572862, dimss/144575074, Kawaii/144576113, matouzouken/144576356. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://mirror.codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.
Attention!
Your solution 144557728 for the problem 1632C significantly coincides with solutions Weierstrass/144543081, codebuster_10/144548751, Kawaii/144549603, matouzouken/144551794, Winterfrost/144556519, 876pol/144557728, xiaoququsd/144562448, dimss/144563984, Kanheyalal/144564250. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://mirror.codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.
I wrote the code for both these submissions locally on vscode and I don't know any of the people mentioned in the message. Also, the codes don't seem that similar in the first place.
However, just to be sure, the code for 1632C is fairly short and is just a false positive. I had also submitted a couple WA submissions before this one, so its not like I copied it off of someone.
I got the code for the sparse table in 1632D from https://brilliant.org/wiki/sparse-table/, and the rest of the code is also short and is just two pointers.
(also, sorry for tagging you)
Why their is positive Plag check, submissions are not even similar at all ? MikeMirzayanov Please see to it. I ran both my submissions locally and use my own template, any of the given submissions does not seem to be similar to mine at all.
I also received this message, and I think our codes are completely different (I even didn't use any existing templates).
wow how many cheaters were removed? I should have got only +7 delta at the end of contest but now got +22
SO CRAZY that one out of four accounts were cheaters in last round.
I think that a good way to anti the cheater is to solve the problem faster than them. So whether they are cheating is unmeaningful.
In the third problem, isn't b' the same as a'|b. But, it doesn't give me the correct solution. If anyone could explain.
Hi I am a newbie and would appreciate some assistance here. My submission fails with verdict
Wrong answer on test 2. However when I click on my submission number I can only see test case 1 which is succeeding. My question is how can I see test case 2 ?During the competition you will not be able to see private test cases. However, after the competition, you can resubmit your code and you will be allowed to see them.
I have a trouble understanding problem D example test case 3:
I expect that for prefix (2 12 4 8) we will need only 2 replacements, but it's 1 according to example
Specifically, I see two separate pairs: GCD(2, 12) = 2 and GCD(4, 8) = 2. I expect that we will need to replace one value in each pair
Can you help me?
GCD(4, 8) = 4. And we can change this prefix into 2 5 4 8.
Hi MikeMirzayanov, My id has been hacked and someone has submitted fraudulent copied solutions from my account. They have even changed the email address of the account to something random and I can't even recover it. I am sending this message from an existing session. Dm'ed you the details. Please help.