Hello!

Right now happens the first tour of the Open Olympiad in Informatics, and tomorrow will be the second one. This contest is prepared by Moscow Olympiad Scientific Committee that you may know by Moscow Team 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).

Open Olympiad consists of the most interesting and hard problems that are proposed by a wide community of authors, so we decided to conduct a Codeforces regular round based on it, which will happen on Mar/07/2020 12:35 (Moscow time) and will be based on **both** days of the Olympiad. Each division will have 6 problems and 2 hours to solve them.

**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 Open 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 of this competition were prepared by meshanya, cdkrot, wrg0ababd, vintage_Vlad_Makeev, DebNatkh, dimaskovas, voidmax, okwedook, ch_egor, V--o_o--V, Sender, grphil, mingaleg, KiKoS, Endagorion, Nebuchadnezzar guided by cdkrot, ch_egor, vintage_Vlad_Makeev, GlebsHP, Zlobober and Helen Andreeva.

Problems for second division were prepared by vintage_Vlad_Makeev, ch_egor and MikeMirzayanov, to who we also want to say thanks for the Codeforces and Polygon systems.

Good luck everybody!

**UPD1:**

The scoring distribution for both divisions is standard: 500 — 1000 — 1500 — 2000 — 2500 — 3000

Due to the official competition source codes of other participants will not be available for an hour after the end of the round.

**UPD2:** Editorial

**UPD3**: Winners!

Div. 1:

Div. 2:

3 years ago? wut?

Yeah, this announcement is quite vintage.

oh! so problems would be vintage as well.

Hope for no accident!

im ok meme fire!

3 years ago :D

Please no mathforces!

Blog post from 3 years ago.

Dude I thought my "5 months" were creepy enough. :D

What is the onsite format and how will both days be combined in one round? If the onsite is a 5h contest every day, then joining both in a 2h one seems brutal.

The are two days, each has 4 problems for 5 hours.

Each of these problems have subtasks, so they may be given I suppose.

Paşa

The announcement said that this round "will be based on both days of the Olympiad. Each division will have 6 problems and 2 hours to solve them."

What does "both" means?

A. The problems of two divisions are same problems;

B. No problem exists in both division simultaneously;

My english is poor. Could anyone help me with it?

.

Here "both" means that problems from two days of Olympiad will be used for Codeforces round.

Each division will have 6 problems. Some of them are common, some of them are not.

Got it, thx :)

Two interesting problem setters in this round are vintage_Vlad_Makeev and Vlad Makeev

As you can see, preparation of this contest started a long time ago (preparing most of the problems started even before announcement writing), so some of them we prepared by vintage Vlad Makeev and some by modern Vlad Makeev.

preparing most of the problems started even before announcement writingYou mean more than 3 years ago? XD

Should I prepare my vintage Paint MS for a vintage meme about vintage_Vlad_Makeev , vintage_Vlad_Makeev , vintage_Vlad_Makeev and that other guy whose handle I'm not going to type from my phone?

Plz make a meme about yuhao

What's the score for each problem?

The scoring distribution for both divisions is standard: 500 — 1000 — 1500 — 2000 — 2500 — 3000

Can anyone explain how and how much rating increases or decreases depending on what factor ? I read this FAQ from codeforces Codeforces FAQ rating and div link but it is still not clear how much it changes and on what factor?

This might be the simplest explanation: Based on your rating before a contest starts, you are given an "expected rank", ie, you are expected to perform that well. If you outperform your expected rank then your rating increases and if you underperform, your rating decreases.

You can see the formula here. Though it is important, I don't care that much and use CF-predictor with live rating changes instead.

There are 11 Candidate Master among Div.2 registration and 9 Expert among Div.1 registration. When will it be corrected?

Who else checked the date? :p

Is this contest rated?

Yes, vintage contests are usually rated.

Schools are like:

Taught in Class: Div2 A

Solved for practice: Div2 B

Homework: Div2 C

Exams: Div2 D,E,F

After solving C

Why are we not allowed to copy others code in our system to check for hacking? We are only allowed to see others code. Previously we were allowed to copy also (around 7-8 months back).

Only in edu round, you are allowed to copy.

How to solve Div 2 D?

Problem Div1 B was Info1Cup 2017 XORsum

Its a little difficult to understand from the editorial given. Can you simplify the approach to solve this question?

Here is more detailed.

How to solve Div2B

Hate SpeedForces.

How to solve div2 B??

Thanks for this great problemset, I haven't seen better one on Codeforces in a while.

i already told you swistakk as the age passes contests become much and much better as they were in your young days.

How to solve div 1 B. My time complexity was O(n log(n)*log(1e7)) which gave TLE on test case 4.

I tried to find for every $$$k$$$-th bit how many number are there such that $$$Bi+Bj$$$ $$$mod$$$ $$$2^{k+1}$$$ $$$>= 2^k$$$ where $$$Bi=Ai$$$ $$$mod$$$ $$$2^{k+1}$$$. I don't know if this is correct I had some bugs in code.

Exactly the same idea..

Same problem with me too, I implemented binary search instead of using lower_bound. It is giving TLE on test case 4. People who have used lower_bound did not get TLE. My submission: 72730048

How to solve div2 D?

What is testcase 6 in div2C?

maybe something like 6 ))()((

What is the expected answer for that?

6

I have no idea for div2 D!!!

How to solve div 2 D? Was looking at a trie based approach but how to handle carries properly?

To calculate if there's a carry in n-th binary position you can modify array a, and set bit n and higher bits to 0 in every number. Then after sorting array it is easy to count pairs of numbers with sum of 2^n or more. Pair counting step can be done in O(n), but I used binary search, which is n*log(n), and it worked fine.

Did anyone solve with idea that converting to problem for binary array and do some stuff. btw I had something to do so I couldnt continue competing.

How to solve DIV 2D?? is it based on calculating freq array of all pair less than o(n^2) if yes then how?

freq array off all pair can be calculated in o(nlogn) time using FFT but I receive Memory limit.

sorry. it can be calculated in o(10^7log(10^7)) time.

Before the contest: I want to solve Div1 D!

After the contest: How to solve Div1 B and C ??

I have never seen a shitty contest like this. The problemset(Div.2) was completely imbalanced. Disgusting!!!

Div2D/1B was copied : https://oj.uz/problem/view/info1cup17_xorsum

Would still like to know how did you guys solve it ?

My solution to B: A sum $$$s = a_i+a_j$$$ (w.l.o.g. both $$$\lt 2^{k+1}$$$) has a bit $$$2^k$$$ set iff $$$s \ge 2^k$$$ and either $$$s \lt 2^{k+1}$$$ or $$$s \ge 2^{k+1}+2^k$$$. For each $$$k$$$, use a Fenwick tree to count them. $$$O(N \log^2)$$$ with a good constant.

C: Consider vertices from the right half. Let's ignore vertices with no edges to the left half. Merge vertices with the same sets of left neighbours. The answer is the GCD of the total weight and weights of all these merged vertices. Complexity: $$$O(M + N \log)$$$ with hashing.

Proof: consider the answer $$$g$$$ and its divisor $$$d$$$, which must divide the total weight. Among the merged vertices whose weights aren't divisible by $$$d$$$, find one with the smallest degree. If we take all vertices from the left half that aren't adjacent to it, then we take all other vertices from the right half, since all other merged vertices have $$$\ge$$$ degree and those with equal degree don't have the same set of neighbours, so their weight (total weight — weight of this not taken merged vertex) is indivisible by $$$d$$$.

D: There's a reasonably straightforward DP: for each aggressiveness $$$l$$$ and each suffix of already chosen candidates, calculate the maximum cost if we have $$$j$$$ people that fought and crossed over to aggressiveness $$$l+1$$$. This is $$$O(N^2M)$$$, but we can notice that the number of people that can cross over to gradually higher $$$l$$$ decreases exponentially, so we can remember the maximum $$$j$$$ that resulted in a reachable state for each $$$l$$$ and suffix. Complexity: $$$O(ok)$$$ probably.

Another proof of C would be the following.

For a sets $$$S$$$, $$$T$$$, define $$$\gcd(S, T)$$$ as $$$\gcd$$$ of sum of elements of $$$S$$$ and $$$T$$$. We note the following, if $$$A \subseteq B$$$ then $$$\gcd(A, B) = \gcd(A, B - A)$$$.

For two vertices we want $$$\gcd(N(u_1), N(u_2), N(u_1) \cup N(u_2))$$$, if $$$A = N(u_1)$$$ and $$$B = N(u_2)$$$.

Notice that all these are all the sections of the Venn Diagram of $A$ and $$$B$$$. We can easily generalize to more sets (just use induction).

We effectively have to sum all the nodes that are in the same section of the Venn Diagram. Two nodes are in the same section of the Venn Diagram if and only if, they are in the same $$$N(u_i)$$$'s which is the same as saying they have the same left neighbours. $$$\blacksquare$$$

The dumbass I am, I didn't realize that the problem was trivial from here and managed to not solve it. :'(

I don't know what's wrong with this code for Div2 B. It's giving WA on testcase 3. Can anyone please tell my why??

## include<bits/stdc++.h>

## define lli long long int

## define ulli unsigned long long int

## pragma GCC target ("sse4.2")

using namespace std;

## define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)

## define time cout<<"\nTime Elapsed: " << 1.0*clock() / CLOCKS_PER_SEC << " sec\n";

int main() { fast; lli n,m,k; cin>>n>>m>>k; vector<pair<lli,lli>>vp; for(lli i=1;i<=sqrt(k);i++) { if(k%i==0) { vp.push_back({i,k/i}); if(i!=k/i) vp.push_back({k/i,i}); } } /*for(auto i:vp) { cout<<i.first<<" "<<i.second<<"\n"; } */ vectora,b; for(lli i=0;i<n;i++) { lli x; cin>>x; a.push_back(x); } for(lli i=0;i<m;i++) { lli x; cin>>x; b.push_back(x); }

}

can someone tell me how to ask question so that i will not get so many downvotes. I am new to codeforces. THis was my first contest. And i don't know what i did for getting so many downvotes

First important thing is to not post long code directly into your comment. Use a link instead

Contest was unbalanced. Difficulty level between C and D was very wide.

The gap between Div2 C and Div2D doesn't nice at all

For Div1 C, I made a randomized solution, which is completely wrong. I submitted it 16 times before it got Pretests passed. So if I count with 1/16 chance to pass 12 tests and with about 96 main tests (8*12), then I have about (1/16)^8≈2*10^(-10) chance to pass main tests, so about 1 in a 5 billion. I like my chances!

I really wouldn't want to be the one preparing tests for div1C. Not only is it possible to make a correct solution without realising it (see above), it's really easy to make a solution that's almost correct and distinguishing between them reliably is hard.

Oh yeah, it was quite hard to come with idea of strong tests. However there is a test with ~7500 non-zero degrees vertices in left half and exactly one subset of size 5 of vertices that you should handle to find proper GCD and connected graph.

You can try to find such test yourself it's a very nice problem.

You can make a solution by simply comparing neighboring vectors by size and elements instead of hashing. But indeed building strong tests for it are so difficult to me. I prefer preparing problems with easy work in generating data ^o^.

Mine's a randomised and a bit greedy solution as well. (greedily sorting vertices with several comparators and considering all prefix of vertices as subsets to calculate gcd).

It passes systests, submitted after the contest. 72661488

Unfortunately I tle'd systests during the contest with the same soln 72655512 thanks to using endl instead of '\n'. T-T

Greedy comparators used: Sort left vertices in order of how less connected their right neighbours are to left vertices. Sort by degree.

D was much easier than C, in my opinion (just a straightforward dp). Also including isolated vertices in C was pure evil, Took me around a quarter to figure that out :/

Btw is the intended solution to E parallel binary search on the value of each index and then some book-keeping of left and right pointer for each index via DSU? If so, it was a bad idea to have it as E since not many would reach it in time (though it isn't much hard).

Nice problemset overall.

For me it was the opposite: C was very straightforward, I just looked at when some $$$x$$$ divides the GCD, and it was easy to see and prove that this holds when every non-isolated right-side vertex has value divisible by $$$x$$$ (assuming every right-side vertex has a distinct set of connections. If they do not, just join vertices with the same connections). I did get one WA from the isolated vertex case though.

On the other hand, in D I had to work with this monstrosity: 72679047, which I couldn't optimise and debug in time.

Is it just me or is the TL for E strict? I should have used a fast set instead of std::set.

I used multiset, set and segment tree at the same time (for different purposes), 1247 ms on pretests

Seems like my implementation has a bad constant. My solution runs in 3sec on my machine (which is a bit faster than CF), and with fastset it runs in 1sec.

Ok mine is too slow too :(

n log n, TLE systests, byebye

How to solve div1C?

Good Balance!

Div2 D/ Div1 B — https://atcoder.jp/contests/arc092/tasks/arc092_b

As the editorial, my O(NlogNlogMAX) time solution get TLE, maybe my implementation is not optimal enough. By the way, if I use int instead of int_64, I get wrong answer on the same test case, which means within time limits.

Amazing problems, thanks for them!

Btw, statement of F was TERRIBLE, it got so many stupid things I am not even gonna point them out, cause it would take me too long

For Div2, Over 2k solutions for C, and about 100 for D. Quite a shift though

I Hate SpeedForces :(

Good problemset, but as I suspected squishing a 2-day 4-hour(?) contest into a single 2h round is just gonna make it too difficult.

Yeah, it's quite sad that nobody had time for F, I like this problem very much :(

However we dropped some hard problems from original competition to make this contest more solvable, but probably 0.5-1 extra hours were probably required.

Why is this solution to 1C getting TLE on test 72？

link

It seems many other people got TLE on the same testcase.

"Due to the official competition source codes of other participants will not be available for an hour after the end of the round."

Wait a bit or paste the code to somewhere else, if you want to get an answer.

Probably sensible to not paste code somewhere else as that kind of defeats the purpose of making codes not available. Just wait.

A rule that can be broken without repercussions is useless.

It seems I'm getting TLE due to std::cin. Why such a tight TL... Or is it intended to fail solutions with slower I/O?

You are probably just doing it wrong. Using endl or sth like this. It's never an intention to fail solutions with iostream since it is not slower than cstdio when used properly.

Then how to use iostream "right"? I've done nothing but to replace

`std::cin>>a[i]`

with`scanf("%lld",&a[i])`

and it passed.`ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);`

.And

`'\n'`

instead of`endl`

.Thanks,it passed after doing this.

Yes, I already replaced "cout<<ans<<endl" by "printf("%lld\n",ans)" and got accepted in less than one second, after failing by TLE at 72.

After long time i will reach on specialist.

Thank you codeforces .

So all the pretests in Div1B are either $$$n$$$ is even or $$$a_1\oplus a_2 \oplus a_3 \dots \oplus a_n=0$$$... lol

Pretest is weak?

The most important part for Div.1 C is not to use std::endl.

Why does it matter so much? You're printing one integer.

I thought so too during the contest. But it has multiple test cases.

7

Even if one uses the standard ordered map for storing vectors, no problem. Just the "cout" is the problem.

My solution for Div 1 A shows Pretest passed and I did not get any points for it. Does it mean it failed system test or something else? It is weird..

Will I get minus if I got wrong answer on pretest 1?

No penalties for solutions failed on (pre)test 1

I know about NO PENALTIES. But what about getting minus?

You mean something like "-1" "-2"("tried" counter)?

Failing on (pre)test 1 won't be counted in the "tried" counter

Forget about it. I already got minus in rating.

You mean rating change?I didn't understand it :( sorry for inconvenience

Being a master was truly magnificent experience.

Au revoir!

I took part in Codeforces Round #626 (Div. 1, based on Moscow Open Olympiad in Informatics) just now. I passed the pretest of problem A. But the system didn't send my solution into system test. Why does this happen？

Same with me :(

Are you extra registration?

Yes!

I am extra registration too. And did you use m1.codeforces or m2.codeforces.com or m3.codeforces.com?

No i used codeforces.com, the reason seems to be extra registration.

I suddenly accepted. It really confused me.

My submission 72636993 got a TLE during system testing. Submitting the same exact same code does gets an AC!! Also the TLE was on test 5 wasn't it already included in the pretests??

The submissions:

72661261

The below submissions I just added another variable x, just to bypass submitting the exact same code twice. Other than that there is no difference in the codes.

72661081

72661159

72661597

Submissions image

vintage_Vlad_Makeev vintage_Vlad_Makeev ch_egor MikeMirzayanov

Your solution works quite close to time limit. There are always some fluctuations in program working time, so it's just a bad luck that your submission got TL on system tests.

Thanks for the reply.

How come my code for B fail at test case 5 ,which was already present in pretests.

The execution time may be different in runs.

If your code consumed almost 1000ms(e.g:996ms) in the pretests, it's probably to fail in the main tests.

Hello, you know when the rate change?

in several hours? no one knows the exact time.

Okay, I will say it. The pretest for Div1 C is fucking garbage.

I passed pretests using only 580ms. The time limit is 2s. My solution is deterministic, and runs in basically the same time given that the input size is fixed.

It got TLE on test 72.

I then changed from

`cout << ans << endl;`

to`cout << ans << '\n';`

. It now runs in 800ms.It means that it takes at least 1.2s to flush 500000 times, which implies there is no such test where $$$t = 500000$$$ in the pretest (I really doubt the maximum $$$t$$$ in the pretest is even close). Now I'm pretty sure that Codeforces has the policy on problems that the pretest must satisfy i) it contains all corner cases on which some known solution fails and ii) all parameters specified in the problem must hit their respective maximal values. With that knowledge, I put my trust in the problem setters that they have at least complied with the policy and believed that Codeforces actually could handle 500000 flushes better than I thought. Turned out I was wrong on both, LOL.

It would be really great if anyone involved can explain the thought process (or lack thereof) behind the decision not to put such tests in the pretest.

So you knew that flushes could be a problem, but decided to use endl anyway, hoping that jury will comply with some imaginary policy that noone except you knows? Seems like you got what you deserved.

Not including all "simple" types of max tests (and I believe $$$t=500\,000$$$ is one of them) is a questionable decision, especially considering that large $$$t$$$ might be here for a reason. For example, my first idea involved factorizing a number as large as $$$10^{12}$$$, which is pretty hard when you have to do it $$$t$$$ times within 2 seconds.

I did not know how long it takes for Codeforces to process that amount of flushes. I used flushes to debug my solution locally, and forgot about it. I submitted the solution, saw that it passed within 1/3 of the time limit, and was completely convinced that it would not be that big of a problem.

I didn't say that I deserved to pass using 500000 flushes; however, if such tests were present in the pretest, I would have known immediately what the issue was.

For the "imaginary policy" part, feel free to enlighten yourself. Some quotes taken from the document:

Always make tests (at least) with minimum possible, maximum possible and some value in between for each variable and their combinations.

In general, pretests should include: a test with maximum size of input (e.g. maximum n), a test against integer overflow, a few random small tests.

There should be no warnings in polygon, except (if reasonable) "there are tests with input/output for statements [without TeX marks]". ("parameter 't' does not hit maximal value" is one such warning).

I have involved in preparing some Codeforces rounds, I know what I am talking about. I don't pull facts out of my ass. Have a nice day.

First and third points are about all tests, not pretests. Second point only implies that there should be a pretest with sum of $$$n$$$ equal to $$$500000$$$. Still don't understand why would you expect pretests to be perfect.

FYI, here is a screenshot taken from Polygon:

As you can see, the system does warn about pretests being incomplete. In fact, if you insist on trying to nitpick things, the test with $$$t=500000$$$ and $$$n=1, m=1$$$ for each case also gives the maximum input size possible (about $$$1$$$ million more integers to read), therefore it should be included in the pretest (this is rather redundant, since the third quote already pointed that out anyway).

OK, authors are wrong. But still you relied on something that is not written in the rules (for contestants) and got punished. Seems right.

Yeah I mean people also expect each other to not tell a dick joke at the funeral, even if it's not written in the rules, and will be upset (rightfully so) if one does.

But fair point I guess. Sorry for the bad analogy.

Ignore: in prev version Russian colypasted joke

the same situation happened to SeehtEntity. You can consider it as a good experience :3

I guess B and C got swapped :(

so sad, this sentence "Then output k distinct integers (1≤pi≤n), indexes of the chosen elements" in div2 A, Let me misunderstanding, i think it's k distinct integers a[i], not the index of a[i].

Unfortunately, Problem Div.1 B coincides with atcoder ARC092D.. TAT But it's nice problem anyway.

There is a small typo in the input section of the problem statement of the problem Div.1 D.

Finally this code got TLE on test 72...

72676139

To solve this problem,I use gets lol

72676564

Can anyone please tell me why this submission (for Div 2 B) gave run time error on TC 34, as on my compiler, for same case it gives the expected output 0 as answer? https://codeforces.com/contest/1323/submission/72650213

in your solution problem is with this statement " i=v.size()-1 " here v.size() is unsigned integer. make sure to convert it into int before using it like this "i=(int)v.size()-1".

Can someone explain div1D because I can't get much of what the editorial is saying?

Div 2 was shit first 3 very easy and other all was out of mind #fuckedup

zhouyuyang congratulations for rank 1.

Wish Codeforces could be better and better.