Hi everybody,

This Sunday there will be a XVIII 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).

The round will be held at Nov/01/2020 14:05 (Moscow time) and will last for 2 hours. Each division will have 5-6 problems. **The round will be held according to the Codeforces rules and will be rated for both divisions.**

Problems are prepared by vintage_Vlad_Makeev, NiceClock, ismagilov.code, vintage_Vlad_Makeev, KiKoS, wrg0ababd, ch_egor, Roms, voidmax, DebNatkh, Nebuchadnezzar, Endagorion, craborac, 300iq, cdkrot, LHiC, vintage_Vlad_Makeev, V--o_o--V, grphil 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, meshanya and cdkrot for statement translation, and also thanks for MikeMirzayanov for systems codeforces and polygon, which was used to prepare problems of this olympiad.

Good luck everybody!

**UPD1:** Thanks to Um_nik, satashun, mraron, ustze, Karavaiev, KKiYeer for testing.

**UPD2:** Scoring distribution:

Div.1: 500 — 1000 — 1500 — 2000 — 3000

Div.2: 500 — 1000 — 1500 — 2000 — 2500

**UPD3:** Editorial

**UPD4:** Winners!

Div. 1:

Div. 2:

Friendly time for Chinese again!

Clashes with ABC 181 :(

This round directly clashes with Atcoder Beginner's round 181 which starts after 1 hour of the start of this round. I request authors to please check once.

Too early

This round is based on onsite olympiad and they can't change time of start.

It's gonna be another Div.1.5-like Div.2 contest, and Div-0.5 like Div.1 contest

Most div1 people complain because there are few div1 rounds. Maybe proposing more rounds based on Olympiads can be an improvement. There are a lot of rounds based on Russian Olympiads, so I think that it can be extended to other nations.

Do you really think this is few?

It's an exception to the rule.

In the average graph of div1 people, the number of dots (contests) is significantly lower where the rating is $$$\geq 2100$$$.

Why is it a 'rule'? It's just the result of 'Div.2 only' exist but 'Div.1 only' doesn't. And because creating good harder problems usually takes more time than creating good easier problems, it would be inevitable there are fewer Div.1. If I can choose more lower-quality Div.1 or less higher-quality Div.1, I will choose the latter.

But Olympiads from countries other than Russia also contain good problems, so why there are only Russian Olympiads on codeforces?

That might be because codeforces is originally a Russian website, so the olympiad organisers may feel good if it is organised in a Russian platform too. Codeforces is growing as a more international platform, so we can see other countries' olympiads in the future maybe.

where are testers ???

I think 20 authors is enough for testing

Well, I'm one of the testers of this round. Seems that they haven't put the testers in the announcement yet.

Upd: It’s updated now.

Yes, I will add all testers after testing is over

The amount of red people in problemsetters scares me..

As a red, they scare me too.

I was literally searching for your comments to upvote them xD.

Well you found them, Sherlock Holmes.

They still haven't added the tester list, so I suppose there's no one to stop me from claiming I'm a tester for contribution farming purposes.

Here comes the post hijacker Monogon xD

Your this kind words motivate me

Is it Rated?

Yes

when I ask this question , this answer not mentioned in blog.

When it is mentioned that it is a div2 / div1 round its anyways rated. It would be specified if it is some external contest. :)

There’re only 32 Legendary Grandmasters at all, and 4 of them took part in preparing the problems!

That's the number of LGMs who competed in the last 6 months. There are inactive LGMs too.

Yes, you are right, but then what is rating(all)?

Rating (all) lists all users, but it lists all the active users before all the inactive users.

Thanks a bunch, but this doesn't change how cool people were involved)

actually 5 LGM's were involved(Um_nik as a tester)

someone tell Codeforces Halloween was yesterday!!

:|

I don't know about you people but actually I prefer contests with harder problems because speed matters less :)

Will the round be rated? Also will it be codeforces rules or something like ACM ICPC?

It is mentioned in the post that

It is ratedClarifications to both my questions were added in bold after I posted my comment

moscow team olympiad aight imma skip this one

No-one

Cares! about your participation.there is atcoder beginner contest 181. so, it is tough to attend 2 contest at a time

Codeforces contest is more standard , imo . But i believe that atcoder contest time will be changed. ..

Yes, it would be good for everyone if they cooperate.

[deleted]

https://twitter.com/chokudai/status/1322557968651415553

AtCoder's president said "We can't change the time of tomorrow's atcoder contest".

And this makes me sad :(

Yes,both atcoder and codeforces will definitely see into it and change the timings to remove any possible overlaps.

Note that the start time is unusual.:(Clashes with OpenCup :( (apparently)

Fortunately managed to solve all my problems, including first solution to Geo3D, in 2:47 and left teammates with optimizing code to last one :D

We will face one of the hardest contests. Let's see what happens.

hopefully we will see score distribution before the contest..

How will tie be resolved? Sorry I am new to cf so that's y asked

How can 20 authors propose 10 problems? Isn't it like one problem is completely written by a single writer?

Seems like showing the name of movie makers before starting a horror movie!!

For those in US, note the clock change. On Nov 1st at 2 a.m. most US states will fall back one hour to 1 a.m.

Those who didn't know this happens... sounds stupid uh!? :)

Thank you, I did not notice this! It seems the time zone adjustment on Codeforces is different from the one if you click the link to timeanddate.com

Yeah, I was confused about this too.

The daylight saving time

Last time when I saw this many reds, I saw an accident.

Reminds me of Codeforces Round #659

Can't we have rounds in codeforces based on other olympiads? This would increase the rate of contests for both divisions and you would not need that much of co-ordination cause these problems appeared in Olympiads so it must be good. We only see rounds based on Russian Olympiads in codeforces unfortunately.

This competition is friendly for Chinese competitor!

Thanks ch_egor

The amount of red people in problem setters scares me.

Why so many authors this time??

do you have any problem??

All the best for everyone who are giving the contest !!!

A huge number of setters.

.

Gap between D and E is huge.

I'd say the gap between C (your E) and D is the huge one.

I think the gap always seems biggest near the limit of your abilities.

Am i the only newbie stuck in C??

Friendly time for Chinese again!

What is test case 2 of Div 2 C :(((

How do you do Div2E/Div1C? I think the problem reduces to "Find number of pairs of groups $$$G_1$$$ and $$$G_2$$$ such that $$$G_1 \cup G_2$$$ is bipartite", but I can't think of anything better than brute force.

There are only $$$O(m)$$$ pairs $$$(G_1, G_2)$$$ such that $$$G_1$$$ and $$$G_2$$$ are bipartite but $$$G_1 \cup G_2$$$ might not be.

Ohhhhh that's actually pretty obvious, thanks!

Efficiently perform bipartite checks for each pair of groups that have an edge between them. You can look at the graph formed by edges within groups, find its components, throw away bipartite ones (along with whole groups), compress the 0/1 parts of remaining components into single vertices and on that graph, bipartite search takes O(number of edges between groups).

checking if a graph is bipartite with DSU + restorable DSU

the number of pairs you have to check is bounded by the number of edges, so for each pair, add in all of it's edges, check if it's bipartite, and then rollback.

You can check if a graph is bipartite using a modification of the union-find data structure: for each vertex, we keep a bit indicating whether it has the same color as its parent in the union-find data structure. When inserting an edge between $$$u$$$ and $$$v$$$, if $$$u$$$ is already in the same component as $$$v$$$, we check if they have the same color. Otherwise, we merge the components of $$$u$$$ of $$$v$$$.

Then we can simply check whether a pair $$$(G_1, G_2)$$$ is good by inserting the edges between $$$G_1$$$ and $$$G_2$$$ in that data structure, and we do a rollback after each check.

Please, why didn't you bold non-increasing and non-decreasing in D1B? Of course it's my fault, but I was solving wrong version for $$$40$$$ minutes.

Also, it's duplicate of SRM 781 Med

Same here, but didn't see it till the very end :((

same here :((

same here for 20 minutes. :(

I count myself very lucky for spotting it.

I also misread the problem. I saw the sample test cases before solving the problem and couldn't understand why the answer is 12. After around 10 minutes, I finally realized that I misread the problem.

Similarly, please bold "teams may have different sizes" in C. I made a mistake at first, and then spent lots of time wondering if it is even possible to do knapsack this fast.

Same feelings.

Same here, take my upvote. Spent ~30 minutes trying to solve the wrong version until I tried to run the samples.

Nevermind. I FSTed it anyways!

2 FST? I would have died if it happened to me.

saw it right now, was solving the wrong version until the end :(

Same here. BTW I thought the wrong version was a nice problem.

Same, but I reread the problem after my $$$N^2$$$ gave WA on the sample ...

Same here :(. I think the answer in that case was related to Catalan numbers. Can someone verify?

Hello, I am here to complain about yet another problem statement again. After seeing editorial of Div1D, I was confused as to why $$$h=v$$$ was given, since drawing the following polyline works: $$$(0,1) -> (1,1) -> (1,-1) -> (-1,-1) -> (-1,1) -> (0,1)$$$. It isn't clarified in statement that they have to cyclically alternate, I think. Please,

please, have more testers (who are perhaps non-native speakers) read and test the round so that such issues do not happen.I don't think that many people misunderstood the statement. Even if they had more testers, it's not certain that some of them would think that a closed alternating polyline may satisfy $$$h = v + 1$$$.

I specifically asked for a clarification there because it's not given.

It seems I didn't express myself clearly. I tried to say the probability of misunderstanding is low to begin with. It's just my speculation, though.

Closed polylines don't really have a beginning nor an end.

The statement says "One drew a closed polyline...". What isn't clear to me is if the alternating was just for the drawing, or for the actual diagram. I didn't get to asking clarifications as I was too busy misreading C, and thought that this problem would be hard (based on what I thought the problem was — might need to handle annoying cases). Turns out it was very clean.

Oh, I see. Yeah if you think that way it's quite possible to be confused.

Probably it would have been better if they simply gave two equal length arrays (it could ruin your results in some unexpected ways even if you interpreted the statement correctly).

How to solve div2E, I am struck for 1 hour and haven't got a single hint

i mean you're not supposed to get hints during the contest...

Sorry, I haven't got your words. If I understand what you said, I commented after contest.

ah mb, i thought you meant something different

Anyway, how to do this problem?

see above https://codeforces.com/blog/entry/84198?#comment-717474

this is first time i have ever solved 4 questions in div2,just hoping not to fail system test

How to solve C? (ِDiv 2)

In Div2D or Div1B , I was getting some double summation. For optimizing that i need to calculate summation of the form $$${n\choose n-k}$$$ + $$${n+1\choose n-k+1}$$$ + $$${n+2\choose n-k+2}$$$ .... $$${n+k\choose n}$$$ faster. Can some one tell O(1) formula for that (or some log(n) method will also work)

Sort the array and then find the sum of the absolute difference of elements at index 0 and n,1 and n+1 and so on.... then simply multiply it by 2nCn.

Can you please elaborate the multiply it by 2nCn part ? I guess you are trying to pair up element $$$i$$$ with elements at indices greater than or equal to $$$i+n$$$ and multiplying difference by number of times they can occur in two sequences such that they face each other. My approach was similar .

Edit : Got it by comments below .

How do you find two subsets of equal sum fast enough in D?

I tried to do it with iterative NTTs, which should be $$$O(MN \log M \log N)$$$ (where $$$M = 1000$$$ is the maximum value) and then some loops to check which pair actually makes the target value, but this TLEd.

bitset works better than FFT :)

Yeah, bitsets indeed gave AC :(

97358236

If you just want to find two subsets of equal sum, can't you just do normal knapsack with bitsets? (in O(NW/32) ish time?)

Isn't that $$$O(N^2 W / 32)$$$?

Too bad I didn't have time to try bitsets after getting TLE :(

Something like this:

codeI haven't got AC but I think this might work: you want to assign "+" and "-" to elements of the sets such that the set sums to 0. Shuffle the input and use a dp table $$$\mathrm{dp}[i][j]$$$ where $$$0 \le i \le n$$$ and $$$-B \le j \le B$$$ for sufficiently large $$$B$$$ (you can cut down a lot from $$$10^6$$$ here). Because the input is randomized, if there exists a solution there exists one where $$$j$$$ is not too large.

I tried just adding the "+" segments from the largest one and then subtracting the "-" segments from the largest (absolute) one, but got WA...

That won't work, what if we have $$$n-1$$$ copies of $$$1$$$ and one $$$n-1$$$. Then no matter the order we need $$$j$$$ at least $$$(n-1)/2$$$ or so.

Huh? $$$j$$$ being around $$$n$$$ is totally fine, the complexity here is $$$O(nB)$$$.

Oh, right, of course. That should work.

how to solve div2C?

Div2D/1B is same as the topcoder problem I set.

Fun fact: You can perform a magic trick based on this problem in front of your friends too. :D

how to solve div2 C? O(n^1/2) is too slow...

my solution passed pretests with $$$O(q^{1/2})$$$.

Yeah what was you solution?

The idea is that $$$ans$$$ will be largest divisor of $$$p$$$ for which the following holds: for at least one prime divisor $$$i$$$ of $$$q$$$, the exponent of $$$i$$$ in $$$ans$$$ will be less than that in $$$q$$$ (so that $$$q$$$ does not divide $$$ans$$$). My solution: link

Dude yes I just read the editorial as well. The problem was that even if I have thought of this solution I discarded it immediately because I was like "Oh the prime factorization of

qwill take a lot of time" and now I just realized that no! it would not since I have to find the primes up until the sqrt(q).. smh. I will never ever become a master unless I sit down and solve all math tagged problems until 2000 rank.can you clarify what you mean by exponent of i?

the power of a prime in prime-factorisation

Problem B: Am I the only one who thought that both $$$p$$$ and $$$q$$$ are sorted in the same order for 30 minutes?

EDIT: Just read https://codeforces.com/blog/entry/84198?#comment-717476. Seems like I am not the only one.

How the hell the answer to the example in D2E (D1C) is 3?

The number of possible combinations cnk(3, 2) = 3 and one combination is wrong, we cannot chose first and second group, because there is not way to split four students according to the rules

The answer should 2

Do I miss something?

We can choose the first and second group. Make groups $$${1, 3}$$$ and $$${2, 4}$$$.

Oh, crap. Thx

How to solve DIV2D/DIV1B ? I thought ans is $$$\sum\limits_{i=1}^n a_i *(c_i - d_i)$$$

But I was not able to fill $$$c_i$$$ and $$$d_i$$$

Problem c division 2 why my solution gives TLE ? its O(LOG P) https://ideone.com/fDlClB

It's O(sqrt(p)) not log(p) and sqrt(10^18) is 10^9 which is too slow

thanks didnt even realize

I have no idea what I missed in Div1B :|

I mean... I had multiple n^2 solutions, but nothing close enough.

For every element I tried to calculate how many times it will be with + and with -. (if a is sorted) a[i] will be +, as long as it is in the first i/2 elements if his array, and will be — otherwise.

That amounted to a sum of binomial coefficients that I didn't know how to reach a formula for.

By the amount of people who solved it, I assume the answer had a completely different approach...

Edit: just as an example, a[0] will always (i.e. 2n choose n times) be with a minus, and a[2*n-1] will always be with a plus.

The trick is

It does not matter how you split the array, the cost is always the same

I noticed it accidentally while looking at different partitions

That is so cool damn it xD

No matter which arrangement you take, cost of partition remains the same. So just find the cost for an arrangement and multiply by total possible arrangements i.e., 2nCn.

WitchOfTruth Yogi79 What do you mean by the cost of the partition is same ?

Sum of all differences

Let's say the array is

`1 2 3 4 5 6`

Total cost is 5 + 3 + 1 = 9

Total cost 5 + 1 + 3 = 9

No matter how you swap elements, it will always be 9

Wow! that's an amazing observation, just curious how did you come up with it ?It is very difficult to arrive at it analytically.

I wrote down a couple of partitions for n = 3 and tried to figure out some non-quadratic formulae, then just observations

Yup... I just noticed that even though I knew it was non-increasing and non-decreasing, I tried solving it for non-increasing and non-increasing....

LOL

Can someone provide a testcase where this would fail ? It ofcourse seems the wrong solution looking at other peoples answers but I'd like to know why :/

https://codeforces.com/contest/1445/submission/97349096

I believe you did not consider the case where q is prime (so then divs would be empty)

Is CF PREDICTOR not working ? I think it's showing wrong rating prediction .

how can u say that u did't participated in the contest??

Yeah I think it is broken because it has been showing wrong predictions for some time now. Maybe the ranking algorithm changed.

Can anyone tell me how C was solved because I can't wait for editorial. I bet it needed some witchcraft of math to get it. My thoughts were that if p % q != 0 you print p otherwise you know that p is divided by q and I could do nothing from there. I guess math is the reason I will never rank up. I guess I just need to solve all math problems until 2000 to be able to rank up from expert.

you can read tutorial it is out now.

97340796

So many people got FST in D1C...

I was solving D1B in math all through the contest, but not until last five minutes did I find the pattern to solve the problem. I had no time to complete my code. It was the worst thing I met today...

I was also trying to solve some double summation formula in fast way to solve this problem.

E is very close to what I do in my uni research. In short it is computing treedepth of a line graph of a tree. I was even reviewing one paper about problem which was related to that one, but I didn't inquire on how to do that specifically and papers I've found were too long too read. There is a fair share of papers tackling this problem and in fact it is possible to solve it in

linear timeas proved here https://sci-hub.se/10.1007/s004530010076Pretests for Div1C are soooooooooooooooooooooo weak!!!!!!!!!!!!!!!!!!!!!!

I failed sys tests in DIV2 C because of precision issues in python!! urghh! So stupid of me writing

instead of

Thanks for strong pretests!

Tfw I FSTed on C because I read the input wrongly. How did I pass pretests :thinking:

(My code uses 0-indexed group numbers but I read group numbers in the input and forgot to subtract 1 from each of them oof)

Obviously Codeforces is not to blame but I discovered something I didn't really know before. Thought it might be useful for others.

So basically my approach was if the prime factorization of q exists in p such that for each prime factor and its respective power in q, there exists the same prime factor with >= power in p and this is true for all prime factors of q then I would have to try and set one power less of one of the prime factors of q in p and find the largest such number.

This obviously works in theory but what I didn't account for was that pow() in C++ takes only double as arguments, converts everything down to double due to which for larger bases and exponents which were still in long long reach, there was inaccuracy in the result. Implemented with custom pow() it works perfectly.

Very interesting, thought I'd share. Here are my two submissions :

97340883 97357774

PS: RIP Rating :/

Everyone learns not to use pow() the hard way xD

Anyone faced issues in Div2 C question with PyPy3 submission where sys.maxsize was potentially used. My submission for the 2nd set of test cases, the 4 test case is giving the correct result 1 locally but on submission, it's showing participant output as some other 10 digit number. Then I used 10**20 instead of sys.maxsize it worked (but logically this change is not required).

sys.maxsize depends upon the 32bit vs 64bit OS being used. Codeforces uses 32 bits thus my answer was coming wrong online.

Fastest Rating Updation : )But with wrong name color.

(It seems that CodeForces predicted my future.)

Same happened with me also but between Expert and Specialist

Hello,FST forces! :)

This round is successful,but...

We all passed during the contest time,but all failed in the system testing.

Although our wrong solutions were hacked in the end,I think this is still one of the shortcomings of this round — pretests are too weak, leading to the wrong solutions must rely on the data submitted by users.I think you can strengthen pretests the next time.

If we can get the WA result during the contest time,perhaps we will pass it.That's a pity for us.

Wrong solutions are wrong because contestants don't test them properly, not because the pretests are weak. It is completely in the contestant's power to test more thoroughly, and thus not depend on the whims of fate, authors, pretests, or whatever else.

Why even have pretests then?

There are three test groups: samples, pretests, and final tests. Ideally:

Samples help to understand the problem statement.

Pretests catch obvious flaws in a solution.

Final tests let only the correct solutions pass.

As you can see, each group has its distinct purpose.

The formal rules regarding pretests can be found here, and the contest format overview with a section on pretests is here.

I think the question is vague, and tried to not imply any specific interpretation, as it would most probably be wrong. If the answer turns out to be unsatisfactory, please be more specific.What can't be an obvious flaw?

Thanks for this great contest!

There are only one test in pretests of problem C except samples whose answer is not C(k,2). (I guess all of the tests in pretests are random graphs with fixed number of nodes and edges)

Thanks for strong pretests!

To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove cheaters and update the ratings again!

Can someone tell what is the minimum constant rank someone should keep, to become expert?

Edit, I mean in Div 2

since u asked minimum, i would say 1, be careful you might become red

I don't know if you can become red, if you come 1 in Div2

A consistent 1000 should be a low-to-mid expert, although I'm not very sure.

However, this is probably pretty useless, since you can't just say "I will be rank 987 for round #X". Just aim to solve more problems and learn more about solving problems :)

Just look in the standings table the rating changes of participants on that level.

I'd say you need to be around top1500 in contests like that and around top2500 in isolated div2 (because there is higher rating threshold)

I usually dislike the usage of mod $$$998244353$$$ and favour $$$10^9+7$$$, but this time it was hilarious because input in B was up to $$$10^9$$$ and it allowed me to hack a solution which assumed the input is less than mod. Nice.

P. S. Thanks for cool pretests in C! Admire that.

Oops

orz, thank you for your hack, you saved me from FST.

please explain why my code is not passing all the test case.

My logic is — Both the array is already sorted so i reverse the array b and calculate the sum of a[1]+b[1] and a[n-1]+b[n-1]. This will give the possible range of sum of all corresponding indexs .so check the condition only these two will give the answer. Code link-https://ide.geeksforgeeks.org/aPAZIrNwTO

Are you dumb? Can't you provide the link to your submission instead of copy pasting the whole code, can't you see how ugly it looks!

Thanks for your advice ,sure i will take care of that .

Are there somebody know the feature of test 29 on Div.1 C, which I FSTed on it.

Idk if it's normal or not but I'm specialist with 1300 rating

After this contest, my rating has increases by 159. And now my rating is 1328. But yet it shows that I am newbie. Has the rating system changed or it is a system problem?

Thanks for the nice problems!

My Div1C failed system test because I literally forgot to write a part of the solution. Surprisingly, pretests didn't catch that.

Contrary to some other expressed opinions, I think it's a Good Thing. It's good when the contests teach us to actually test our solutions, instead of being given an instant and omniscient check on a silver platter.

Solving problems, as a general skill, shouldn't depend on an oracle instantly telling you whether your solution is completely right, or has flaws. Some of the skill is to be able to gain confidence that you actually solved the problem, all by yourself.

Easy way to avoid a lot of C FSTs: just make a lot of small test cases and, since the graph in the input doesn't have to be connected, you can just merge them all into 1 test case.

Anyone knows why rating changes of this round are rolled back?

Never mind. It's rolled back now :D

Dreams come true ;)

Congratulations!

Thanks!