Привет, Codeforces!
Во 14.12.2021 17:35 (Московское время) состоится Codeforces Round 760 (Div. 3) — очередной раунд для третьего дивизиона. В этом раунде будет 8 задач, по сложности подходящих для участников с рейтингом до 1600 (во всяком случае, мы надеемся на это). Но, конечно же, участники с рейтингом 1600 и выше могут зарегистрироваться на раунд вне конкурса.
Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов (мы очень надеемся, что в течение нее упадет не очень много решений).
У вас будет 2 часа и 15 минут на то, чтобы решить 8 задач. Штраф за неверную посылку будет равняться 10 минутам.
Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:
- принять участие не менее чем в двух рейтинговых раундах (и решить в каждом из них хотя бы одну задачу),
- не иметь в рейтинге точку 1900 или выше.
Независимо от того, являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.
Раунд основан на задачах муниципального этапа Всероссийской олимпиады школьников в Саратове и Саратовской области, поэтому если вы участвуете в нем — пожалуйста, воздержитесь от официального участия в этом раунде.
Задачи вместе со мной готовили Brovko, shnirelman, Lankin и awoo. Выражаем свои благодарности тестерам раунда: vovuh, Nil_Sinyaev, IsaacMoris, altynai, MarcosK, osylai, ZulaMostafa, nondeterministic, mumumucoder, peroon и kocko.
И, как и всегда — большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces, без которых этот раунд бы не состоялся!
Удачи в раунде! Надеюсь, задачи, которые мы подготовили, вам понравятся.
UPD: Разбор задач.
Looking forward to this round!
Wish everyone positive delta
Though I have solved 1st problem in 22 min in 1st attempt yet why I'm not ratted?
The rating changes will be published after 12hrs long hacking phase, where you can hack others' solutions.
what is hacking?
After the end of this contest round. The hacking phase is of 10-11 hours in which the participants and view the submission of other participants and and can give hack(i.e some test case in which code will fail but code has passed system test). Giving a correct hack will add to your rating and giving wrong hack will deduce to your rating.
Actually in Div3 there are no points for hacking, no add and no reduce.
But if someone's code is hacked he will obviously lose marks
For reference Check my submissions, I got hacked on F :)
when will the rating change??
idk, hope that it changes soon
im waiting so eagerly
Aah ,i miss those days of rated div3's for me.
Though, not too long ago.
Thats why i ain't used to it ,hence i miss them
BledDest and what if the people who participated in All-Russian Olympiad for schoolchildren in Saratov and the Saratov region take part in this Div 3?
Just solve more and it wont affect you.
1199r. I hope i will be green after this round
Sorry to say but your rank in last round look suspisious .
UPD :- There is nothing wrong in your rank and performance , I misunderstood your rank which you acheived in Technocup round 3 as your rank in CF round 759 . I recently came across blog stating 22-40 rank in previous contest are all cheaters and lot of cheating happend in last contest and then I saw you rank and it look suspisious and I didn't saw the contest name . I apologize for that .
what's wrong? what if a person just performed well for their rating and reached 1199?
Upd.: ok,now it seems ok;)
My rating was 1199. I remember. Techno cube gave me 1199 r
maybe you could turn green today itself after cheaters are removed.
Upd: sadly you lost 1 point
First unrated round for me :)
Looking forward to be unrated on this contest
I wish i could gain 200+ in this round.
Wow, I am very impressed by your persistence on cp(by looking at your graph). Keep it up!
Thanks bro.
Last 2 rounds had very bad organization. But I think this will be good.
BledDest and awoo have written about a hundred educational rounds and they are pretty good at their work. So I think (and hope) we can expect a great round :))
The round will contain 8 problems, which are mostly suited for participants with rating below 1600 (or we hope so).we hope that our tests are strong enough, so there won't be too many solutions hacked during this phaseI hope you'll enjoy solving the problems we have prepared.hopeforces?I hoe... I become LGM this round. teh heh
You can copy 'p' from here and paste it.
i hate comments under this post so much.
like i hope to reach pupil/expert or i hope everyone positive delta
there are so many comments like these, they are just rubbish
read this: https://codeforces.me/blog/entry/68909
Also me when it's accepted
Small bug in codeforces ...
EDIT : It has been fixed, sorry
Educational Div3 Round
How Many problems should I do in div 3 as a newbie to become pupil?
Increase by how much ?
Depends on rank not no. Of problems
Also on number of participants
I think three or four will be enough
solve just like my alt hi123bye he is again pupil now
130 day streak ... How did you get that much patience?
inspired by the legend of all times prashant_th18
Good luck for everyone!
Last few contests have had issues, there are some new-to-me names in list of setters, and the site is bugging out as I try and see who's registered (in addition to the usual last-contest-colorchange bug)...
Div3 all-problems-equal-points ups the risk for bricking and I haven't had a good night's sleep since advent of code started...
Screw it, I'm in. I don't want to start caring about keeping my gamified color-number artificially high from contests I don't participate in anyway...
May this comment age like rancid eggnog.
OkaY Bois, Hope this one will be f*cking awesome Enjoy solving
let's make me the most downvoted user on cf !
1 minute left. Good luck everyone :)
RecoveryForces
Announcement blog says there are 8 problems, but there are only 7?
We decided that the contest was difficult enough with 7 problems, so one problem was excluded.
worst E
Why?
My smoll brain takes forever to understand Problem E's statement ;-;
just read the sample explanation. I didn't understand the statement either.
could someone explain problem D to me? my greedy solution gives WA 2. Is there another way to solve a problem?
Your solution was difficult to understand. But basically, you want to match the last $$$2k$$$ elements, $$$a_n$$$ with $$$a_{n-k}\ $$$, $$$a_{n-1}$$$ with $$$a_{n-k-1}\ $$$ and so on..
How to solve E? Looks very interesting, dissapointed about not solving that
sum(a) = sum(b) / (n * (n — 1) / 2) b[i] — b[i — 1] = sum(a) — n * a[i]
I think it should be sum(a)=sum(b)/((n*(n+1))/2).
I love it, the we have two main observation, first is:
Let S(b) sum of all bi and S(a) sum of all ai
the total time of every singer is ai + 2*ai + ... + n*ai = ai*n*(n+1)/2
S(b) = sum of total time of every singer -> S(b) = a1*n*(n+1)/2 + ... an*n*(n+1)/2 -> S(b) = S(a)*n*(n+1)/2
Using 0 indexed, the second observation is:
bi = 1*ai + 2*a(i-1)%n + ... n*a(i+1)%n
b(i+1) = 2*ai + 3*a(i-1)%n + ... 1*a(i+1)%n
b(i+1) — bi = ai + a(i-1)%n + ... — (n-1)*a(i+1)%n
b(i+1) — bi = ai + a(i-1)%n + ... + a(i+1)%n — n*a(i+1)%n
b(i+1) — bi = S(a) — n*a(i+1)%n
a(i+1)%n = (b(i+1) — bi — S(a))/n
To check if the answer is YES or NO, you have to be sure that all divisions leave 0 remainder and all ai > 0.
My code: https://pastebin.com/iaxwvTSq
Thank you for this amazing contest! I really like the problems, all of them were perfect for their place, especially problem E!
Is problem D a mixture of greedy and sorting?? btw i was not able to solve it... can Anyone tell me the correct approach
yes. sorting in decrease order then greedy use a[i + k] / a[i] for each i from 1 to k
We must/want remove the k*2 biggest numbers.
So sort descending, and pair a[i],a[i+k] for cost of 0 if these both numbers differ, or cost=1 if same. Then add the other (n-k*2) smallest numbers.
For me B and C where more complecated than D,E,F. No idea how to solve C, even cannot think of a randomized solution.
Take the GCDs of all the elements at odd and even indices, let's say G1 and G2. If any element at an odd index is divisible by G2 and any element at even index by G1, the answer does not exist. Else answer is either G1 or G2.
get gcd of all odd-index elements, then check if any even-index element is divisble by it. Then do reversely.
Ah, ok. I somehow misinterpreted this one. I searched for a d that divides the array into two sets of numbers with same size. :/
Just wondering why did the authors gave n <= 100 for problem D , was it just to confuse , or the correct solution is O(n*2) indeed ?
It's O(nlogn). I am also confused.
How to solve F?
I generated all possible binary numbers as strings up to length 62. Thats fairly quick since we basically can only append a '1' at begin and reverse.
at first operation, if you add 0, then all the 0s at the end of the original number is removed. Then you can only add 1 to both sides of the original number to get the target number. Add 0 is no-op.
for F it's kind of understandable if you can break it down. how i did it was:
If you add a zero, essentially you are saying, I can flip the string and trim all zeroes at the front and back. So essentially I can always reverse it whenever I want.
If you add a one, you can think of it as I can add a one on the left or right of the string without much thought because I can flip whenever I want
So the only caveat left is, did I have to trim the zeroes to do this reversing operation in the first place?
So there are 2 cases:
A) String is [1?????0].
B) String is [1?????1].
For case A: I can add a 1 at the back, and only then can I add the 1s however I want. Or, I can trim the zeroes, and then add the 1s however I want.
For case B: I can add 1s at the front or back, however I want.
So your final answer will look like this:
Case A:
Case B:
and thats the final answer, maybe a little complicated now that i type it out
edit: removed redundant statement for clarity
Submitted AC solution of F just after the contest :)
E was a nice problem.
An amazing round ruined in the end by leaked E and leaked D. Mass submission at the end was the indicator.
Please take appropriate actions BledDest MikeMirzayanov
very educational channel
Very anti-educational channel
**Any One what is wrong in my Code
C**Code
I think it is because you are taking maximum of the two gcds. Instead you should try both.
sorry for my bad case
Could someone tell me how did you guys solve B and C? It took me forever to understand the question and could not come up with the solution. Even a hint would be enough, this is my second contest and I am trying to improve.
First you have a string s equal to the first bigram. for B, if one bigram's second character and the next bigram's first character is the same, you can always treat them as adjacent, add the next bigram's last character to s. Otherwise, add the next bigram to s. After you have iterated all the bigrams, if length of s is smaller than N, add one 'a'.
After you read a bigram into a string, you can delete all spaces with a consecutive letter if that space has the same letters on both sides. After that you delete the last space left or add any letter otherwise. Regex code: 139328475
one doubt about F problem, can we add multiple '0' or '1' and then perform a reverse operation?
no. only one for each operation.
I could not solve any problem. It was so disappointing. Although I can solve division-2's problem in archive but I couldn't solve any problem here in real time contest.
DO practice my friends !!!!!
what is wrong with my code? please help!
my approach:- I divided the array into two arrays a(all Even Indexed Elements) and b(all odd indexed). then either the ans is min(a) or min(b) or 0. if min(a) divide entire a and doesn't divide a single element in b then min(a) is ans, and vice versa for b. if none of the above two conditions are satisfied then ans is 0. https://codeforces.me/contest/1618/submission/139292894
not min(a), it's gcd(a).
35 6 14 9. No element divides any other, but $$$d=3,7..$$$ are answers.
I solved F recursively with some early termination conditions. Hacks would be appreciated
I noticed this relation in problem E that
b[i] — b[i+1] = n*a[i + 1] — sum(aj)[j = 1..n]
b[i — 1] — 2*b[i] + b[i + 1] = n*(ai — ai+1)
and then i calculated a1 — a2 , a1 — a3 ,...... a1 — an
but i couldn't get which value of a1 give the solution
my first time to solve all problems in a contest, although it's a div. 3. Thanks to the authors!
Please, can somebody explain why is my code for problem D wrong or give any counterexample? 139306202
1 2 4 4, I think.
Thanks. Such a stupid mistake, it's a shame.
Guys I need help with question C. I keep getting wrong answer on test 3, and I don't understand why my code fails. if you can, please help me understand why my code fails and how to properly solve it? my submission: https://codeforces.me/contest/1618/submission/139297986 thank you in advance.
Think about this case:
1 4 3 6 5 The answer is 2 but your code says that there is no answer. Divisor can be not presented in array, you should check gcd of all odd and then for even positions as a d.
An extension of problem A if anyone wants to try :
https://dunjudge.me/analysis/problems/1166/
Hello everyone, I'm new to competitive programming, and this is my first official round. I have a problem with Prob A (yes, A). I think my answer is correct but marked as a wrong answer. You can check this submission 139305580 for more details.
I want to know, if possible, where my mistake is so I won't make the same mistake in the upcoming rounds.
Thanks!
Check ur solution for value of a=[ 1 2 4 ]
it is wrong .I also made the same error at the first glance. actually if you are looking for sums you know that 2 smallest values will be your first and 2nd value but you don't know about the third value because if 1+2=3<4 ,so we know that sum of all the values is going to be the maximum ( last value in the given input ) so if you are taking given input in array soln will look like this. a[0] ,a[1], a[6]-a[0]-a[1]
Hi ,Can anyone hack my problem F ? i wrote it in a hurry and want to know if someone can hack it.Thanks
How to solve G ?
If you concat array A and B (let's call it array C), after sorting the array C, the problem becomes: for each K, you can connect C[i ... j] if each i <= x < j, and C[x + 1] — C[x] <= K, so after choosing some elements in each range, what's the maximum sum?
So we need to maintain:
What are the leftmost and rightmost index of the range that C[i] belongs to? (hint: DSU)
How many numbers I can choose in this range? (hint: since array C is sorted, we should always start picking the largest one first in greedy)
How do I merge 2 ranges?
Turns out our best sum only changes when the merge happened, so I took the offline approach by sorting the queries first and used DSU to maintain the information.
Hope it's clear, you can check my submission: 139325375.
A simple way to solve: use two sets, both store vectors of four elements: the leftmost index of the segment, the rightmost index of the segment, how many numbers we take from it, and the distance between it and the next segment on the array. The first set will sort by the distance, the second set will sort by their first elements.
So how to use them? At first, merge the two arrays a and b into 1 array, let's call it TTL, use a map to save if we are currently have something or not. Then for each element, we will make a segment based on them: the leftmost and rightmost is their index, the number of elements we will take is either 1 or 0 depending on the map I described above, the distance will be the difference between it and the next number in TTL.
What will we do now? Solve the problem offline, for each query merge some of the segments which have the smallest "distance" into some other segments, so there will be no more than N merges. Since we are using sets, the complexity is O(NlogN).
To calculate the sum efficiently, use a prefix array.
You can check my implementation if you want:
Hope that my defines are not difficult to understand.
made it to double digit for the first time,got my f hacked ffs *cry_emoji *cry_emoji
how to solve F?
There are only few numbers you can generate from a given number. Generate all and check if one equals the searched value.
Hello, at my source's verdict writes hacked. Can you please tell me what's wrong with it? It's code is 139283121. Thank you!
Bye 2021
nice round, first time solve all problems in div3
If I am successfully able to hack someone's code in Educational or DIV3 rounds , then what will happen ? my penalty will decrease or not ?
Nothing happens, it won't improve your score or rank.
No
.
my Friend is introvert so , he couldn't ask saransh_singh
lol
Well your penalty won't change but if some people hacked solutions of people with rank better than you , then you might see your rank improved
I got frustrated from problem B. I read statements carefully, but it seems like I still don't understand what do they want from me. Why my code gave MLE? Of course while is infinite, but still how is that possible? How can I have more than 1 "unconnected" bigrams.
NVM, I found an error. Now I feel more stupid. I guess I should've slept more lol
Why time limit for G is 4.5 seconds?
The obvious solution is $$$O(nlogn)$$$ and runs in 265 ms for me.
In Reverse (F problem) how can we turn 23 to 59?
0 1 0
I participated in this contest and got 2 questions correct but still, I am unrated. This was my first contest. So will I get ratings or not?
Yes, you'll get rating.
Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.Wait for the system test.
according to post:
To qualify as a trusted participant of the third division, you must:
if this is your first rated contest, I don't think you will be rated.
untrusted != unrated
I participated first time and solved 2 questions. Why am I unrated?
Wait for the system test.
First time to participate and solve 6 problems. Wish I can be better in the future.
how much time rating change will take after system testing??
I still get the rating now,I feel so confused
i refresh page frequently o.o
Hi guys I need some help with problem D.
https://codeforces.me/contest/1618/submission/139363593
I seem to be off by 1 in the test case and I can't seem to understand why. Much appreciated.
Your solution seems to be matching up a_i with a_{i-1}, which is incorrect. Try this test input: 1 5 2 1 2 2 3 3
correct answer is 1, your solution gives 2.
I am surprised that there were very few pretests for problem D and how my 1st sol passed. The solution which I submitted for the first time should have given RTE in the pretests itself as I took it=s.rbegin() and then decremented it by 1, which is clearly outside the bounds. This solution is completely wrong, isn't it?
my solution is same as you
and I got FST too :(
I don't know why this logic doesn't works can someone help on this?
https://codeforces.me/contest/1618/submission/139284177
It is not optimal to choose neighbouring elements. Eg: 1 1 4 5.
You can refer to the editorial.
for 1 1 4 5 my algorithm answers 0
Ok, I misunderstood your code. st ignores the actual values, which causes the in-optimality. So for instance in the test 4 of your submission, 11-22 or 11-33 or 22-33 are matched, which leaves a count of 1.
Thanks
my solution is same as youNo, it's quite different. You just decremented the two largest values with each other which I think is not a correct way to do, you should decrement both numbers by 1. Also, break when the size of set <= 1
I don't know why this logic doesn't works can someone help on this?Testcase is small, you can check it manually.
i am waiting to become a cyan by this contest
Why did they roll back the rating?
Where is the solution to the game
hi, i was using 2 personal accounts(the other one is @prakylovesgym) of mine for submissions to avoid errors and penalties since i had very slow internet and it was taking a lot of time to compile the program, i please request you to consider my submissions this time and provide me with my rating this one time, i shall not repeat this again.
How slow internet connection can be an excuse for submitting from two different accounts? How are they related? Anyway, it's your fault.
bruh please! i was using my college wifi and it had died, this one time please consider my actions and please get me my ratings back, i can give the password of the other account as well.
Don't cry if its your 1st or 2nd time the contest would be unrated for you.
it's not. is the entire contest unrated? else please get me my rating T-T
The contest is rated, but submitting same code from 2 accounts is violation of rules, so the contest will be skipped for you. Try not doing this in the future. GL :)
I got a message from system that my code (EsmuBeediigs/139243190) coincides with submissions vivecod/139296713 and IITiansuyash/139308628 . No cooperation had happen, since I didn't publish the code online, nor do I know these users. How should I proceed?
Because, you are new I think you had used ideone or any other online editor. And they copied your answers from there. But your answers are not skipped and their answers are skipped. I think you are safe.
I compiled my code locally. The submissions reported to coincide are quite different. And this is in fact just a coincidence. Anyhow, I thank you for taking your time to respond to my comment.
Yes I saw the solutions. They are different. But you are safe I think so.
Did the rating change for anyone in code forces wrt to this contest For me it still did not got updated
yea they took back the ratings.
I really don't know how the code is the same between me and it This will be the first time for me to encounter such a problem, and God willing, it will not happen again
Мне пришло сообщение о том, что мой код находится в подозрении на плагиат. На задачи E и F. Но такие задачи является "баяном" и их похожие разборы есть в свободном доступе. Основываясь на них, можно написать очень похожий код. Прошу пересмотреть мои отправки на эти задачи.
Hey MikeMirzayanov BledDest, I got these 3 messages 2 hours ago.
Attention! Your solution 139256876 for the problem 1618D significantly coincides with solutions Mayur9agt/139256876, Anumish/139287249. 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://codeforces.me/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 139250426 for the problem 1618C significantly coincides with solutions Anumish/139238842, Mayur9agt/139250426, genisis2002/139275622. 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://codeforces.me/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 139228636 for the problem 1618A significantly coincides with solutions genisis2002/139227247, Mayur9agt/139228636. 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://codeforces.me/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 haven't used any online IDE or compiler, nor did I copy the solution from anywhere. I even don't know any of these persons, not in real life nor on Codeforces. The questions were pretty simple & so there's a very high chance that the logic might be same for two different individuals. But the code is almost different if you manually check. Even my logic is same as that of editorial, that doesn't mean I got access to editorial beforehand. It's just a coincidence that the logic matched. I don't know what else can I give as a proof. Please look into the issue, hoping for a resolution.
problem F.
getting MLE on test case 1.
I have explained my approch in comments in submission
Please tell what is wrong.
thanks in advance :)
The problems are really interesting, I love it!