### ch_egor's blog

By ch_egor, 17 months ago, translation,

Hi everybody,

This Sunday there will be a XIX Moscow Team Olympiad, high school students competition based in Moscow that is an elimination contest for All-Russian Team Olympiad. This contest is prepared by Moscow Olympiad Scientific Committee that you may know by Moscow Open Olympiad, Moscow Olympiad for Young Students and Metropolises Olympiad (rounds 327, 342, 345, 376, 401, 433, 441, 466, 469, 507, 516, 541, 545, 567, 583, 594, 622, 626, 657, 680, 704, 707, 727).

The round will be held at Oct/25/2021 09:35 (Moscow time) and will last for 2 hours. Note the unusual time of the round. Each division will have 6 problems. The round will be held according to the Codeforces rules and will be rated for both divisions.

We kindly ask all the community members that are going to participate in the competition to show sportsmanship by not trying to cheat in any manner, in particular, by trying to figure out problem statements from the onsite participants. If you end up knowing some of the problems of Moscow Team Olympiad (by participating in it, from some of the onsite contestants or in any other way), please do not participate in the round. We also ask onsite contestants to not discuss problems in public. Failure to comply with any of the rules above may result in a disqualification.

Problems are prepared by LHiC, cdkrot, isaf27, AlesyaIvanova, Tikhon228, voidmax, fedoseev.timofey, KiKoS, NiceClock, 4eT_llpuyHblJl, vintage_Vlad_Makeev and Daria Krokhina under my supervision with great help of GlebsHP, meshanya, Endagorion, Zlobober and Helen Andreeva.

Thanks to adedalic and KAN for the round coordination and verifying statement of original olympiad, adedalic and GlebsHP for statement translation, and also thanks for MikeMirzayanov for systems codeforces and polygon, which was used to prepare problems of this olympiad.

Also thanks to napstablook and Anti-Light for providing an additional problems that helped to create (I hope) a balanced problem set for the round

Good luck everybody!

UPD2: Scoring distribution:

Div.1: 500 — 1250 — 2000 — 2250 — 2250 — 3000

Div.2: 500 — 1000 — 1500 — 2250 — 3000 — 3250

UPD3: Editorial

UPD4: Winners!

Div. 1:

Div. 2:

• +267

| Write comment?
 » 17 months ago, # |   -23 T_TThe 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
 » 17 months ago, # |   -36 Why is it on Monday at 14:35? We're still at school...
•  » » 17 months ago, # ^ |   +38 In my region the contest is at 1 am. I need to wake up at 6 am to go to school D:
•  » » 17 months ago, # ^ | ← Rev. 2 →   +3 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.
 » 17 months ago, # | ← Rev. 3 →   -15 Did this have only 2 comments before? [It says the blog has been posted 2 weeks ago.]
•  » » 17 months ago, # ^ |   +3 The blog was written 2 weeks ago but published recently.
•  » » » 17 months ago, # ^ |   0 I thought, I saw this post before and assumed it was republished. But there were no comments. And got confused. thanks for reply :)
 » 17 months ago, # | ← Rev. 4 →   -22 Spoiler!https://ibb.co/zh2VpTX
 » 17 months ago, # |   +6 i wish contests timings will go back to normal...
 » 17 months ago, # | ← Rev. 3 →   -25 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.
 » 17 months ago, # |   +9 This should be the most unusual time I've ever seen in Cf
 » 17 months ago, # |   -15 Bad time
 » 17 months ago, # |   +13 I hope there will be more datastructure problems . I like that more than construction problems.Hope everyone good luck!
•  » » 17 months ago, # ^ |   +7 You should've used "those" or "these" instead of "that".
•  » » » 17 months ago, # ^ |   0 Your English is very good!
•  » » » 17 months ago, # ^ |   +8 Or "them"
 » 17 months ago, # |   +26 waiting for aryanc403's pigeonhole comment
 » 17 months ago, # |   +13 lighthearted (redirect)this idea was given to me by the legend himself
 » 17 months ago, # |   +43 As a student, who has already participated in this olympiad, I say that problems are good.
 » 17 months ago, # |   +1 Oh 22:35, note the usual time!
 » 17 months ago, # |   +48 As a tester, the problems are great! Good luck to everyone! :)
 » 17 months ago, # |   +45 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!
 » 17 months ago, # |   +138 If you test a round but don't shamelessly beg for upvotes in the comments, can you really call yourself a tester?
 » 17 months ago, # |   +158 I guess orzdevinwang will become LGM after this contest!
•  » » 17 months ago, # ^ |   +23 sadly the contest contains some unfair problem which is 100% not original and meaningless,we have to wait longer...
 » 17 months ago, # |   +32 Waiting for weak pretests.
 » 17 months ago, # |   +28 SpoilerNow I have a reason to skip my online classes. XD
 » 17 months ago, # |   0 nice contest but still at expert :'(
 » 17 months ago, # |   +7 OMG , this contest will give me one of my best rank if there will be no FST , I m so happy
 » 17 months ago, # |   -71 Div.2 D is so hard for me :(
•  » » 17 months ago, # ^ |   +53 You are so naive.
 » 17 months ago, # |   +6 FML for never improving my bit manipulation concepts, didn't even get close to solving C.
 » 17 months ago, # |   +8 Just for sure, is problem D bfs?
•  » » 17 months ago, # ^ |   +9 tem_shett thinks that yes!
•  » » » 17 months ago, # ^ |   0 So dp is a wrong solution for this problem right?
•  » » » » 17 months ago, # ^ |   -15 right
•  » » » » 17 months ago, # ^ |   0 It is not wrong, it is just different. I solved it with dp + segtree
•  » » 17 months ago, # ^ |   0 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
•  » » 17 months ago, # ^ |   +1 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.
•  » » » 17 months ago, # ^ |   0 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?
 » 17 months ago, # | ← Rev. 2 →   +16 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 :/
•  » » 17 months ago, # ^ |   0 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[].
•  » » » 17 months ago, # ^ | ← Rev. 2 →   0 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.
 » 17 months ago, # | ← Rev. 2 →   0 How to solve div2 C?
•  » » 17 months ago, # ^ | ← Rev. 2 →   0 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
•  » » » 17 months ago, # ^ |   0 How did you came to this and plz explain why it works.
•  » » » » 17 months ago, # ^ |   0 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$.
•  » » 17 months ago, # ^ |   0 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
 » 17 months ago, # |   +74 Why is Div1C time limit so so tight.
•  » » 17 months ago, # ^ |   +42 +1. I pass it by using a quicker input ways .
•  » » 17 months ago, # ^ |   +3 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
•  » » 17 months ago, # ^ |   +1 You can search optimal positions not fair, but with ternary search + checking small neighborhood. Constrains was raised against such solutions.
•  » » » 17 months ago, # ^ | ← Rev. 2 →   +7 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
•  » » » 17 months ago, # ^ |   -13 If very tight tl is intended why not have ai,bi<=1e6 instead of 1e9.
 » 17 months ago, # | ← Rev. 3 →   +19 Problem 1D/2F is a problem of a private contest in our school.. I'm so amazed..Here is the photo
 » 17 months ago, # |   +3 how to solve Div.2 D?
•  » » 17 months ago, # ^ |   -9 My DP solution 133030971 didn't work :( people have tried segment tree and bfs approaches
•  » » » 17 months ago, # ^ |   0 My solution 133023219 fails at Time limit exceeded on pretest 17, can't find a way to decrease time complexity
•  » » 17 months ago, # ^ |   0 kind of bfs with some dp
 » 17 months ago, # |   +74 "Dp with data structures" round ...
 » 17 months ago, # |   +1 Wondering why BFS solution on div2-D got TLE. The complexity would be O(n.log(n)) which is fine!
 » 17 months ago, # | ← Rev. 3 →   +3 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, $DP_i=\max_{x \in [0,s_i]}DP_j+1$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:(
 » 17 months ago, # |   +1 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.
 » 17 months ago, # | ← Rev. 3 →   0 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
•  » » 17 months ago, # ^ |   0 Yes and the proof is not hard either.
•  » » » 17 months ago, # ^ | ← Rev. 2 →   0 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?
•  » » » » 17 months ago, # ^ | ← Rev. 3 →   +3 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$.
•  » » 17 months ago, # ^ |   0 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
 » 17 months ago, # |   -15 I accidently do my best ever contest in my alt account but not my main account
•  » » 17 months ago, # ^ |   +3 Time to run: swap(main, alt);
 » 17 months ago, # |   0 very super legendary strong pretest in B :( Unbelievable :(
 » 17 months ago, # | ← Rev. 2 →   0 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.
•  » » 17 months ago, # ^ |   0 for me ,it worked till n ,you can check my submission for that https://codeforces.cc/contest/1602/submission/132999960
•  » » » 17 months ago, # ^ |   0 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.
•  » » » » 17 months ago, # ^ |   0 https://codeforces.cc/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
•  » » » » » 17 months ago, # ^ |   0 Ahhh got it. Thx
 » 17 months ago, # |   +14 To not keep you waiting, the ratings are updated preliminarily. In a few hours/days, I will remove cheaters and update the ratings again!
•  » » 17 months ago, # ^ |   +11 Thanks! Fastest rating updates in recent time
 » 17 months ago, # | ← Rev. 3 →   +101 About problem D,I submitted a simple code and it passed system test.Could anybody Hack it or prove that it is right? int n,d,ans; struct P{int s,a;}a[N]; bool cmp(P x,P y){return max(x.s,x.a)==max(y.s,y.a)?x.s=d) ans++,d=max(d,a[i].a); cout<
•  » » 17 months ago, # ^ |   +44 I tried to prove it by swaping adjacent positions.Let's suppose that $\max(s1,a1)<\max(s2,a2)$ and now we swap them.If $a2>\max(s1,a1)$,the answer will be obviously smaller.If $s2a1$,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.
•  » » » 17 months ago, # ^ | ← Rev. 2 →   +12 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.)
 » 17 months ago, # |   -31 I am really surprised to see why div2 winner of this contest having less number of question solved as well as contest also.
•  » » 17 months ago, # ^ |   -10 Because he has exercised a lot on other websites
 » 17 months ago, # |   0 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.
•  » » 17 months ago, # ^ | ← Rev. 2 →   +13 For each $b_{i}$,we use $c_{j}=1,0,-1$ to denote \$a_{j}>b_{i},a_{j}=b_{i},a_{j}
 » 17 months ago, # | ← Rev. 5 →   +6 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 https://codeforces.cc/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