Всем привет!
В воскресенье в Москве пройдет XVIII Московская командная олимпиада — командное соревнование для школьников, проходящее в Москве как отборочное соревнование на ВКОШП. Над туром работала Московская методическая комиссия, известная вам также по Открытой олимпиаде школьников по программированию, Московской олимпиаде для 6-9 классов и олимпиаде Мегаполисов (раунды 327, 342, 345, 376, 401, 433, 441, 466, 469, 507, 516, 541, 545, 567, 583, 594, 622, 626, 657).
Раунд состоится в 01.11.2020 14:05 (Московское время) и продлится 2 часа. В каждом дивизионе будет предложено по 5-6 задач. Раунд будет проведён по правилам Codeforces, будет рейтинговым для обоих дивизионов.
Задачи соревнования подготовлены vintage_Vlad_Makeev, NiceClock, ismagilov.code, vintage_Vlad_Makeev, KiKoS, wrg0ababd, ch_egor, Roms, voidmax, DebNatkh, budalnik, Endagorion, craborac, 300iq, cdkrot, LHiC, vintage_Vlad_Makeev, V--o_o--V, grphil под моим руководством, а также GlebsHP, meshanya, Endagorion, Zlobober и Андреевой Е. В.
Спасибо adedalic и KAN за координацию раунда и вычитку оригинальных задач МКОШП, meshanya и cdkrot за перевод условий, а так же MikeMirzayanov за системы codeforces и polygon, который использовался при подготовке задач этой олимпиады.
Всем удачи!
UPD1: Спасибо Um_nik, satashun, mraron, ustze, Karavaiev, KKiYeer за тестирование.
UPD2: Разбалловка:
Div.1: 500 — 1000 — 1500 — 2000 — 3000
Div.2: 500 — 1000 — 1500 — 2000 — 2500
UPD3: Разбор
UPD4: Победители!
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
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 rated
Clarifications 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.
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 :(
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.
Last time when I saw this many reds, I saw an accident.
notice the unusual time)
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
Why so many authors this time??
do you have any problem??
All the best for everyone who are giving the contest !!!
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.
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.me/blog/entry/84198?#comment-717474
this is first time i have ever solved 4 questions in div2,just hoping not to fail system test
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:
I 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 q will 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.me/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 6Total 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.me/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 time as proved here https://sci-hub.se/10.1007/s004530010076
Pretests 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
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!
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?
Dreams come true ;)
Congratulations!
Thanks!