Всем привет!
В воскресенье в Москве пройдет XIX Московская командная олимпиада — командное соревнование для школьников, проходящее в Москве как отборочное соревнование на ВКОШП. Над туром работала Московская методическая комиссия, известная вам также по Открытой олимпиаде школьников по программированию, Московской олимпиаде для 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).
Раунд состоится в 25.10.2021 09:35 (Московское время) и продлится 2 часа. Обратите внимание на нестандартное время начала раунда. В каждом дивизионе будет предложено по 6 задач. Раунд будет проведён по правилам Codeforces, будет рейтинговым для обоих дивизионов.
В связи с этим мы просим всех участников сообщества, участвующих в соревновании, проявить уважение к себе и другим участникам соревнования и не пытаться читерить никоим образом, в частности, выясняя задачи у участников соревнования в Москве. Если вы узнали какие-либо из задач МКОШП (участвуя в ней лично, от кого-то из участников или каким-либо иным образом), пожалуйста, не пишите раунд. Участников олимпиады мы просим воздержаться от публичного обсуждения задач. Любое нарушение правил выше будет являться поводом для дисквалификации.
Задачи соревнования подготовлены LHiC, cdkrot, isaf27, AlesyaIvanova, Tikhon228, voidmax, dyrbulshchyl, KiKoS, Kaurker, PaHbLLle_91_6blJl_6blcTp, vintage_Vlad_Makeev и Дарья Крохина под моим руководством, а также GlebsHP, meshanya, Endagorion, Zlobober и Андреевой Е. В.
Спасибо adedalic и KAN за координацию раунда и вычитку оригинальных задач МКОШП, adedalic и GlebsHP за перевод условий, а так же MikeMirzayanov за системы codeforces и polygon, который использовался при подготовке задач этой олимпиады.
Также спасибо napstablook и Anti-Light за предоставление дополнительных задач, которые помогли составить (я надеюсь) сбалансированный проблемсет для раунда.
Всем удачи!
UPD1: Спасибо Um_nik, PurpleCrayon, LHiC, VladaMG98, JovanB, TadijaSebez, AlanSkarica, Markadiusz, actinium16, jurichhh8 за тестирование.
UPD2: Разбалловка:
Div.1: 500 — 1250 — 2000 — 2250 — 2250 — 3000
Div.2: 500 — 1000 — 1500 — 2250 — 3000 — 3250
UPD3: Разбор
UPD4: Победители!
Div. 1:
Div. 2:
The good thing is that, The contest day is my Birthday. But my unfortunate is that my math final xm is clashes with first 30 minutes of contest T_T
Why is it on Monday at 14:35? We're still at school...
In my region the contest is at 1 am. I need to wake up at 6 am to go to school D:
Please consider others. Not everything is for you.
P.S. I really love this round! Really good pretest. There's even a n=1 pretest so that I would not FST.
Did this have only 2 comments before? [It says the blog has been posted 2 weeks ago.]
The blog was written 2 weeks ago but published recently.
I thought, I saw this post before and assumed it was republished. But there were no comments. And got confused. thanks for reply :)
Is it going to be held in the ICPC 10mins penalty format or score distribution will be released?
https://ibb.co/zh2VpTX
For europe this is a ridiculous time
i wish contests timings will go back to normal...
In problem E in the last sample, why [7 9][7] is impossible?
Thanks.
EDIT: Nevermind. I was too hungry when I read the statement.
EDIT: Looks like I was so hungry that I commented on the newer contest's announcement. Apologizes for spamming.
This should be the most unusual time I've ever seen in Cf
Bad time
I hope there will be more datastructure problems . I like that more than construction problems.
Hope everyone good luck!
You should've used "those" or "these" instead of "that".
Your English is very good!
Or "them"
waiting for aryanc403's pigeonhole comment
this idea was given to me by the legend himself
As a student, who has already participated in this olympiad, I say that problems are good.
Oh 22:35, note the usual time!
As a tester, the problems are great! Good luck to everyone! :)
As a tester, I can confirm that the tasks are very interesting, and the statements are clear and well written. I hope you enjoy the contest. Good luck!
If you test a round but don't shamelessly beg for upvotes in the comments, can you really call yourself a tester?
I guess zhoukangyang will become LGM after this contest!
sadly the contest contains some unfair problem which is 100% not original and meaningless,we have to wait longer...
Waiting for weak pretests.
Now I have a reason to skip my online classes. XD
nice contest but still at expert :'(
OMG , this contest will give me one of my best rank if there will be no FST , I m so happy
Div.2 D is so hard for me :(
You are so naive.
FML for never improving my bit manipulation concepts, didn't even get close to solving C.
Just for sure, is problem D bfs?
tem_shett thinks that yes!
So dp is a wrong solution for this problem right?
right
It is not wrong, it is just different. I solved it with dp + segtree
Kind of... At least in my case, I solved it with a DP + queue, where the DP states are propagated using a queue, sort of like in a BFS fashion
Yes, 0-1 BFS backwards from the top of the well on the state {current position, next event is a slip or jump}.
Slips (zero cost move) can be easily maintained as an adjacency list and jumps (1 cost move) are just marking all positions where $$$j - a_{j} \leq i$$$ when we are at $$$i$$$. So we can just sort all points by values of $$$j - a_{j}$$$ and process as many unprocessed ones from the start as we can in each step.
I've seen your code but I still don't get how going through the 'order' vector only once is enough. Could you please explain that?
Is range addition + range min queries segtree not intended in Div1C or is the TL just really tight?
Had to switch to ints and replace two sets with vector + sort + unique to even go from TL2 to TL13, I half expect replacing the remaining maps in this fashion will fix TLE :/
I've got OK with seg-tree queries that you mentioned. But only after switching from __gnu_pbds::tree to BIT in computation of number of inversions in a[].
I used a BIT from the start, still TLE on 13 :/
I suspect I'll need to remove the majority if not all the maps in my code to get AC.
Edit: Yup, removing all maps and using a sort based compression instead was enough to get AC.
How to solve div2 C?
check for each bit the frequency among all numbers($$$f_0$$$ ~ $$$f_{29}$$$), find the GCD for the freq among all bits($$$gcd(f_0, f_1, \cdots, f_{29}$$$), the answers are all the factors of the GCD value.
also, remember to handle the case where all numbers are zero.
updated: the special case should be all numbers are zero instead of equal
How did you came to this and plz explain why it works.
the idea came to me after I write down the numbers in base-2.
why it works: for a bit $$$i$$$, let's say it occurs $$$f_i$$$ times, it will be subtracted only when all $$$k$$$ chosen number in that round has that bit, which means that $$$k$$$ has to be a factor of $$$f_i$$$.
Count the setBit of all position from 0 to 30 of all element. Run a loop from 1 to n and check if the mod of i and count of setBit in all position give zero then it is possible to distribute for I
Why is Div1C time limit so so tight.
+1. I pass it by using a quicker input ways .
I don't get why authors set problem with complexity O((n+m)*log(n+m)) n,m<=1e6 with non-trivial constant.Even the time taken by the accepted submissions is very high.Is it intended to use getchar while taking input?.Would never have happened if anton coordinate the contest
You can search optimal positions not fair, but with ternary search + checking small neighborhood. Constrains was raised against such solutions.
You do realize that because of blocking some weird heuristics many genuine solutions were not allowed?There are 6 pages of TLE in this problem and most accepted submissions are close to tl
If very tight tl is intended why not have ai,bi<=1e6 instead of 1e9.
Problem 1D/2F is a problem of a private contest in our school.. I'm so amazed..Here is the photo
how to solve Div.2 D?
My DP solution 133030971 didn't work :( people have tried segment tree and bfs approaches
My solution 133023219 fails at Time limit exceeded on pretest 17, can't find a way to decrease time complexity
kind of bfs with some dp
"Dp with data structures" round ...
Wondering why BFS solution for DIV2-D got TLE? The complexity would be O(ElogE)!
Wondering why BFS solution on div2-D got TLE. The complexity would be O(n.log(n)) which is fine!
My idea for D was the following:
Since an alpinist $$$j$$$ can come after alpinist $$$i$$$ only if $$$\max(s_i,a_i) \le s_j$$$ so we can first sort the array by $$$s_i$$$ values and say for each index $$$i$$$ the value of max length subsequence ending at this index is $$$DP_i$$$, recurrence would be,
And this could be done with a segment tree where after reaching each index we update the $$$\max(s_i,a_i)$$$ index in the segment tree by $$$DP_i$$$ Is this solution anywhere close to the original solution?
EDIT: Okay, I read the editorial and this approach is incorrect:(
I really liked problem C. If you construct $$$n \times 30$$$ binary grid of the number's bits, we are essentially taking maximal (vague but it doesn't matter a lot) all one subgrids (in the subseqeunce sense) with column size $$$k$$$ and flipping them to zeroes. This shows that the value of $$$k$$$ should divide all the column sums in all the $$$30$$$ columns. And it's easy to check that it is possible to do the latter when $$$k$$$ does satisfy these conditions.
for C, k is in the answer if and only k divides all sum of 1 in 30 columns bitwise? I couldn't prove the correctness but passed pretests.
For problem C, is it true that k is in the answer set if and only k divides all count of 1 in 30 bitwise positions? I couldn't prove correctness but passed pretests
Yes and the proof is not hard either.
what is the proof? the condition of k divides is obviously a necessary condition, but how do you prove is it also a sufficient condition?
Consider any divisor $$$k$$$ and a set of numbers such that the count of numbers with the $$$i$$$-th bit on is a multiple of $$$k$$$.
In each step, choose any set of $$$k$$$ numbers which share at least one same on bit. Clearly this is do-able as long as all the numbers are not zero and the condition that count of numbers with the $$$i$$$-th bit on is a multiple of $$$k$$$ is maintained.
Now the $$$\textbf{and}$$$ of these numbers will only include bits which are on in all the numbers. So we will reduce the count of numbers with the $$$i$$$-th bit on by $$$0$$$ or $$$k$$$ for each $$$i$$$.
So the count of numbers with the $$$i$$$-th bit on will remain divisible by $$$k$$$ and we can repeatedly perform this to solve it.
If you want a more formal proof, you can write a strong induction proof using this fact. The predicate would be something like $$$p(x)$$$ means for any positive integer $$$k$$$ there exists a way to solve an arbitrary set of non-negative numbers with sum $$$x \times k$$$ given that the count of numbers with the $$$i$$$-th bit on is a multiple of $$$k$$$.
every time we want to subtract, we need to subtract k or 0 counts of bitwise pos, so if we want to subtract all elements to zero, the bitwise count in every pos must be divided by k
I accidently do my best ever contest in my alt account but not my main account
Time to run: swap(main, alt);
very super legendary strong pretest in B :( Unbelievable :(
In problem B (div 2), what is the maximum value of k after which the there is no change? I thought it would be N, but that failed pretests. Running an infinite loop and breaking when the array becomes constant worked.
for me ,it worked till n ,you can check my submission for that https://mirror.codeforces.com/contest/1602/submission/132999960
I got WA when I checked only up to N, but accepted when I ran the loop until the array stabilizes. I don't know why this is happening, it seems so intuitive that it will take at max N iterations.
https://mirror.codeforces.com/contest/1602/submission/133072897 You are just checking it till n-1 ,you have to check it till n ,when i did that ot got accepted ,see above submission
Ahhh got it. Thx
To not keep you waiting, the ratings are updated preliminarily. In a few hours/days, I will remove cheaters and update the ratings again!
Thanks! Fastest rating updates in recent time
About problem D,I submitted a simple code and it passed system test.
Could anybody Hack it or prove that it is right?
I tried to prove it by swaping adjacent positions.Let's suppose that $$$\max(s1,a1) \lt \max(s2,a2)$$$ and now we swap them.If $$$a2 \gt \max(s1,a1)$$$,the answer will be obviously smaller.If $$$s2 \lt a1$$$,we can find that $$$a2 \gt a1$$$,so the answer may be smaller,too.
I haven't found a situation that we can make the answer bigger by swaping adjacent positions,so I guess it is right.
But why you explain this to your classmate in English through Codeforces?(I mean that they are classmates and they are both Chinese.It is convenient for them to communicate with each other in private.)
I am really surprised to see why div2 winner of this contest having less number of question solved as well as contest also.
Because he has exercised a lot on other websites
About E2/C1 problem. Does anyone have the way to construct the final array with A and B elements. Because my only problem is to construct this array.
For each $$$b_{i}$$$,we use $$$c_{j}=1,0,-1$$$ to denote $$$a_{j} \gt b_{i},a_{j}=b_{i},a_{j} \lt b_{i}$$$ respectively,so the cost of inserting $$$b_{i}$$$ is the number of prefix $$$c_{j}=1$$$ and suffix $$$c_{j}=-1$$$,and it's equal to the total number of $$$c_{j}=-1$$$ plus a prefix sum of the sequence $$$c$$$.So we can use the segment tree to solve it.
Attention! Your solution 132999485 for the problem 1602C significantly coincides with solutions Scut22/132996768, phantom654/132999485. Such a Enr oxamole 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 minutes ago the round with all the details. More information can be found at http://mirror.codeforces.com/blog/entry/8790.Such violation of the rules may be the reason for blocking your may be blocked.
I agree the codes are very similar but the logic of the problem was pretty straightforward. Also using variable names like cnt for counting, g for gcd is a quite standard. So I appeal that it was a mere coincidence. Also Scutt22 seems to be from outside India, and I don't know him in any way. Also please note that I submitted the problem during first 30 minutes of the contest. @MikeMirzayanov