Всем привет!
В воскресенье в Москве пройдет XX Московская командная олимпиада — командное соревнование для школьников, проходящее в Москве как отборочное соревнование на ВКОШП. Олимпиаду подготовила Московская методическая комиссия, известная вам также по Московской олимпиаде школьников по программированию, Открытой олимпиаде школьников по программированию и олимпиаде Мегаполисов (раунды 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).
Раунд состоится в 23.10.2022 10:50 (Московское время) и продлится 2 часа. Обратите внимание на нестандартное время начала раунда. В каждом дивизионе будет предложено по 6 задач. Раунд будет проведён по правилам Codeforces, будет рейтинговым для обоих дивизионов.
В связи с этим мы просим всех участников сообщества, участвующих в соревновании, проявить уважение к себе и другим участникам соревнования и не пытаться читерить никоим образом, в частности, выясняя задачи у участников соревнования в Москве. Если вы узнали какие-либо из задач МКОШП (участвуя в ней лично, от кого-то из участников или каким-либо иным образом), пожалуйста, не пишите раунд. Участников олимпиады мы просим воздержаться от публичного обсуждения задач до окончания раунда. Любое нарушение правил выше будет являться поводом для дисквалификации.
Задачи соревнования были подготовлены Tikhon228, teraqqq, Ormlis, sevlll777, Artyom123, vaaven, Mangooste, Siberian, Alexdat2000, TeaTime, Ziware под руководством Tikhon228, grphil и Андреевой Елены Владимировны.
Спасибо DishonoredRighteous и KAN за координацию раунда, перевод условий, подготовку и предоставление дополнительных задач, а так же MikeMirzayanov за системы Codeforces и Polygon, который использовался при подготовке задач этой олимпиады.
Также спасибо KLPP и TheOneYouWant за предоставление и подготовку дополнительных задач, которые помогли составить (я надеюсь) сбалансированный проблемсет для раунда.
Обращаем ваше внимание, что рейтинги не будут пересчитаны до начала Codeforces Round 830 (Div. 2), системное тестирование также может быть задержано до окончания Codeforces Round 830 (Div. 2).
Всем удачи!
UPD1: Раунд был перенесен на 15 минут. Обратите внимание, новое время начала — 23.10.2022 10:50 (Московское время).
UPD2: Большое спасибо тестерам: Um_nik, dorijanlendvaj, errorgorn, vertig1, Makcum888, iakovlev.zakhar, Kon567889, I_love_geom, golikovnik, mejiamejia, Aleks5d, ak2006, jampm, IgorI! А также команды тестирующие основную олимпиаду: Elderly Passion Fruit (Siberian, alexxela12345, talant) и (maximrufed, omega_alpha, All1gator).
UPD3: Разбалловка:
Div.2: 500 — 1000 — (750 — 750) — 1250 — 2000 — 2250
Div.1: (500 — 500) — 750 — 1750 — 2000 — 2500 — 3000
UPD4: Победители!
Div. 1:
Div. 2:
UPD5: Editorial
As a contestant, Good luck everyone. Hoping for a great and balanced round :).
As a contestant, good luck everyone. Hoping for a great and balanced round :)
I'm actually curious, if a newbie somehow AKs both rounds on the day, will it be a world record on shortest time to get to Expert/CM/Master?
Second Last line hurts me :cried:
So early in the US :(
This contest contains one of my favourite problems I've written, so please participate! :)
Sure, will do
Hoping That Both 829 and 830 will be my best round ever . And I am able to find my Codeforces profile in green :)
I am looking forward to the problems of this contest, hoping to surprise me.
"and system testing may be delayed until the end of Codeforces Round #830 (Div. 2)."
Imagine doing two contests in a row only to find out you FST'd in both, at the same time
Please note that this contest doesn't start at a usual time. And there is also a contest (#830) on the same day. (As I said in #830)
How will Codeforces decide whether or not someone should be rated after round #830? Does it depend on their rating just before #830 begins or after #829 gets rated?
I feel bad for who will participate in this round then get a negative delta and participate in the second one to cover the loss then get also a negative delta
well,
I hope this doesn't happen to me.
Why are you talking about me Sir!
Unusual timing. I hope this round will not be speedforces in 2 or 3 problems like Educationals.
I think 4th on last round were perfectly solvable
it is pupil time
Best of Luck
Thanks for preparing for the contest and I'm very interested for the contest. By the way, couldn't it have announced a little earlier?
If I remember correctly, this contest's schedule was added to the calender three days ago. As div1 contests are not abundant, I try to adjust my schedules as much as possible since the date has been added. Actually, three days ago is too late to make adjustments. Ofcourse I understand there are several reasons why you can't give us notice, but can it be a little quicker? As div1 contests are valuable, we contestants want to participate in as many as possible.
We are very sorry for this. I hope you enjoy the contest =)
I got the news earlier than you, and I knew it before codeforces didn't show the competition on the page. Personally, I feel that it is really necessary to inform the players of the contest time in advance, but there are always some uncertain factors interfering, and I can only hope that these factors play as little role as possible.
As a contestant, I would you and myself good luck and hope I won't lose too much!
Give me downvotes for spending 5 nights for developing my problem. I deserve it.
I'm ready! Good luck to all the contestants
unbelievable to see two contests both with unusual time
I am fortunate to witness two consecutive rounds one after the other both with unusual timings best Sunday ever
I hope I can get back to specialist after this two consecutive rounds :) .
Почему у Андреевой Елены Владимировны нет СF?
I'm not familiar with Moscow Team Olympiad, but will it be an ICPC style contest (i.e., all problems having equal value, no hacking during contest, etc)? If so, this should be specified in the post (as well as what the resubmission penalty is, since the Codeforces standard of 10 minutes is not universal). If not, the score distribution should be posted, or at least a note that it will be posted later (but there is less than an hour before the contest starts...)
It's based on ICPC-style contest (Moscow Team Olympiad), but codeforces contest will be normal.
Why tourist is not participating ??
Stop stalking him.
is this round delayed 15 minutes?
yes, it will start after 20 minutes
Thanks bro
Speedforces is trash.
How in the world >3000 people solved D1B/D2D /:
How to solve Div2D T_T
Problems like those make me question my existence.
what a noob
:((
how to do C1?
You have no zeros so each value change parity of sum regardless of partition. So if $$$n\ mod \ 2 \ne 0$$$ then answer is $$$-1$$$.
Then you can split array in subarrays of length of $$$2$$$. Than you have cases:
So you got correct partition.
C2 can be got by sligtly modification to this, but I spent 1.5 hours to try write this out :((.
C2 is like C1 but it adds +4 cases in your solution which depends on parity of zeros between ones and also you need consider zeros between pairs of ones, the first one and the last one.
How to solve E?
End goal = get $$$K$$$ $$$1$$$s towards the end of the array, where $$$K$$$ is the count of $$$1$$$s in the initial array. Say in the current state, there are $$$R$$$ $$$0$$$s in the last $$$K$$$ positions. (end goal is to get $$$R$$$ down to $$$0$$$)
This number $$$R$$$ can only decrease or stay the same with operations.
Let $$$f(R)$$$ be the expected number of turns to go from $$$R$$$ $$$0$$$s to $$$R - 1$$$ $$$0$$$s. Since our end goal is to get to $$$R = 0$$$, i.e no $$$0$$$s in the last $$$K$$$ positions, we want to find $$$f(R) + f(R - 1) + ... f(1).$$$ $$$(R \rightarrow R - 1 \rightarrow R - 2 .... 1 \rightarrow 0)$$$.
Note that $$$R =$$$ #$$$0$$$ in the last $$$K$$$ positions = # of $$$1s$$$ in the first $$$N - K$$$ positions.
So probability that we go from $$$R$$$ to $$$R - 1$$$ in one turn is $$$p(R) = \frac{R^2}{nC2}$$$. i.e we need to pick a $$$1$$$ from $$$R$$$ $$$1$$$s in the left $$$N - K$$$, and a $$$0$$$ from $$$R$$$ $$$0$$$s in the right $$$K$$$.
That makes $$$f(R) = \frac{1}{p(R)}$$$
Answer is sum of $$$f(r)$$$ for $$$r$$$ in $$$[1, R]$$$ i.e sum of $$$\frac{nC2}{r^2}$$$ for $$$r$$$ in $$$[1, R]$$$.
can anyone explain Why $$$f(R)=1/p(R)$$$ ? sinus_070
If an event occurs on a try with probability $$$p$$$, the expected number of tries to achieve that event is $$$1 / p$$$.
Exp trials = $$$S = 1 * p + 2 * (1 - p) * p + .. i * (1 - p)^(i - 1) * p$$$
$$$S - (1 - p) S = p + (1 - p) .p + (1 - p)^2 .p + ...$$$
$$$p . S = p . (1 / (1 - (1 - p)))$$$
$$$S = 1 / p$$$
Roughly if probability of an event is p = 0.2, we say it happens 1 out of 5 times. For a general p, it's expected to happen once every 1 / p times.
Thank you <3
I am too dumb to solve A. I think B, C1, C2, D are even easier than A.
Would you please review my code: https://codeforces.net/contest/1754/submission/177553775? I stuck at A for 30 minutes but ended up failing to solve it.
same not able to solve A
brother i stucked with B problem
int t; cin>>t; for(int i=1;i<=t;i++) int n; cin>>n; int k=n/2; int s=1; for(int i=k+1;i<=n;i++) cout<<i<<" "; if(s<=k){ cout<<s<<" "; s++; } } cout<<endl; } }
Although here is my solun but i didnt undersatnd at all i can make the more minimum like 4 3 2 1 or its reverse which will give always minmum but after that what is the maximum? i mean which things maximum they have been said? someone said o that 2 3 2 3 this will be the maximum permutaion of 3 1 4 2 5? among of 120 permutation. will anyone please share me how its the maximum permutaion and what is the maxmium of which values? really confused need an experts hand. Thanks
the question is that we have to find such a permutation whose minimum absolute difference of all consecutive elements is maximum . we can observe that this value is n/2 .
for implementation you can refer this 177548133
thanks brother,i appreciated btw your progress was super have any suggestion for this newbie?
regular practice !!
I didn't properly review your code, but I skimmed over it, and you seem to be focused on the chain length for the Qs, which I don't think should be important. Here is a failing test:
Answer should be No, because there are five questions and only four answers.
I'm not sure exactly what your approach is, but you might be overthinking this. Here is a hint for a much simpler solution: maintain a count for the number of unanswered questions while you read the characters. This count cannot be negative. My solution: 177536462
I first-solved on Problem C1, and I got -100 rating XD
Please someone tell me how did you solve D ?? Could solve A,B,C1&C2 in the contest but wasn't able to solve D:( Hope that my rating increases by some significant amount
Merge small factorial to large factorial:
https://codeforces.net/contest/1754/submission/177602806
Do not have too much time to explain because the next competition is coming.
Am I missing some very obvious observation on div 2 D? How does it have so many solves?
What happens when you add 2 factorials? How many x! is needed to make it (x+1)!
So just greedy priority queue would work?
assume $$$a_i$$$ is the smallest $$$a_*$$$ , then $$$a_i$$$ must ocurr $$$k(a_i+1)$$$ times for the whole sum to be divisible by $$$(a_i+1)$$$
Lets take the first sample test for example
6 4
3 2 2 2 3 3
Sum of all factorials of the array will look like:
3! + 2! + 2! + 2! + 3! + 3!
This can be further simplified:
3! + 3*(2!) + 3! + 3!
Now 3*(2!) is simply 3!. So:
3! + 3! + 3! + 3!
Again simplifying:
4*(3!)
Which makes it:
4!
You can see that this is divisible by 4! :)
I will leave the rest little corner cases and observations to you. Good Luck!
This is exactly what I did though, but it didn't pass... I made a map to count the number of occurrences of each element, and then iterated from the smallest to the biggest. If element $$$v$$$ appears $$$k$$$ times, then we can form $$$k/(v + 1)$$$ copies of $$$(v + 1)$$$ (which we add to the count for $$$(v + 1)$$$).
After all this, we check the last element of the map (which has a count of at least 1), and see if it's $$$\geq x$$$. If so, the answer is YES. Otherwise, the answer is NO. My submission: 177595468
I suspect that the failure arises because I did nothing with the leftovers, i.e., the remaining $$$k \% (v + 1)$$$ copies of $$$v$$$. But I don't see how they would influence the result, and such consideration seems really tricky, so are you sure there isn't a more challenging observation that you aren't mentioning?
7 3
1 1 1 1 1 1 2
Note that: 1+1 = 2 = 2!
Thus, sum of array becomes:
1. 1! + 1! + 1! + 1! + 1! + 1! + 2!
2. 2! + 2! + 2! + 2!
3. 3*(2!) + 2!
4. 3! + 2!
Nice, this is most simplified equation, you can get.
And, all that's left is to just check if this is divisible by 3!
What do you need to make the sum divisible by 3!? The sum should be a multiple of 3!.
Can you take 3! common out of 3!+2!? No. You can atmost take 2! common, which makes 2! * (3 + 1). But, this does'nt help.
This is how the left-overs affect the solution.
Also note that there can be left-overs which are greater than x.
Because you can take 3! common out of 3! + 5! => 3! * (1 + 4*5)
Here's my submission 177646415
Hope this helped, and I did not overcomplicate it ;-;
I figured it out, thanks to your help, and managed to AC 177657032
Problem was actually much easier than I initially thought. Thank you so much!
Glad it helped!
It doesn't matter what the last value of your map is, in fact you don't care about the values
>= x(those are already $$$0 \mod x!$$$). All that matters is that you shouldn't have any leftovers at all.Consider having the maximum number of leftovers you could, i.e. you have $$$x$$$ copies of $$$x!$$$, for all $$$x$$$
You can see this by adding $$$1!$$$ to $$$\sum\limits_{x=1}^{N}{x \cdot x!}$$$, it becomes $$$(N+1)!$$$
Hi, I still don't understand the problem 1753B — Factorial Divisibility. I don't understand the case when there are leftovers, why do we can say that if that happens, it's no divisible by x! ?
For example how to know that 3*7! + 4*5! are not divided by 8!?
Could someone help me please? Chimpanzee,gupta_samarth,SilverWing05
Just take a look at this example, (9! + 8! + 9!) and you want to check if this is divisible by 8!
For (9! + 8! + 9!) to be divisible by 8!, (9! + 8! + 9!) should be a multiple of 8!
Can you take 8! out of (9! + 8! + 9!)? Yes.
8! * (9 * 1 * 9)
Thus, it is divisible by 8!
But what if the sum of array was something like this (7! + 8! + 9!)
Now, what's the biggest factorial you can take out of (7! + 8! + 9!)? It's 7!
So, 7! * (1 + 8 + 8*9)
But, this cannot be divided by 8! because we need the factor to be greater than equal to 8!
This is why there can be no leftovers less than x.
Hope you understood, because this is the best I could do in layman terms)
Do-you-know-calculus-forces
Very amazing contest!Congrats to the authors!
Sudden death when I noticed that I was wrong about the usage of priority_queue right after the contest
(Waiting unlock the contest to resubmit for about 3 hours due to the round #830...)
Anyway the problems are good though I make fatal mistakes in the contest. Good job!
Is Div1 D related to Kuhn? I thought, that I can start from free cell, and then find increasing chain with minimal cost. However, I died in last sample, when starting from any free cell, I try to do two rotations and one shift.
Yes it is related, you are missing the case when you split the augmenting path in two and shift everything in each half to cover the free cell instead of shifting everything along the path ie creating two free cells at the end or the beginning.
I hope Div1 D will be harder next time .
Is the round #830 now rated for me? I will fall to candidate master after this round rating changes come.
Can someone show me their implementation for C2? Im pretty sure I figured it out but found the implementation very tricky!
Based on the C1 code, you can reverse the sign according to the number of leading zeros.
Can you please elaborate?
First, divide all the non-zeros into pairs. If there is an odd number of non-zero values, then the objective is impossible (output -1).
Let's say you have some non-zero value $$$a$$$, followed by $$$k$$$ 0s (where $$$k \geq 0$$$), followed by a non-zero value $$$b$$$. If $$$a \neq b$$$, then take a partition of $$$a$$$ with all the $$$0$$$s and a partition of just $$$b$$$, so they cancel each other out. Otherwise, if $$$a == b$$$, there are two cases:
What happens if there is some non-zero value a, followed by k zeroes, then some non-zero value b where a != b. Then what happens?
That was the first case I mentioned. Take a partition of $$$a$$$ with all the 0s and just $$$b$$$. For example:
One of the correct answers would be:
Yes i understand now, thanks.
Hacked a solution for 1B with fixed-module hashing.
The hacked numbers are 998244353, 10^9+7, 10^9+9 and 19260817(oops).
How did you create it?
I guess i should not complain but it feels bad that other solutions will pass just by having a different prime modulus but mine will fail even though the solution is exactly the same :(
You hacked me, T^T. However, thanks for your ingenious constructions. I have learned a lot from this.
Nice dude
Personally, I was disappointed.
Because:
D was very easy compared to C2.
You can guess the formula of E by just looking at the hint.
Actually I'm complaining because I'm screwed...
So when will the system test begin？
After R830 ends.
Speed Forces in Div.1 (
can any one give a hint in problem d
Thanks to the last educational round's problem 1749E - Cactus Wall, I managed to solve today's D1D. Although they are quite different problems, they both essentially boil down to the same technique — construct a weighted graph with edges between elements connected diagonally (such as black squares on a chessboard), and then run Dijkstra on the graph.
splitted-problems-forces
ABD-forces
Can anyone provide pretest 2 for problem C1?
When will system test begin?
Jesus D. Christ why do these rounds never have maximal tests in pretests
pretest 5 had, you just got unlucky
Bruh
Problem D has a bad pre-test, at least for my code, https://codeforces.net/contest/1754/submission/177564421 , I counted twice, but passed the pre-test
Any idea when will we get the rating changes??
Let $$$cnt[i]$$$ the number of times $$$i!$$$ appears in the sum, it's a compressed form of the sum. (which can be easily calculated; it's the number of times $$$i$$$ appears in $$$A$$$). First, let's start from the very simple basic stuff : imagine $$$cnt[1]$$$ is equal to $$$2$$$. In other words, it means that there is this expression in the sum : $$$1! + 1!$$$. But more simply, it can be written as $$$2 \cdot 1!$$$. But is there another way of writing this : in fact, since $$$1! = 1$$$, $$$2 \cdot 1! = 2 \cdot 1 = 2!$$$. So maybe ... we can just add $$$1$$$ to $$$cnt[2]$$$ (indicating that we have to add $$$2!$$$ to the sum) and just set $$$cnt[1]$$$ to $$$0$$$. Now, more generally what happens if $$$cnt[1]$$$ is magnificently big, let's say $$$500000$$$. But we can always do the same : add $$$1$$$ to $$$cnt[2]$$$, remove $$$2$$$ to $$$cnt[1]$$$. And redo it again, redo it again, .... In this way, we will have $$$cnt[1] = 0$$$. But there is a more mathematically and not-time consuming way to do this : it's to just add to $$$cnt[2]$$$ ($$$\left \lfloor {\frac{cnt[1]}{2}} \right \rfloor$$$), and set $$$cnt[1]$$$ to $$$cnt[1] \text{ mod } 2$$$. Now imagine after this operation, $$$cnt[1]$$$ is equal to 1. That means that the sum is not divisible by $$$2$$$ : all the other blocks ($$$2!, 3!, 4!, 5!, 6!$$$ have all a factor $$$2$$$ inside it, thus divisible by $$$2$$$). And that implies that the sum is not divisible by $$$k!$$$. Let us continue this algorithm other and other, and check if $$$cnt[i]$$$ equal to $$$0$$$ (after each operation). At the end, we will have only blocks of $$$k!$$$, and that means that the sum is divisible by $$$k!$$$ !
If you could not solve D during contest and want to upsolve it — I suggest that you read about The factorial number system.
UPD: OOF FACTORIAL NOT FRACTIONAL damn my typos are f**ked up when its late
Can anyone please tell me why my sol is wrong for D https://codeforces.net/contest/1754/submission/177575412 I have used the fact if two number are divisible than taking prime mod(mod > coefficient) will give the same value
I think someone came up with a hack that uses a collision specifically for 1e9 + 7 and 1e9 + 9. Use different primes and it's AC.
Edit: Actually they left a comment about it too that I missed :P
Thanks
Thanks for the round!
I enjoyed this round, especially problem E was interesting!
problem F: I calculated (r+1)*(-l+1) instead of r-l+1 and lost the first place.
When I corrected that, it actually passed as shown in this submission. Very regrettable :_(
Anyway, thank you for preparing good problems!
Is this round unrated??
I don't think so
Good round, the difficulty of div2 is very moderate, very suitable for a novice like me, the E questions are not too difficult, I love it!!!
I enjoyed the problems too! Though I feel like this time around the div 2 was a lot easier, since D2E-D2F was actually doable for me in < 1hr. Though that is from my experience upsolving and not actually in contest :p.
The contest is too short for me. If its duration is 2.5 hour. I can solve Div.1 D and have a positive delta. QaQ.
D has bad pre-test.
not actually
1 1 1 this case didnt included in pretest.
Of course because that case is trivial. duh
Hi, your comment is not funny nor helpful. Next time, please refrain from writing such comments.
What decides if a comment is useful or not? I don't know exactly, but I think it's definitely not the 6~10 mfs (Yes, this may include you. I mean YOU, THE ONE READING THIS.) consistently downvoting my comments regardless of content, is it?
Some of your comments are definitely useful, I was too pissed off yesterday, sorry. I admit that your comment yesterday was useful.
But the comment “Of course because that case is trivial. duh” is definitely useless, because:
and a lot of your comments (the ones that have negative votes) are like this, which makes some of your valid comments look useless
Thanks for your sincere advice, I appreciate it. I always try to suggest points that I consider valid, and I agree that some of them are a bit flawed as you suggested. I'll try to recheck the validity more before I post the comment next time.
p.s. The 6~10 consistent downvotes happen on very valid points also (Like the suggestion about adding rated/unrated register), why do they downvote literally every comment of mine? I see absolutely no reason for them to mass-downvote me on these unless the occasion is that they simply hate me.
The problems are good quality.It suprised me very much.I am looking forward to more contests!
In this contest again we had unrated winners and many people with high ranks who it was their first contest and seems to be fake users. time to have some ideas about recognizing fake users and avoid them from participating in contests. Any idea?
I wonder what would have been difficulty of Div2 D if a[i] and x had been up to 10^18
Then the answer would not be possible in 10**5 array unless all the elements are equal to x
I am from India and how come you skip my answer saying that it matches significantly with someone whom I don't even know he/she exits? And if it is then why I am the only one to be skipped and he got ratings??
Attention!
Your solution 177569022 for the problem 1754A significantly coincides with solutions Millionaire2022/177535697, BadalArya2/177569022. 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.net/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.
You listed 2nd and 3rd places in the wrong order.
Thank you! Fixed.
EXPERT LES GOOOO
有中国人吗？