Всем привет!
Сейчас проходит первый тур Открытой олимпиады школьников по программированию, а уже завтра состоится второй. Олимпиаду подготовила Московская методическая комиссия, известная вам также по Московской олимпиаде школьников по программированию, Московской командной олимпиаде и олимпиаде Мегаполисов (раунды 327, 342, 345, 376, 401, 433, 441, 466, 469, 507, 516, 541, 545, 567, 583, 594, 622, 626, 657, 680, 704, 707, 727, 751).
Открытая олимпиада составляется из самых интересных и сложных задач, которые были предложены многочисленным коллективом наших авторов, поэтому мы решили провести рейтинговый раунд Codeforces, который состоится 06.03.2022 12:55 (Московское время) и будет основан на задачах обоих туров олимпиады. В каждом дивизионе будет предложено 6 задач и 2 часа на их решение.
В связи с этим мы просим всех участников сообщества, участвующих в соревновании, проявить уважение к себе и другим участникам соревнования и не пытаться читерить никоим образом, в частности, выясняя задачи у участников соревнования в Москве. Если вы узнали какие-либо из задач Открытой олимпиады (участвуя в ней лично, от кого-то из участников или каким-либо иным образом), пожалуйста, не пишите раунд. Участников олимпиады мы просим воздержаться от публичного обсуждения задач. Любое нарушение правил выше будет являться поводом для дисквалификации.
Задачи соревнования были подготовлены cookiedoth, shishyando, gmusya, Tikhon228, ligaydima, Siberian, isaf27, I_love_myself, talant, KiKoS, _overrated_ под руководством cdkrot, vintage_Vlad_Makeev, GlebsHP, Zlobober, meshanya, ch_egor, grphil, voidmax, fedoseev.timofey, Endagorion и Андреевой Елены Владимировны.
Спасибо gop2024 и KAN за координацию раунда, перевод условий и подготовку задач для второго дивизиона, а так же MikeMirzayanov за системы codeforces и polygon, который использовался при подготовке задач этой олимпиады.
Также спасибо low_ и Jeffrey за предоставление дополнительных задач, которые помогли составить (я надеюсь) сбалансированный проблемсет для раунда.
Всем удачи!
Заранее сообщаем, что из-за проведения официального соревнования исходные коды других участников будут недоступны ещё час после окончания раунда.
UPD1: Победители!
Div. 1:
Div. 2:
UPD2: Разбор
good luck everyone! :)
As a supporter I'd like some contribution pls thanks ^^
"Notice the unusual time"
"Notice the unusual time"
My favorite part of a Moscow round is seeing this list grow one number longer.
My favorite part of a Moscow round is problems with n <= 10^9 with n*sqrt(n) intended solution and Time Limit of 0.1 seconds.
Dear contest, I know that you and your siblings feature beautiful problems under short periods of time, which proves to be quite challenging. As a result the rating dropping haters downvote your announcement. Please try not to take this very seriously. the haters don't know what they are doing.
Regards, that one random contest orzer (and rating admirer)
Unlike other cf rounds, this one doesn't have testers
I now firmly believe that words have power and can change life, I got FST on B :'(
gl everyone! My first round with green rating, hopefully i dont lose it after this one :)
don't get your hopes too high on this one, GL :)
Another Div $$$0.5$$$ / Div. $$$1.5$$$ round?
Actually, your prophecy has come true!
So much contest this week :)
Intresting!!
How many tester you want to make good prestests.
Admins : Yes
Notice the unusual time (is quite usual these days) :)
All the best everyone, have a positive delta!
The unusual timing struck back but fortunately, this time it's a Sunday.
Unusual time with unusual 20 minutes delay
Boycott russian olympiads until the war is over! How can they casually host an informatics olympiad while Ukrainian schools lie in ruins? snark already shows his solidarity by postponing GPs, you should do as well
Everyone understands your concerns, but I don't know how it is going to help.
When we will get score distribution for the contest??
Only 40 minutes left, And the score distribution haven't been published!
6 min Left and still no score distribution !! Does Anyone has idea What's going on
And the contest was over, still No score distribution
Good luck everyone!!!!
first contest without score distribution? or waiting more delays?
good luck everyone!
SCORE DISTRIBUTION?
А как вам хватает совести делать контесты во время войны с Украиной?
А что еще они должны делать.. Авторы с большой вероятностью никакого отношения к войне не имеют, и они просто выполняют свою работу и никто их не должен в этом упрекать.
Сказали бы Вы всем остальным людям в России которые выполняют свою работу вне военной сферы остановиться?
Damn!! what a contest..Hardforces.. Logic for B??
Sort the array. Take the sum of all elements except the last one. For one football, this sum should be greater than the largest element. Else the count is the difference between those 2.
isn't this the logic for A?? i want B
Corner case: if all elements of the array are 0, print 0.
Else, Calculate the sum of the array and call it s. Let ans be 1.
Then iterate through the array and make ans equal to max(ans, a[i] — (s — a[i]));
The idea is that, for each player, you cannot make him pass the ball to himself again but only to the other players, and that means that for one ball, he can do only min(a[i], s — a[i]) passes. For the rest of the passes he has to kick another ball for each hit.
More than that, we have to consider only the maximum of the array. The following code passes:
sort the array and if a[n] > 1+a[1]+a[2]+...a[n-1],the answer is 1+a[n]-(a[1]+a[2]+...a[n-1])-1,otherwise you can always use at most one ball to complete the session,the answer is 1 or 0.
If the highest value — 1 <= rest, then answer is 1.
Else while (highest value — 1> rest) { highest value -= 2; rest -=1; ans++; }
Problem C & D , both seem very interesting.
Any hints on how to solve C? Also , can D be solved using two pointers method? if so then how , or any other method of solving , if you can help, Thank you !!!!
For C, it seems to be summing the same colors so that we only deal with a row vector and a column vector.
Do you see how you can solve this in 1-D?
Try to think in the way we calculate prime numbers using sieve
How to solve Div1B?
brute force from 1 to sqrt(C)
Sort a. Now, for each unique a_i, iterate over all possible quotients k when a_i divides some a_j. So a_j has to be between [a_i*k, a_i*k + a_i-1]. Check if there is any number in this interval using binary_search. If k is not found in a and there exists an a_j in given interval then "No". I wonder if this would TLE on system tests.
Let us assume that the value of floor(x/y)=a.
Then the maximum number of distinct values of a for any fixed y is c/y.
We can bruteforce for all pairs of y and a in ClogC. Once we have bruteforces we have to find if any other number from the array(i.e. x) gives us the required dividend a . This can be done using prefix sum of the frequencies.
If you fix the value of x, then if you take the value of y in range x...2x-1 floor(y / x) will be the same. So the solution is very similar to Sieve of Eratosthenes. First you fix the value of x, then you fix y's like (x, 2x, 3x...) and if there is some number in range [y,y+x-1] you should check whether (y/x) also appears in our array. You just can calculate cnt_x for every x and then calculate prefix sums on this array. Sorry for my bad English.
Bro can you help me...I did the same still tle 148674159
Instead of the map you can use something like a frequency array
Now it's showing tle on test 3 148682603
Now it worked after using unorderedmap 148682987 What was the difference in map/unorderedmap/freqarr ?? map and freqarr didn't work. But u_map worked :|
Problem statement: The array is good if for each $$$x$$$ and $$$y$$$ (s.t. $$$y \geq x$$$), $$$\lfloor{y/x}\rfloor$$$ should be part of array as well.
First, the number 1 should be present in the array.
For every number $$$x$$$ in the array, the number of elements $$$\lfloor{y/x}\rfloor, \text{where } y \geq x$$$ is at most $$$c/x$$$ where $$$c$$$ is the largest value in the array.
If we just iterate for each $$$x, y$$$, the time complexity will be $$$\mathcal{O}(n^2)$$$.
Instead we can iterate on $$$x, j$$$ where $$$1 \leq j \leq c/x.$$$ For a fixed $$$j$$$, if there exists a number $$$y$$$ s.t. $$$\lfloor{y/x}\rfloor = j$$$, then $$$j$$$ must also exist in the array.
The condition to check if there exists a number $$$y$$$ s.t. $$$\lfloor{y/x}\rfloor = j$$$ can be translated to check whether there exists an element in the range $$$[j * x, j * (x + 1) - 1]$$$. This can be done by prefix sums.
Overall time complexity of this algorithm will be $$$\sum_{x=1}^{c} \lfloor{c/x}\rfloor $$$ = $$$\mathcal{O} (c \log c)$$$
Why 1 should be present in the array?
Answer should be yes whenever we have 1 in our array.
Almost straight up bruteforce in $$$O(N\sqrt{C})$$$ passes: 148611843
UPD: I am not sure about correctness of this approach, if someone could prove it or hack it.
I thought $$$O(10^{6}\sqrt{10^{6}})$$$ $$$=$$$ $$$1e9$$$ gets $$$TLE$$$ $$$:/$$$
Hey, can you explain the j<i&&j*j<v[i]; part in your code, please? How can I differently type that? I tried to do D like you, I just changed that part, but it fails on 31st test.
Rephrase it as: check only first $$$X$$$ numbers, where $$$X = \sqrt{v[i]}$$$
You can rewrite it also as: $$$j < min(i, \sqrt{v[i]})$$$
Looks like my D is $$$O(M \log^2)$$$ but barely fits within TL on pretests. I should be able to make it $$$O(M \log)$$$ but I already spent way too much time on it and was rushing to save at least some points.
Problem B was confusing!
5 seconds before the end of the contest, I clicked the submit button and... my solution was not sent... Sad...
Div2 A wording could have been better. I got WA and couldn't solve the problem because I thought we could make multiple jumps just could not repeat jump of size x.
SAME XD , i forgot to notice that we can only jump once, resulted in 4 WA's thinking what am i doing wrong.
it was written in bold so problem writers cannot be blamed for it :D
Yup ::_;; my eyesight too bad xD
this part is in bold "no more than"? what does that even mean?
It would be much clearer if this part was bold "you can make a non free jump only once"
no more than one means either 0 or 1
wording could have been better? it's literally there, they just put no more than in bold instead of once, your reading should have been better
Both D and E are hard to implement .
Totally agree!!!
I am still debugging my 300+ lines in D...
Div 2A should've been translated better, the statement was complicated man ;(
Exactly , use a better translator , not solving A within first few minutes really spoils the mood
What even was B? Looked very confusing. Almost cried seeing 4k people solve it and here I was without even any direction T_T
I made video Solutions, for Div2 A-E
No more contests in unusual timing please. It conflicts with many people's routine and only a few people participate. Also contests around this time turns out to be bad
I am curious to know, on what basis are the timings of a contest decided? Is it according to the availability of contest admins & testers (for clarifying problem statements etc.)?
factorial[0]=0... I failed problem E. f##k. https://codeforces.net/contest/1649/submission/148602004
how to solve div2 c?
calculate fox x and y
thank you,I think I get it
calculate ans fox x and y seperatly
colorx[i] — list of coordinates x with color i
sort(colorx[i])
ans +=sufcolorx[i][j] — colorx[i][j]*(colorx[i].size()-j+1);
Div1C/Div2E looks like a somewhat classical problem, but i could only think of a quadratic solution. Could anyone give me some hints?
My idea: calculate # of strings such that the first i characters from each one are equal to the first i characters of t. then, i+1-th character from every string must be lexographically smaller than the i+1-th character of t. You also have to use a data structure like bit to know how many "good" characters there are for each i and compute modular inverses for some products.
i used segment tree for problem E
Implementation contest :(
Div1F doesn't seem so hard(If it's correct that after contracting three-edge-connected components as single nodes, the graph would be a cactus.), but it requires tooooooooooooo much implementation.
It also needs some effort to code Div1E.
Where is the Solution？
In Problem F, I figured out how to solve the problem on cacti, but do not know how to find 3-edge connected components :)
My opinions:
All problems are decent OI-style problem, but E and F just do not fit into Codeforces contests due to implementation issue. It will be better to make F on cacti.
You can find it in Library Checker. lol
Why does this TLE?
https://codeforces.net/contest/1649/submission/148571491
It's O(n)
EDIT — it AC'ed now, unsure why it was TLE earlier.
Next time try to store sum(l) and max(l) so you only compute them once
Well, I am so sad of getting FST on B -__-, Why weak pretests :(((
Why there's no test of maximum n in pretests ?? Why?? I just changed maxn to 1e5 and it got AC :(((
What the ridiculous test in Div.1 C, if you don't take modulo in the end, you will print
998244353and get fst. :(I couldn't imagine that someone can come with such a test so I just ignored it during the round :((
It's a common thing though and happens all the time in EDU rounds, as such tests are not that hard to come up with. I remember sum did a whole lot of hacks in some recent EDU using this modulo flaw in a couple hundred solutions.
Almost half of my friends are hacked because of it.fortunately,I didn't lock the problem...
thanks for STRONG pretest!
I can't find some sort of report button in messages. Should I report that somewhere and in what way?
Send him your code for B now. Also, don't forget to apologise for not sending your code during the contest. :D
Why people are so desperate .. Come on man work hard and be proud of yourself . This guy surely don't have any self respect . Got left ignored for whole contest . Damn guys Life ain't that easy. Don't make it more easier ..
148588961 I had FST in a test already had on pretest (test 13) ???? MikeMirzayanov can you rejudge my submission pls. 148606321 I have accepted after contest with exactly code
Same with me.
https://codeforces.net/contest/1648/submission/148554934
https://codeforces.net/problemset/submission/1648/148608334
I would like a rejudgment please MikeMirzayanov.
Same. 148582657 148611197
why so many downvotes ?
Although I got fst on Div.2 E, my ranking didn't drop a lot, because many ahead of me got fst too. I think this contest showed a good way to deal with the problem of too many people fst.
But on the same problem, Div.1 C, I was not able to keep my rank after getting fst. I'll end up getting a negative rating change. :(
What is fst?
148593938
Can some one hack this?
Or is it correct?
Done
Could you please hack 148593938 as well?
done
weak pretest TAT
Good contest and very good balance, ths
I think Div.2 B is an interesting problem. In my opinion it's even more difficult than C,D and E. I spent more than 40 minutes on it. :D
~[retracted]~
Maybe you solve such problems for te first time.
how to solve 1D using segment tree. plz help
Back to Master again,Thank you :)
:D
weak pretests in problem D. I use this code to pass the pretests.
In this statements,the elements in the vector aren't changed,and I suppose it changed and do something else. It passed the pretests,but fst on test 24.
D: rewrite the objective function as "maximize{$$$l<r$$$} $$$a_l + b_r$$$ — (cost to cover $$$[l, r)$$$)"
I used divide and conquer to cope with the restriction "$$$l<r$$$" in each step, make graph with edges
$$$l$$$->$$$r$$$ with cost $$$k$$$
$$$x$$$->$$$x-1$$$ with cost $$$0$$$
S->$$$l$$$ with cost $$$-a_l$$$
$$$r$$$->T with cost $$$-b_r$$$
calculated the shortest path from S to T In order to shrink time complexity, I had to care edges outside $$$[l, r)$$$ (only $$$\mathrm{O}(r-l)$$$ edges have to be taken into consideration)
Idea itself was interesting to me, but implementation was too heavy for an almost retired person.
to a graph，nice idea！
We found a lot of interesting solutions to this problem, almost half of participants' successful submissions (it was like 5 out of 10) on the olympiad had it's own approach. And all of those solutions weren't easy to code as well.
contest is good , except some meaningless corner case which leads to FST
Div1.D has pretests that suck
Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!
Codeforces is not trash bin.
How to hack problem C in div 1?
How to make the answer multiple of $$$998,244,353$$$ ?
DeCantor Expansion
O！ Thanks a lot!
ya problem setters really love weak samples and pretests... i dunno the reason.
jiangly's codes are so clean ...like seeing latex text
Did someone understand what is special in test 53 in div1 C? I can't get it for now
You have used break before making ok = false.
I made a submission for problem A. Link I am confused as to why it's failing for the testcase:
I think its answer should be 4 but it's given 5. Can someone explain how 5 is the answer for this testcase ?
you can only make one jump.
You can make exactly one jump This video editorial might be helpful
Cannot describe it with any words.jpg
Здравствуйте! У меня на сегодняшнем раунде упала задача D(div 2) на 13 тесте, хотя 13 претест она прошла. После контеста отослал такой же код, и задача зашла. Посылки: 148606610 и 148579156 Можете пожалуйста перетестировать
can somebody just explain what does the problem A means; i am not understanding when is free and when is not; Are the jumps free onle at ends;
If you are/were getting a WA/RE verdict on any of the problems from this contest, you can get a small counter example for your submission on cfstress.com
Problems added: "A, B, C, D, E, F" from Div-2, which translates to "A, B, C, D" in Div-1.
If you are not able to find a counter example even after changing the parameters, reply to this thread, mentioning the contest_id, problem_index and submission_id.
problem A really bad statement..
My exactly same code for div2 D got TLE during system test and AC after the contest, can this be rejudged? :'(
Hello, please hellp me. I need a hint for problem C. I have no idea
try to solve it for x and y separately
you can get a list for each color using map/unordered map (i used map) then you iterate through the map and do following thing:
At first, you have to notice that all points of the certain colour are already sorted by x; you can calculate the distance from the first point, then calculate for others using that value then you have to sort all the points by y and do previous steps again
i didn't explain the whole implementation, but you can see my submission there: https://codeforces.net/contest/1649/submission/148590975
thank you so much, I'll try to implement
good luck!
what are the downvotes for on the post this time? did just a lot of people not like the div2A statement?
Weak pretests perhaps? There were quite a bit of people getting FSTed in Div1C.
I have a question in problem A div 2 why this case result is 5, not 4?
6
1 0 1 1 0 1
Because you count the land on which you jump too.
If it was 4, then it would count that you jumped on the 0 (that is on position i = 4), not on 1 (that is on position i = 5)
thanks so much
You're welcome buddy :D
Thanks for great round!
Can anyone tell me in Div2 problem D why answer of 1 3 3 7 should be no as 3/1 = 3 which is present in the array.
any pair... 7/3=2 not present in the array
Thanks, I thought that if any pair satisfy the given condition then array will be integral array
I think i have used ideone in public mode by mistake because i dont have idea that someone can see my solution there thats why my solution has been copied by somebody
I tried running my code on ideone in default setting and someone copied my code and I was not aware about that.