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, 626, 657, 680, 704, 707, 727, 751).

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/06/2022 12:55 (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 cookiedoth, shishyando, gmusya, Tikhon228, ligaydima, Siberian, isaf27, I_love_myself, talant, KiKoS, _overrated_ guided by cdkrot, vintage_Vlad_Makeev, GlebsHP, Zlobober, meshanya, ch_egor, grphil, voidmax, fedoseev.timofey, Endagorion and Helen Andreeva.

Thanks to DmitryGrigorev and KAN for the round coordination, statement translation and preparation of problems for the second division, and also thanks for MikeMirzayanov for systems Codeforces and Polygon, which was used to prepare problems of this olympiad.

Also thanks to low_ and Jeffrey for providing an additional problems that helped to create (I hope) a balanced problem set for the round.

Good luck everybody!

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

**UPD1**: Winners!

Div. 1:

Div. 2:

**UPD2:** Editorial

Back at it again :')good luck everyone! :)

As a supporter I'd like some contribution pls thanks ^^

My favorite part of a Moscow round is seeing this list grow one number longer.

My favorite part of a Moscow round is problems with n <= 10^9 with n*sqrt(n) intended solution and Time Limit of 0.1 seconds.

Dear contest, I know that you and your siblings feature beautiful problems under short periods of time, which proves to be quite challenging. As a result the rating dropping haters downvote your announcement. Please try not to take this very seriously. the haters don't know what they are doing.

Regards, that one random contest orzer (and rating admirer)

Unlike other cf rounds, this one doesn't have testers

I now firmly believe that words have power and can change life, I got FST on B :'(

gl everyone! My first round with green rating, hopefully i dont lose it after this one :)

don't get your hopes too high on this one, GL :)

Another Div $$$0.5$$$ / Div. $$$1.5$$$ round?

Actually, your prophecy has come true!

So much contest this week :)

Intresting!!

How many tester you want to make good prestests.

Admins : Yes

Notice the unusual time(is quite usual these days) :)All the best everyone, have a positive delta!

The unusual timing struck back but fortunately, this time it's a Sunday.

Unusual time with unusual 20 minutes delay

Boycott russian olympiads until the war is over! How can they casually host an informatics olympiad while Ukrainian schools lie in ruins? snark already shows his solidarity by postponing GPs, you should do as well

Go to Hell! Why you think your opinion matters?

Everyone understands your concerns, but I don't know how it is going to help.

When we will get score distribution for the contest??

Only 40 minutes left, And the score distribution haven't been published!

6 min Left and still no score distribution !! Does Anyone has idea What's going on

And the contest was over, still No score distribution

Good luck everyone!!!!

first contest without score distribution? or waiting more delays?

good luck everyone!

SCORE DISTRIBUTION?

Damn!! what a contest..Hardforces.. Logic for B??

Sort the array. Take the sum of all elements except the last one. For one football, this sum should be greater than the largest element. Else the count is the difference between those 2.

isn't this the logic for A?? i want B

Corner case: if all elements of the array are 0, print 0.

Else, Calculate the sum of the array and call it s. Let ans be 1.

Then iterate through the array and make ans equal to

max(ans, a[i] — (s — a[i]));The idea is that, for each player, you cannot make him pass the ball to himself again but only to the other players, and that means that for one ball, he can do only

min(a[i], s — a[i])passes. For the rest of the passes he has to kick another ball for each hit.More than that, we have to consider only the maximum of the array. The following code passes:

sort the array and if a[n] > 1+a[1]+a[2]+...a[n-1],the answer is 1+a[n]-(a[1]+a[2]+...a[n-1])-1,otherwise you can always use at most one ball to complete the session,the answer is 1 or 0.

Problem C & D , both seem very interesting.

Any hints on how to solve C? Also , can D be solved using two pointers method? if so then how , or any other method of solving , if you can help, Thank you !!!!

Do you see how you can solve this in 1-D?

Try to think in the way we calculate prime numbers using sieve

How to solve Div1B?

brute force from 1 to sqrt(C)

Sort a. Now, for each unique a_i, iterate over all possible quotients k when a_i divides some a_j. So a_j has to be between [a_i*k, a_i*k + a_i-1]. Check if there is any number in this interval using binary_search. If k is not found in a and there exists an a_j in given interval then "No". I wonder if this would TLE on system tests.

Let us assume that the value of floor(x/y)=a.

Then the maximum number of distinct values of a for any fixed y is c/y.

We can bruteforce for all pairs of y and a in ClogC. Once we have bruteforces we have to find if any other number from the array(i.e. x) gives us the required dividend a . This can be done using prefix sum of the frequencies.

If you fix the value of x, then if you take the value of y in range x...2x-1 floor(y / x) will be the same. So the solution is very similar to Sieve of Eratosthenes. First you fix the value of x, then you fix y's like (x, 2x, 3x...) and if there is some number in range [y,y+x-1] you should check whether (y/x) also appears in our array. You just can calculate cnt_x for every x and then calculate prefix sums on this array. Sorry for my bad English.

Bro can you help me...I did the same still tle 148674159

Instead of the map you can use something like a frequency array

Now it's showing tle on test 3 148682603

Now it worked after using unorderedmap 148682987 What was the difference in map/unorderedmap/freqarr ?? map and freqarr didn't work. But u_map worked :|

Problem statement: The array is good if for each $$$x$$$ and $$$y$$$ (s.t. $$$y \geq x$$$), $$$\lfloor{y/x}\rfloor$$$ should be part of array as well.

First, the number 1 should be present in the array.

For every number $$$x$$$ in the array, the number of elements $$$\lfloor{y/x}\rfloor, \text{where } y \geq x$$$ is at most $$$c/x$$$ where $$$c$$$ is the largest value in the array.

If we just iterate for each $$$x, y$$$, the time complexity will be $$$\mathcal{O}(n^2)$$$.

Instead we can iterate on $$$x, j$$$ where $$$1 \leq j \leq c/x.$$$ For a fixed $$$j$$$, if there exists a number $$$y$$$ s.t. $$$\lfloor{y/x}\rfloor = j$$$, then $$$j$$$ must also exist in the array.

The condition to check if there exists a number $$$y$$$ s.t. $$$\lfloor{y/x}\rfloor = j$$$ can be translated to check whether there exists an element in the range $$$[j * x, j * (x + 1) - 1]$$$. This can be done by prefix sums.

Overall time complexity of this algorithm will be $$$\sum_{x=1}^{c} \lfloor{c/x}\rfloor $$$ = $$$\mathcal{O} (c \log c)$$$

Why 1 should be present in the array?

Answer should be yes whenever we have 1 in our array.

Almost straight up bruteforce in $$$O(N\sqrt{C})$$$ passes: 148611843

UPD: I am not sure about correctness of this approach, if someone could prove it or hack it.

I thought $$$O(10^{6}\sqrt{10^{6}})$$$ $$$=$$$ $$$1e9$$$ gets $$$TLE$$$ $$$:/$$$

Hey, can you explain the j<i&&j*j<v[i]; part in your code, please? How can I differently type that? I tried to do D like you, I just changed that part, but it fails on 31st test.

Rephrase it as: check only first $$$X$$$ numbers, where $$$X = \sqrt{v[i]}$$$

You can rewrite it also as: $$$j < min(i, \sqrt{v[i]})$$$

Looks like my D is $$$O(M \log^2)$$$ but barely fits within TL on pretests. I should be able to make it $$$O(M \log)$$$ but I already spent way too much time on it and was rushing to save at least some points.

Problem B was confusing!

5 seconds before the end of the contest, I clicked the submit button and... my solution was not sent... Sad...

Div2 A wording could have been better. I got WA and couldn't solve the problem because I thought we could make multiple jumps just could not repeat jump of size x.

SAME XD , i forgot to notice that we can only jump once, resulted in 4 WA's thinking what am i doing wrong.

it was written in bold so problem writers cannot be blamed for it :D

Yup ::_;; my eyesight too bad xD

this part is in bold "no more than"? what does that even mean?

It would be much clearer if this part was bold "you can make a non free jump only once"

no more than one means either 0 or 1

wording could have been better? it's literally there, they just put no more than in bold instead of once, your reading should have been better

Both D and E are hard to implement .

Totally agree!!!

I am still debugging my 300+ lines in D...

Div 2A should've been translated better, the statement was complicated man ;(

Exactly , use a better translator , not solving A within first few minutes really spoils the mood

What even was B? Looked very confusing. Almost cried seeing 4k people solve it and here I was without even any direction T_T

I made video Solutions, for Div2 A-E

No more contests in unusual timing please. It conflicts with many people's routine and only a few people participate. Also contests around this time turns out to be bad

I am curious to know, on what basis are the timings of a contest decided? Is it according to the availability of contest admins & testers (for clarifying problem statements etc.)?

how to solve div2 c?

calculate fox x and y

thank you,I think I get it

calculate ans fox x and y seperatly

colorx[i] — list of coordinates x with color i

sort(colorx[i])

ans +=sufcolorx[i][j] — colorx[i][j]*(colorx[i].size()-j+1);

Div1C/Div2E looks like a somewhat classical problem, but i could only think of a quadratic solution. Could anyone give me some hints?

My idea: calculate # of strings such that the first i characters from each one are equal to the first i characters of t. then, i+1-th character from every string must be lexographically smaller than the i+1-th character of t. You also have to use a data structure like bit to know how many "good" characters there are for each i and compute modular inverses for some products.

i used segment tree for problem E

Implementation contest :(

Div1F doesn't seem so hard(If it's correct that after contracting three-edge-connected components as single nodes, the graph would be a cactus.), but it requires tooooooooooooo much implementation.

It also needs some effort to code Div1E.

Where is the Solution？

In Problem F, I figured out how to solve the problem on cacti, but do not know how to find 3-edge connected components :)

My opinions:

All problems are decent OI-style problem, but E and F just do not fit into Codeforces contests due to implementation issue. It will be better to make F on cacti.

You can find it in Library Checker. lol

Why does this TLE?

https://codeforces.com/contest/1649/submission/148571491

It's O(n)

EDIT — it AC'ed now, unsure why it was TLE earlier.

Next time try to store sum(l) and max(l) so you only compute them once

Well, I am so sad of getting FST on B -__-, Why weak pretests :(((

Why there's no test of maximum n in pretests ?? Why?? I just changed maxn to 1e5 and it got AC :(((

What the ridiculous test in Div.1 C, if you don't take modulo in the end, you will print

`998244353`

and get fst. :(I couldn't imagine that someone can come with such a test so I just ignored it during the round :((

It's a common thing though and happens all the time in EDU rounds, as such tests are not that hard to come up with. I remember sum did a whole lot of hacks in some recent EDU using this modulo flaw in a couple hundred solutions.

Almost half of my friends are hacked because of it.fortunately,I didn't lock the problem...

thanks for STRONG pretest!

I

can't findsome sort ofreport button in messages. Should I report that somewhere and in what way?Send him your code for B now. Also, don't forget to apologise for not sending your code during the contest. :D

Why people are so desperate .. Come on man work hard and be proud of yourself . This guy surely don't have any self respect . Got left ignored for whole contest . Damn guys Life ain't that easy. Don't make it more easier ..

148588961 I had FST in a test already had on pretest (test 13) ???? MikeMirzayanov can you rejudge my submission pls. 148606321 I have accepted after contest with exactly code

Same with me.

https://codeforces.com/contest/1648/submission/148554934

https://codeforces.com/problemset/submission/1648/148608334

I would like a rejudgment please MikeMirzayanov.

Same. 148582657 148611197

why so many downvotes ?

Although I got fst on Div.2 E, my ranking didn't drop a lot, because many ahead of me got fst too. I think this contest showed a good way to deal with the problem of too many people fst.

But on the same problem, Div.1 C, I was not able to keep my rank after getting fst. I'll end up getting a negative rating change. :(

What is fst?

148593938

Can some one hack this?

Or is it correct?

Done

Could you please hack 148593938 as well?

done

weak pretestTATI think Div.2 B is an interesting problem. In my opinion it's even more difficult than C,D and E. I spent more than 40 minutes on it. :D

~[retracted]~

Maybe you solve such problems for te first time.

how to solve 1D using segment tree. plz help

Back to Master again,Thank you :)

:D

weak pretests in problem D. I use this code to pass the pretests.

codeIn this statements,the elements in the vector aren't changed,and I suppose it changed and do something else. It passed the pretests,but fst on test 24.

D: rewrite the objective function as "maximize{$$$l<r$$$} $$$a_l + b_r$$$ — (cost to cover $$$[l, r)$$$)"

I used divide and conquer to cope with the restriction "$$$l<r$$$" in each step, make graph with edges

$$$l$$$->$$$r$$$ with cost $$$k$$$

$$$x$$$->$$$x-1$$$ with cost $$$0$$$

S->$$$l$$$ with cost $$$-a_l$$$

$$$r$$$->T with cost $$$-b_r$$$

calculated the shortest path from S to T In order to shrink time complexity, I had to care edges outside $$$[l, r)$$$ (only $$$\mathrm{O}(r-l)$$$ edges have to be taken into consideration)

Idea itself was interesting to me, but implementation was too heavy for an almost retired person.

to a graph，nice idea！

We found a lot of interesting solutions to this problem, almost half of participants' successful submissions (it was like 5 out of 10) on the olympiad had it's own approach. And all of those solutions weren't easy to code as well.

contest is good , except some meaningless corner case which leads to FST

Div1.D has pretests that suck

Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!

Codeforces is not trash bin.How to hack problem C in div 1?

How to make the answer multiple of $$$998,244,353$$$ ?

DeCantor Expansion

O！ Thanks a lot!

ya problem setters really love weak samples and pretests... i dunno the reason.

jiangly's codes are so clean ...like seeing latex text

Did someone understand what is special in test 53 in div1 C? I can't get it for now

You have used break before making ok = false.

I made a submission for problem A. Link I am confused as to why it's failing for the testcase:

I think its answer should be 4 but it's given 5. Can someone explain how 5 is the answer for this testcase ?

you can only make

onejump.You can make exactly

onejump This video editorial might be helpfulCannot describe it with any words.jpgIf you are/were getting a

WA/REverdict on any of the problems from this contest, you can get a small counter example for your submission on cfstress.comProblems added: "A, B, C, D, E, F" from Div-2, which translates to "A, B, C, D" in Div-1.

If you are not able to find a counter example even after changing the parameters, reply to this thread, mentioning the

contest_id,problem_indexandsubmission_id.problem A really bad statement..

My exactly same code for div2 D got TLE during system test and AC after the contest, can this be rejudged? :'(

Hello, please hellp me. I need a hint for problem C. I have no idea

try to solve it for x and y separately

you can get a list for each color using map/unordered map (i used map) then you iterate through the map and do following thing:

At first, you have to notice that all points of the certain colour are already sorted by x; you can calculate the distance from the first point, then calculate for others using that value then you have to sort all the points by y and do previous steps again

i didn't explain the whole implementation, but you can see my submission there: https://codeforces.com/contest/1649/submission/148590975

thank you so much, I'll try to implement

good luck!

what are the downvotes for on the post this time? did just a lot of people not like the div2A statement?

Weak pretests perhaps? There were quite a bit of people getting FSTed in Div1C.

I have a question in problem A div 2 why this case result is 5, not 4?

6

1 0 1 1 0 1

Because you count the land on which you jump too.

If it was 4, then it would count that you jumped on the 0 (that is on position i = 4), not on 1 (that is on position i = 5)

thanks so much

You're welcome buddy :D

Thanks for great round!

Can anyone tell me in Div2 problem D why answer of 1 3 3 7 should be no as 3/1 = 3 which is present in the array.

any pair... 7/3=2 not present in the arrayThanks, I thought that if any pair satisfy the given condition then array will be integral array