Всем привет!
В воскресенье пройдет Московская олимпиада школьников для 6-9 классов. Олимпиаду подготовила Московская методическая комиссия, известная вам также по Московской командной олимпиаде школьников по программированию, Открытой олимпиаде школьников по программированию и олимпиаде Мегаполисов (раунды 327, 342, 345, 376, 401, 433, 441, 466, 469, 507, 516, 541, 545, 567, 583, 594, 622, 626, 657, 680, 704, 707, 727, 751, 775, 802, 829).
Раунд состоится в 12.02.2023 11:35 (Московское время) и продлится 2 часа. Обратите внимание на нестандартное время начала раунда. Раунд будет проведён по правилам Codeforces и будет рейтинговым.
В связи с этим мы просим всех участников сообщества, участвующих в соревновании, проявить уважение к себе и другим участникам соревнования и не пытаться читерить никоим образом, в частности, выясняя задачи у участников соревнования. Если вы узнали какие-либо из задач МОШ (участвуя в ней лично, от кого-то из участников или каким-либо иным образом), пожалуйста, не пишите раунд. Участников олимпиады мы просим воздержаться от публичного обсуждения задач до окончания раунда. Любое нарушение правил выше будет являться поводом для дисквалификации.
Задачи соревнования были подготовлены Tikhon228, TheEvilBird, Ormlis, vaaven, Gornak40, Honey_Badger под руководством vaaven, grphil и Андреевой Елены Владимировны.
Спасибо Artyom123 за координацию раунда и помощь в подготовке задач, а так же MikeMirzayanov за системы Codeforces и Polygon, который использовался при подготовке задач этой олимпиады.
Спасибо BucketPotato, KseniaShk, NemanjaSo2005, MagentaCobra, kuertov, prvocislo, 4qqqq, vsinitsynav, FynjyBath, qualdoom, ivanlarin, didedoshka, petyb, PBBx0, Mikhango, charlyk, RP-1, talant, ak2006 за тестирование.
Заранее сообщаем, что из-за проведения официального соревнования исходные коды других участников будут недоступны ещё час после окончания раунда.
Всем удачи!
UPD: Разбалловка: 500 — 1000 — 1250 — 1750 — 2500 — 3250
UPD2: Разбор
The round will be held according to the Codeforces rules and will be rated for both divisions.Shouldn't it be rated for Division 2 only?Shhh, I’m desperate for a rated contest
Like me!
As a tester I can say that I am a tester (again). Don't hurt me, I hope this time everything will be fine.
testers are so cool!
Thanks, hope we don't let you down!
o.O
Nice avatar
thanks(
Forgot to switch the account back?
As a tester, I enjoyed the problem set.
What will be the distribution of points?
Sorry, saw your message late. It is not testers who decide that. As you can probably see, the author made an update to the blog, the distribution is: 500 — 1000 — 1250 — 1750 — 2500 — 3250
Aiming for first 3 problems then!
Let's see how it goes :)
I just could not figure out what was wrong with problem A.
This was my solution:
ll promotions_available = (n * m / (m + 1));should bell promotions_available = (n / (m + 1)) * m;I found some errant cases for you.
TL; DR -> a = 6, b = 5, n = 9, m = 4, expected output = 44; your output = 45
You can use the following code for the same.
Run the generator and save the input in a text file. Use that input to get output from your code, as well as AC code.
Compare the two and debug. Note that this can be done efficiently with scripts. I don't have windows scripts on hand right now, but it's easy with Linux.
As a tester I can say that problems are very interesting. Have a good luck on this round:D
Note the unusual time i.e. 6hrs before general time.
is score distribution going to be announced before the contest?
also can it be delayed ? it clashes with Innopolis finals time
It can't be delayed since it has to be held during Moscow Olympiad for Young Students.
Я буду писать завтра МОШ, пожелайте удачи)))
Удачи!
Спасибо))
Удачи!
Спасибо!
Удачи)
Спасибо!!!
Ну что ж, 319 баллов, писал я за 9-ый класс, хотя сам учусь в 8-ом, поэтому я считаю, что результат у меня похвальный
всем удачи на раунде!
Fingers Crossed for +delta (◠‿◠)
Don't cross your fingers, it will be difficult for you to type during contest. (◠‿◠)
I will solve this olympiad. Good luck to everyone at the round and the olympics!
Friendly time for Vietnamese like me
And Chinese like me
eagerly waiting for a rated contest . Good luck everyone !!
is this china mathforces round or am i safe?
I am looking forward to the problems of this contest, hoping to surprise me.
I hope we can enjoy ourselves in this contest.Make it Sunday, February 12, 2023 at 16:35(UTC+8)
This is at midnight for me. Hopefully I don't brick it :/
I have classes T_T... But still good luck awa
Hoping to have a great round with great learnings!
hope the best for all and to get my cyan color today :)
Edited okay I think I will wait for my cyan for another day :D
Good luck everybody, hope problems will be interesting!
самый ужасный раунд за историю
Is the other contest still ongoing?
Such a permutationforces.
The problem F is the same as 765F.
My code was copied from https://www.luogu.com.cn/problem/solution/CF765F.
Edit: Please don't upvote this comment.
I don't understand why you upvote this. Firstly,if you notice that a problem is similar with another one in the past,keep it for yourself and don't spoil the contest. Second of all,saying that you copied your code from a solution source is against the values imposed by codeforces(ig).
A funnily embarassing contest for me -- A >> B > C for me. I solved the problems in the order C, B, A and got 5 WA on A before getting it. My math solution had a bug I couldn't find, so I tried to binary search the amount potatoes to buy for 'a' coins, which obviously didn't work. Then I thought the function was unimodal, so I tried ternary search on the potatoes, which still didn't work! Finally, I decided to scrap my mess of a code and prove a solution on paper and then implement it. It was less stressful after the 4th WA anyways, since I already hit the maximum penalty for a problem... Finally I solved Problem A, 76 minutes into the contest! I am proud of my persistence and disgusted at my stupidity.
I used binary search for A and it worked. Have no idea how to solve it normally though...
I did the case work on paper: let mx be the most multiples of (m+1) that we can buy without overbuying. Then the answer is the minimum of {n*b, (mx+1)*(a*m), (a*m*mx)+(n-(m+1)*mx)). I wish my binary search solution worked so I could have solved it earlier.
OMG, B is so hard, can anyone explain the solution problem B for me :((
I didn't prove it, but I solved it in a few minutes by greedily going max_sum, max_sum-1, max_sum-2... min_sum, min_sum+1, min_sum+2.. max_sum-1. I was surprised it worked.
Thank you so much. The sad contest, I can't solve B.
Same. I'm beginning to question my ability to make observations :(
Note the length of the array is always
(x-y)*2.I couldn't figure that out, I just had a counter and incremented it by 1 every time I outputted a number lol
n = (x — y) * 2. That's because local minimum and local maximum are alternating(x1, y1, x2, y2, x3, y3, ...(that's quite easy to prove)) which means that the quantities of minimums and maximums are equal(that's unimportant to the solution, it's just an interesting fact). So with this information we can easily count n. Lets look at slice [x1...y1..x2). We can easily count the quantity of all elements in the slice [x1...y1...x2): n = x1 — y1 + x2 — y1. Then add n to answer and do such thing till you return to your first slice. We can see that the final result will be ans = 2 * x1 + 2 * x2 + ... + 2 * xm — 2 * y1 — 2 * y2 — ... — 2 * ym = 2 * (x1 + .. xm — y1 — ... — ym) = 2 * (x — y). Finally, we can easily create an appropriate array with only 1 maximum and minimum which are equal x and y.
How to solve F?
I tried Mo's algorithm, but it won't pass the time-limit. Any nice optimization required in Mo's algo?
Idk if it will pass or not but anyways you should try this optimization: Optimization with Hilbert curve
Bricked B and then couldn't submit D in time.
Seems that last problem is very popular.
last problem is a copy of 765F - Souvenirs
the n = 2 case in B is very stupid
agreed i am surprised that the answer for the case when x — y = 1 is just an array of {x , y} :((
statement so unclear and stupid
Make it unrated, unless you play too much genshin.
Why Genshin out of nowhere...
it's just a joke hhh
Best contest I have ever seen!..
what even is pretest 6 for problem D? i tried to use segment tree type of answer and i still don't know the corner case (that or i somehow fluked the 4th and 5th pretest lol). Also tricky problem A ;)
I mistyped min to max when initializing prefix min of positions. However it also squeezed into the first 5 pretests:(
Segment Tree seems pretty overkill for D. My strategy was to count the #of subsegments such that they share a common MEX by iterating over the MEX value and using 2 pointers to handle everything. I got it to pass the example cases too. Wish I could have submitted it :(
Edit: It got accepted. Here's the code if anyone's curious: 193333734
One tip is to write a brute force solution for D and compare your submission with the brute force solution.
I started by counting solutions with subsegments not including ones, then includeing 1s and not including 2s then includeing 2s and 1s not including 3s ... I used combination for counting this stuff which you can make O(1) easily, so my approach is O(n) which passes(and passed).
note that i used my template here and used cpbooster to parse and submit the code so there are a lot of unnecessary lines. you can assume that solution starts from void solve()
did u find what is pretest 6? mine is also failing
How to do F ? I tried using Mo's algo with sets, but that doesn't feel to squeeze in the TL
just go to https://codeforces.net/problemset/problem/765/F and read editorial
Anyway, is it possible with MO? I have TL too.
Yes, it is possible with MO. To pass time limit, you need super fast set for integers and super fast IO. Check out my code.
Can you copy-paste your code into somewhere else, because currently we're not allowed to look into other's submissions.
Oh, didn't notice that. Code
I solved https://codeforces.net/problemset/problem/765/F with Mo's algorithm: https://codeforces.net/contest/765/submission/164782195.
However, I'm sure my solution won't pass TL in today's problem.
is it sure that F isn't https://codeforces.net/problemset/problem/765/F?
yayy I was able to attempt D this time.. hoping system test pass
accepted :)
My solution to $$$C$$$.
For every element $$$l$$$ as left position, there is minimal $$$k$$$, such that it is required to $$$r \ge k$$$ for $$$l$$$ not to be minimum or maximum. Find all these $$$k$$$ in linear time using stack (note, there can be no such $$$k$$$). Let it be $$$left[i]$$$. Then do the same in other direction: $$$right[i]$$$ is rightmost position, at which $$$i$$$ is neither max nor min.
Now we have to find $$$l$$$ and $$$r$$$ such that $$$l \le right[r]$$$ and $$$r \ge left[l]$$$. Fix $$$l$$$. We have to check, if there is $$$r \ge left[l]$$$, such that $$$right[r] \ge l$$$. We can do this using segment tree for maximum and position of maximum.
Whose solution is longer?
I used two pointers -- while(l < r && flag), flag = false, if a[l] or a[r] = min or max, increment l or decrement r, increment min or decrement max, and set flag to true. Then output l and r as the answer,
Same
I did the exact same thing, even the same variable names.
But it feels like there is a better sol
I have also overkilled! same idea and used 3 sparse table :)
Why is C easier than A and B?
no it isn't
Problem E is just beautiful!
Solution sketch:
First sort array $$$a$$$. Henceforth I assume $$$a$$$ is sorted.
We can prove by greedy exchange that the set of satisfied people form a prefix of $$$a$$$. Now, let's fix the prefix of satisfied people.
Let's maximize the number of distinct books that this fixed set of satisfied people can be assigned such that all have to be read by at-least one person
We can prove again, that:
So for each prefix, we have found the maximum number of distinct books. But the number of books that can be assigned to a prefix is monotonic: if you can assign $$$k$$$ books, you can also assign $$$k-1$$$ books. So if answer for a prefix of size $$$j$$$ is $$$k$$$, update answer for each $$$i<=k$$$ with $$$j$$$. This can be done trivially by maintaining suffix maximums.
193328416
brought a permutation p of length n to the zoo This sentence lol!
What will happen if you try to hack someone's solution with this test x = 1e9 y = -1e9 in problem B?
What will happen if you try to hack someone's solution with this test x = 1e9 ,y = -1e9 in problem B ?
solution exist only for n<1e5 (given) so above case will not have any solution
Yes, absolutely. I think they should have written that the sum of the differences between x and y would not exceed 1e5
First line of the question
For his birthday recently Fedya was given an array a of n integers arranged in a circleLast line of the question
It is guaranteed that the sum of n over all test cases does not exceed 2⋅10^5Im extremely sad. I just solved question D 5 minutes after contest ended. And the even sadder part is that I joined the contest 30 mins late :((. You can tell because I only solved first question after 35 mins. And solved the next two questions almost immediately.
Problem Cjust feels lot easier thanProblem B.bad problem F
Difficulty order according to me: B>A>D>C
I would swap A and D around, but I agree with this lol. Wasted a ridiculous amount of time on B
what was your idea for D that you put is so low on difficulty?
.
my submission
basic idea is with 3 conditions
price on first day is a and price on second day is b
then
if (a < b) ... you should alway buy on first day
if (a > b BUT you can save with a discount ) then you should get discounted items on first day and remaining on second day
else buy everything on second day
Why is problem B such a troll? It says that $$$-10^9 < y < x < 10^9$$$ and the answer has length $$$2 \cdot(x-y)$$$. In my opinion, you should not put this kind of "traps" in Div2 problems, especially in A and B.
First line of the question
For his birthday recently Fedya was given an array a of n integers arranged in a circleLast line of the question
It is guaranteed that the sum of n over all test cases does not exceed 2⋅10^5This is a wrong use of the phrase it is guaranteed.
See this
Meaning 2: Make it clear that this ‘guarantee’ is an additional constraint on the input.
oh, thanks for sharing this. Something for me to think about
Exactly , I was wondering how would i even print such a huge sequence even if i get one :/
Exactly, It had took my lot of time for optimizing number of operations, and I checked constraints on x and y more than 5 times, Also problem statement of A is not well written, it could be written in 2-3 lines. Even F is taken according to me.
Agreed, perhaps the worst Div. 2 B of all time, or at least in recent memory.
I totally agree with this, just this line alone $$$-10^{9} \le y < x \le 10^{9}$$$ can mislead people to think that $$$x = 10^{9}$$$ and $$$y = 10^{-9}$$$ is a valid input, even though the next line says that the sum of $$$n \le 2 * 10^{-5}$$$
And as such leaving their head scratching that there is a better answer than $$$2*(x-y)$$$ for $$$x = 10^{9}$$$ and $$$y = 10^{-9}$$$ that can fit into the given constraint on $$$n$$$, which can possibly cause them to get stuck forever
The problem A is just way too annoying!!
A: Divide n potatoes into floor(n/(m+1)) groups and n%(m+1) single potatoes. The price for a group is min(m*a, (m+1)*b), and for a single potato is min(a,b).
B: Go down from x to y by step -1, then go up from y to x by step +1.
C: Recursion. First, check if [1,n] is a good segment. If not, then a[1] or a[n] will be the max or min value on this segment. If a[1]=1 or a[1]=n, then we need to solve recursively on [2,n], otherwise we solve on [1,n-1]. We do this recursively until we find an answer, or the length of the current segment is <4. Also we need to maintain the max and min value on the current segment.
D: Consider for each possible MEX in [1,n+1]. For MEX=1, we need to find the position of 1 in p and q, and count the number of segments which doesn't contain these positions (which is a subsegment of 3 segments splited by positions of 1), and for MEX=n+1 it's trivial (only [1,n] will have MEX=n+1). For MEX in [2,n], we need to find the minimal segment containing numbers in [1,MEX-1] in both p and q (this segment can be updated by expanding previous segment to contain MEX-1), and find the positions of MEX, we can expand the minimal segment in both directions until it touch these position (also, if there's any occurrence of MEX in the minimal segment, the contribution of MEX is 0).
Can you prove B?
Let the difference between the sum of local maxima and local minima be $$$d$$$, and let $$$n$$$ represent the optimal solution size (note that $$$n$$$ must be even). Assume that $$$d>1$$$ so that $$$n$$$ must be greater than 2.
Consider a local maxima — it must occur as $$$\ldots,x,x+1,x,x\pm 1,\ldots$$$ and now, remove the centre two elements, and we have a new sequence $$$\ldots,x,x\pm 1,\ldots$$$ which has $$$d'=d-1$$$, and a solution with $$$n-2$$$ elements, and reduce.
EDIT: (And a local maxima will always exist)
In A isn't it possible that if we buy x number of the potatoes out of n from a and remaining from b so now we vary this x How can we claim that it is best to divide all n in m+1 groups for a and remaining for b Can't there be any intermediate x out n for which we find the best possible minimum I tried this using binary search but W/A
It's not "divide all n in m+1 groups for a and remaining for b". In fact, there are at least n%(m+1) potatoes we can't buy them by favorable price (so we must buy them by price min(a,b), and we can by at most (m+1)*floor(n/(m+1)) potatoes by favorable price (which is min(a*m/(m+1),b)).
Let c=intmax, l=0,r=n,mid what i am saying is that what if we take i=mid and j=n-mid then we can calculate 'a' for i and 'b' for j
if this is less than equal to c we do r=mid-1 and else we do l=mid+1
i have understood that we can give n%(m+1) to min(a,b), but now it is only applicable when we give (n-n/(m+1)) to 'a', so what i am thinking is if we find certain 'mid' which can give a better result by using same distribution formulae?
I can't understand why you think about binary search. But we can consider problem A atart anew:
--Consider we want to buy only k potatoes where k<m+1, what's the minimal cost? Well, since k<m+1, if we buy them on the 1st day, the price is k*a, on the 2nd day the price is k*b. Therefore, the minimal cost is k*min(a,b).
--Consider we want to buy only m+1 potatoes, what's the minimal cost? If we buy on the 1st day, we need to pay m*a since the promotion, and on the 2nd day we need to pay (m+1)*b. Therefore, the minimal cost is min(m*a,(m+1)*b).
--Now consider we want to buy n potatoes, what's the minimal cost? By the previous discussion, we can do 2 kinds of operation:
buy 1 potato, cost min(a,b).
buy m+1 potatoes, cost min(m*a,(m+1)*b).
Since the 2nd operation includes promotion and 1st does not, it cannot be worse than the 1st operation when there're >= m+1 potatoes we need. So we can do 2nd operation repeatly until we can't do more operations (which means, there're <=m potatoes we need to buy). Then we need to use 1st operation for remaining potatoes.
That B problem T_T
Is anyone able to tell me why in problem B, in the first test case where the local maximum = 3 and the local minimum = -2 the solution cant be just the numbers 3 and -2?
It doesn't seem to break any of the requirements? Am i missing something?
My submission to problem B
Am i missing something? : Yes
consecutive numbers should have a difference of 1 :)
The problem says absolute difference and the numbers 3 and -2 seem to have an absolute difference of 1 right?
Or is it that abs(3-(-2)) = abs(3 + 2) = 5 ?
Absolute difference doesn't mean the difference between the absolute values of the numbers.
It is the absolute value of the difference
it's the latter one sadly
Can someone show testcase 6 in D?
Check this case:
answer = 10
my answer is 10, but thanks
my code passes this and the samples but fails tc 6 lol
Check this case:
6
4 1 2 3 5 6
5 6 4 1 2 3
answer = 6
also correct, Im waiting for open submissions ;d
OMG,D is so hard,can anyone explain the solution of problem D for me :(
FOR（MEX，1，n+1） { Find Range of L in this MEX Find Range of R in this MEX answer += len of Range_L * len of Range_R } you can solve MEX=i by MEX=i-1
The fact that there are people who failed to solve D, but were able to solve F in under 30 minutes :)
Why is this getting downvoted, the round was pretty nice?
Cause F problem was present in previous contests. Most probably round gonna get unrated
This round will not get unrated, Mike did a very good blog post as to why it won't get unrated.
I managed to solve A-D and I have to say I quite liked all the problems. Sadly, I did not look at E.
Problem B give me [-1e9;1e9] and so I say: Nani? How I can minus one with range 1e9 LOL? Finally, I solved it by subtracting the value by 1 and it worked XD! Sorry for my english !
I spent nearly an hour on problem F but now it coincided with another problem in the old round. I don't have time to solve D and E. /kk
you can check the video editorial for
problem C: https://www.youtube.com/watch?v=39LiI3MKack
problem D: https://www.youtube.com/watch?v=H-7tJaW7crI
Подскажите, а почему данное соревнование не является для меня рейтинговым? Я решил 2 задачи, и думаю что для моего рейтинга я заслуживаю крупицы рейтинга. Где они :$ ?
Потому что это раунд для Div.2. Молодец, что решил, но нужно сначала попасть в Div. 2.
Так дождись,когда рассчитается твоё место и будет тебе рейтинг :)
Even without considering the problem F has appeared in the past round, I think the problems(ABCD) are simpler than usual.
Even without considering that the problem F has appeared in the past round, I think the problems in this round is simpler than usual.
statement B has the worst explanation ever, like I spent the whole contest trying to figure out the solution for the case x = 1e9, y = -1e9, the author should have listed in the statement that the differences between x and y doesn't exceed 2e5.
I spent almost 40 mins for solving the problem B for the given constraints. Finally left the contest. One of the worst contests in recent times.
two-pointer forces :).
The objective of the last problem is fairly simple, (not the solution, just the objective), so it makes sense that a similar problem has already been proposed before.
Imo, this coincidence wasn't the only issue with this round, Speedforces rounds are becoming increasingly common these days; though it was indicated beforehand by the problem ratings, still this isn't ideal.
When will the submissions and testcases open?
When can we see the source codes of others? I'm DESPERATE to see where did I get wrong
In the standings page you can double-click on their scores
I don't think that this one is open yet.
How to solve A? I have tried deperately in contest math, binary search but everytime something got wronged
my submission
basic idea is with 3 conditions
price on first day is a and price on second day is b
then
if (a < b) ... you should alway buy on first day
if (a > b BUT you can save with a discount ) then you should get discounted items on first day and remaining on second day
else buy everything on second day
when will u update editorial please :o
Is this round Unrated?
Approach for D: For MEX 1: we have to find no. of common subarrays which dont include 1. So lets say of the 2 arrays leftmost 1 is at i, and rightmost 1 is at j then all subarrays forming less than index i, in b/n i and j , greater than j will give MEX=1.
Now for MEX=2 : We have to fix the subarray where 1 is present in both so i to j is fixed. Now check how many common subarrays we can form excluding 2. Here 2 can lie in the opposite direction of i,j or at the same direction. If it lies in b/n i,j so MEX=2, doesnt exist. also expand i,j which will include 2 for next MEX calc
Everyone who has put a dislike has no brains
In my opinion, C is easier than B.
todays order was a > b > c literally reverse
unfair contest
unfair contest
In problem B, the statement "It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2⋅10^5$$$" is misleading since it made me believe that for all possible inputs $$$x$$$ and $$$y$$$ $$$(−10^9≤y<x≤10^9)$$$ the answer will never exceed $$$2⋅10^5$$$ which is obviously not true for $$$x=10^9$$$ and $$$y=-10^9$$$ since the minimal length is $$$2x-2y$$$. This lead me to believe that the expected solution was not optimal enough and that the problem had to be solved with some optimal value that minimized the length in order to not exceed $$$2⋅10^5$$$ by spamming something like $$$\sqrt{x}$$$ and $$$\sqrt{y}$$$ or using binary search.
It would've been much better to either:
Rewrite the statement as "It is guaranteed that the sum of $$$x-y$$$ over all test cases does not exceed $$$10^5$$$".
Lower the constraints to $$$(−10^5≤y<x≤10^5)$$$ (same problem, same solution).
Ask the solver to output -1 if the minimum length exceeds $$$2⋅10^5$$$.
Rewrite the statement and make it clear that you will not actually receive all possible inputs $$$x$$$ and $$$y$$$ $$$(−10^9≤y<x≤10^9)$$$, but rather all possible inputs $$$x$$$ and $$$y$$$ $$$(−10^9≤y<x≤10^9)$$$ such that the minimum length of the optimal solution does not exceed $$$2⋅10^5$$$.
For me this is an inspiring contest with excellent B&E.
And F itself is just a good problem at the wrong time.
None of you done it on purpose,that's enough.I hope that it will not destroy your confidence and courage.
if Mikhango is tester == round is bad