Hi Codeforces!

Talaodi, YunQian, xukai and I mazihang2022 are excited to invite everyone to participate in Codeforces Round 858 (Div. 2), which will be held on 18.03.2023 15:05 (Московское время). **Please note the unusual start time.**

This round will be **rated for participants with rating lower than 2100**. We will be pleased to see the participants with a higher rating to take part in our round unofficially as well!

You will be given **6 problems** to solve, one of which contains subtasks. You will have **2 hours and 15 minutes** to solve them. Scoring distribution will be announced later.

We would like to thank everyone who helped with this round:

- errorgorn for coordinating the round. He really helped a lot as it's our first time setting up a round on Codeforces.
- Runtime-Terr0r, maomao90, mana, milind0110, Dominater069, Codula, Everule, fengzhengwei, feecIe6418, AlperenT, 18o3 and rsj for testing the round and providing valuable feedbacks, and for all your help in improving this round's quality.
- Alexdat2000 for Russian translation.
- Talaodi for
~~setting no problems finally~~being our mascot for the round. - MikeMirzayanov for the great Codeforces and Polygon platforms.
- You, for participating in the round.

We are looking forward to your participation. Good luck and Have fun!

**UPD1:** Score distribution: $$$500-1000-1750-2000-2250-(2500+1500)$$$

**UPD2:** Editorial

**UPD3:** Congratulations to the winners!

Official winners:

Unofficial winners:

as the mascot, give me contribution!

Negative contribution?

so i give you downvote.

Although -59,thank you for the contest!

As a tester, I liked to test this round, and hope you will have fun participating :)

As a participant, I want to thank you for the contest!

Thanks very much, I hope this round will be fun

As a grey tester I can say that div3 div4 participants will like the round.

Glhf!

Gray tester

Spoilerwho never was a specialist

As a tester, I hope you enjoy the problems as much as I did.

Tomorrow is the birthday of my most beloved and only uncle. I want to congratulate him on the gift and good deltas after the contest!

milind0110 orz!

As a tester, I enjoyed testing the round. Good luck to participants!

Runtime-Terr0r orz

False, WAtoAC2001 orz

Runtime-Terr0r orz

xox0 Nopenope Tensei8869 lmao__ded orz

Runtime-Terr0r orz

SpoilerYes you are! Never believe anything else.

Runtime-Terr0r orz

vipin orz

Runtime-Terr0r orz!

-is-this-ars- orz

Runtime-Terr0r orz

milind0110 orz

orz

orz

Runtime-Terr0r ORZ !!

1riddhi orz

My first contest as an expert. Definitely not dropping back to specialist

SpoilerI will

orz. CM time

My first contest as a master. Definitely not dropping back to candidate master

SpoilerI won't

Big flex

My first competition to be held during the lessons.

MY ANSWER!I will participate!

lol

Perfect time for Chinese people

Because this round is held by Chinese :)

meow.BUT I HAVE CLASS AT 8:00 meow.

As a tester, I must say that this contest has a problem that got into my favorite problems list. You should definitely participate in it.

which one?

1806F2 - GCD Master (hard version)

As a user, this contest is one of the codeforces contests.

As GPT-4, I will be participating in this Round :) Get Ready Humans.

I'll focus on your performance.

lemme know if you are able to solve div2c

Division 2 is still hard for GPT. What's funny is that GPT is eager to solve hard problems than problem A. For example having a potential solution for problem E which got finally TLE, than coming up with some basic logic for problem A. P.S. I wasn't able to use GPT-4 all the time, even with the paid subscription, it's still limited to 25 requests per 3 hours, LoL...

Got positive delta at least :)

What a great time!

first time a round in which I know so many testers :hype:

What a good time!I love the writers very much!

Hope to get a positive delta!

I believe this contest is good

What should I write? ⚫⁔⚫ Can anyone help me? (◕.◕)

what can be reason to increase contest duration by 15 minutes than usual 2 hour duration ?

As a contestant, I anticipate this Chinese Round to be great one seeing the authors!

Hope to become master again!..

ooh there are a contest again...i feel i have got long time without any contest ... ....actually when you get hacked in two consecutive contest you will need more contests to get your lost point again . i hope ,i have no hacked problems in this contest :)

I wish I could do well in this div

CN round, rating recycling round

HOW DO YOUR E'S SOLUTION WORK? I GET 10* TLE ON 10 NOW! TERRIBLE!

OH,a bad time for me QWQ

Yet another bing chilling round!

damn Dominater069 & milind0110 as testers But VIP tester must be Codula

As a newbie i hope to not be a newbie again...

As a human, I will be participating in this Round :) Get Ready chat-gpt.

18o3 orz

feecle6418 orz

omg subtask for problem F round

Another round with problem C of 1750 score

I didn't go to college and I missed classes to attend the contest

As a newbie, I hope you enjoy the problems as much as I did.

:(

Chinese is to be considerate of Chinese and praise the game time.

Hope rating ++ in Chinese rounds! Good luck!

My predictions to this contestProblem C will be related to number theory (something with primes or gcd)

Problem D will be related to some combinatorics or dynamic programming.

Problem E: something with trees

I will be able to solve only ABC and will lose rating.

Screen it! Will check after this contest.

Similar to the real problems!

i feel that someone told you about the tags of the problems :)

Hope rating++

I didn't solve C.;(

good luck!

WOW the score distribution...

Good luck everybody!Hopefully i will become pupil again.

How can I participate if I haven't yet registered for the contest?

Masterforces!

This round is actually for Masters(Cries in C)

I think I am going to have fun after solving A,B good luck in C am not interested :D

speedforces is back !

Now, this was completely opposite to today's Mathura ICPC prelims. :(

Tooooo Tough.

Hardest div2 C ever :)

I saw names of all problems , ans i was like.....isn't it masters' round?!?!?! :)

I can't solve Problem.B :(

and I will 掉大分

C hurts :(

Dumbest C ever lol. So many cases

I couldn't even solve the subtask for C, generating

anyarray that satisfies the condition, let alone a minimum distance one. All I could think of was an array of all 0's.if n is not odd then you can generate one number n, and all other -1

Is there any optimization for the odd case? Or is it just [0, 0, 0, 0...]?

i think is 0000,but i got wa

Then all q should be 0, however, only when n=1 then the answer is abs(p[0]-p[1])

what if n is odd then?

then q should be all 0s

Damn, I got this right. Not sure why still WA.

I think for n==1 abs(v[0]-v[1]) should be good enough because abs(v[0]-v[1]) gives the optimal solution for every case. Maybe you missed something else.

I realized I missed {0,0,0,0} for n==2. I only considered {2,2,2,2} and {-1,-1,-1,2} I am so mad now.

so if n is odd except n=1 ,all the a[i] is 0?

For every n we try 0,0,0,...,0. Corner case n = 1, for n = 2 try 2,2,2,2. and for n % 2 == 0 we got also -1, -1, -1, ..., -1, -1, n

i forget n%2=0,a[i]=00000

same for me :(

how to prove this pattern is optimal?

I got this by brute forcing on 3rd test case but how do we prove that this is sufficient for the given question?

Brute force leads to an array of -1s and n (e.g. [-1,-1,-1,2]) to be good if n is divisible by 2. But still WA for me :(

Let's face it. I solved D by finding patterns using pure brute force. I don't even know what the hell this problem is all about. But i passed it:)

orz

I think you are the luckiest person on the planet for a moment.Can you describe how you have done.

I observed the sample and found that 2=1*2, 7=2*3+1, 31=7*4+3, 167=31*5+12, 1002=167*6, 7314=1002*7+300, 60612=7314*8+2100. Then I found the pattern of the number behind.

However, it is not correct at first, so I wrote a brute force program:

CodeI found about the 0 cases and finally developed the right pattern. When I finished testing, i got pretest passed.

How C & E?

I like problem D, thanks.

I think we should exchange D and E

Hooooooow toooooooo sooooolllllllllvvvvvvveeeeeeeee EEEEEEEEEEEEE TwT too hard

I'm not sure if i understood C wrong, depending on what i have understood the output in sample 3,4 is impossible. that was a mind F*** for me. from what i understood this condition should be met the product of n elements of the array must equal the sum of the same n elements because we should exclude and include the same elements but HOW. it's either 4 elements 2 2 2 2 or if it's more i didnt find other than array filled with zeros. im sure there is a usage for negative and positive numbers bullshit but couldnt find it

[-1,-1,-1,2] works

god damn it i literally thought of every thing except this.

If n is divisible by 2, then the array of length 2n: [-1, -1, ..., -1, n] satisfies the condition.

I'm not sure if I'll be of any help, since i didn't solve the problem either, but a possible solution is to have m+1 elements be equal to zero, that way we can say for sure a zero will be included in every permutation of size m, thus the product will always be equal to zero.

How to solve C? I went through all possible patterns but still WA.

if n is not odd then [-1,-1,-1...,-1,n] works otherwise [0,0,0...] is one possible solution for all arrays. You also need to take care of corner cases for n==1 and n==2. For n==2, [2,2,2,2] works.

I had a stroke trying to comprehend the problem statement of D. The entire time I solved a completely different problem because I misunderstood the task

can someone tell me why my approach for B isn't right all i did was count the no of zeros and non zero elements . by this i made sure if i can't make all zeros disappear i'll take the smallest non zero element as answer

`the smallest non zero element as answer`

But if you have numbers

`0 3 0 0`

, then clearly answer is 1, not 3.i even put one instead of min and still didn't pass just one doubt the answer is always 1 or 0 right

for

`0 1 0 0`

answer is 2:)i missed this ok thanks ....

Nice contest, I liked all tasks I tried (A, B, C, E)

Seems like Mo's algorithm was not enough for E (at least for me).

One of the toughest Div2 for me.

Anyone, please help me in B?

Minimum is 0 if the number of 0s is more than the remaining+1, since you can place 0s on both ends (consider [0, 1, 0, 2, 0, 3, 0]). Else minimum is 1 if either there are no non-zero values, no 1s, or there is a value that is non-zero and not equal to 1 (consider [1, 1, 2, 0, 0, 0, 0, 0]). Else minimum is 2.

if the number of zeros is <= the number of notZeros+1, you can arrange them (for example) like this: 0 2 0 7 0 2 0 5 0... Here, all the sums of adjacent numbers are >0, therefore, you can pick 0

else if the greatest number is greater than 1, you can arrange it like this: 0 0 0 0 0 7 5 2 2 (there is a sequence of 0s and then the other numbers are sorted backwards) Here, all the sums of adjacent numbers will never be 1, therefore you can pick 1

if the greatest number is 1, you can arrange it like this: 0 0 0 1 0 0 1 0 1 (where no 1's are adjacent) Here, all the sums of adjacent numbers are either 0 or 1, therefore you can pick 2

if the greatest number is 0, you can obviously just pick 1

How do you get this approach?

Can you please tell me more?

And how it is correct always?

0 is a special case. When you have more than (n+1)/2 zeros then MEX != 0; If 0 isn't MEX we look at other numbers from 1 to n. If n-number_of_zeros_in_our_array>=1 it means that this number is MEX, because you can just make an array like that: {actual_number,x,x,x,0,0,0}. Zeros are ignored so we put them at the end to not damage our result. x- are all numbers excluding zeros.

The possible solutions for problem B can be either

0,1or2.The solution can be equal to 0 if the number of zeros in the array is at most half of the elements, meaning we can arrange the elements in such a way that we switch between zero and non-zero elements, like this

[0, 1, 0, 8, 0, 4, 0].The solution can be equal to 1 if the number of zeros in the array is more than half of the elements, meaning we cant wrap the zeros around each element, so what we're going to do, is divide the elements into two sections, zero and non-zero section. It's going to look like this

[0, 0, 0, 0, 0, 2, 1]The solution can be equal to 2 if we have more than half of elements being zero, and the only remaining elements are equal to one. In the previous solution we divided the elements into two sections. Notice how we put the element 2 at the border of two sections, that is because that way we allow for no two elements that are next to each other to have a sum of 1. If we only have zeros and ones in the array, we have no other options but to put numbers like this

[0, 0, 0, 0, 0, 1, 1], thus making the solution equal to 2.Thanks a lot.

In problem D Can someone explain why p=[2,1] and a=[0,1] has score 1?

For D, I don't think the answer for case

3

0 1

is 2. for p = {1, 2} we have 2->1->3, and {2, 1} we have 3->2<-1. The total sum of vertex 1's incoming edges is 1.Yet in the case 2 the answer is

1 2 7 31 167 1002 7314 60612

for case

9

0 1 0 0 0 1 0 0

when k = 2 the answer is 2 instead of 1. Why is that?

never mind. api not ai

How to solve F1?

I had to generate all possible sequence to figure out the last sample of C.

My first contest as a specialist!

Definitely not dropping back to pupil!

SpoilerI will

you can try CF-Predictor on Chrome to get the estimated rating changing

The Carrot is better than CF-Predictor.

Read the note given by the developer of Carrot in the overview section of the extension.

Can anyone share some thought for problem E?

What I did in the contest was:

Set a constant B

Compute DP-ish the answer of all f(u, v) when the number of the vertices in that depth is <= B, compute additional answer when needed.

Do the same as in query.

I thought the complexity should be like O(n^(3/2)) when B ~ n^(1/2). Got a TLE though.

Was there a O(n log(n)) or O(n) answer? I was also thinking about some smart way to precompute stuff, but didn't come out with one.

There is a Mo's Algorithm on Trees solution, you can check this blog if you are not familiar with the algorithm.

Thank you for the reference, looking into it!

What the fuck is the brute force solution of E with just memorizing the queries getting pretests passed?

how? i have tried using both map and unordered_map but failed.

What's wrong with that?

It can be proved that the complexity of it is O(n*sqrt(n)).

Consider the set of vertices of the same depth. We call Si as the set of depth i. If the size of Si is below sqrt(n), then we can calculate the answer of each pair in it using the answer of Si-1. Otherwise, we ignore it. Because the size of Si is below sqrt(n), the size of the set of their parents is below sqrt(n), too. So, we can calculate the answer of each pair of their parents. You will find that you calculate the answer of min(sqrt(n),size)^2 pairs in one depth, so the complexity of it is O(n*sqrt(n)).

When we answer a question of (x,y), let i be the depth of them. If the size of Si is below sqrt(n), we can use the answer that we have calculated. Otherwise, we use brute force algorithm until we find the answer of (x,y) is calculated. You will find that the process will happen only if the size of Si is above sqrt(n). The number of those i is below sqrt(n), so we do this process at most sqrt(n) times in one query.

You will find that the brute force solution of E with just memorizing the queries is the same as my algorithm.

You are right, I thought it was Mo's.

Am i true that E is sqrt decomposition?

Approach for C :

if n is 1 then just abs(p[0] — p[1]) else if n is 2 then consider {2, 2, 2, 2} and {2, -1, -1, -1} else if n is even then consider {n, -1, -1, -1 ... (2n — 1) times}

I don't know the proof :(

Awful contest. The letter number of problems should be A-C-D-F-E-G1-G2. How did testers test this contest?

Solved A-C and E. Maybe I could solve D if I've consumed less time on some wrong approaches of E, but I don't have enough time for it.

A: The number of first operation (+1, +1) is d-b, and second operation (-1, 0) is a+d-b-c. The answer is their sum if both are non-negative.

B: Let c0=count of zeros in the array. Then if c0<=floor(n/2), we can arrange numbers such that every 2 occurences of zero are non-adjacent, then every pair of adjacent numbers will have positive sum, so MEX=0. Otherwise, we could put zeros on the left and other number on the right, if there's some number >=2, we put it on the boundary of zeros and positive numbers, so every non-zero sums will be >=2, so MEX=1. Otherwise, there are only 0 and 1 in the array, and because the count of zeros is strictly more than ones, we can arrange them like 01010...0100...00, then MEX=2.

C: By brute force for n<=4 we can conjecture that:

if n=1, good arrays are [a, a] where a can be any integer.

if n=2, good arrays are [0, 0, 0, 0], [2, 2, 2, 2], [-1, -1, -1, 2] (and its permutations).

if n>2 and n is odd, only [0, ..., 0] is good array.

if n>2 and n is even, good arrays are [0, ..., 0] and [-1, -1, ..., -1, n] (and its permutations).

E: Mo's algorithm on tree. For each depth d we need to record nodes with depth d on the current path, and if there are 2 nodes (u, v) with depth d, they contribute a[u]*a[v] to the answer. And we need to add dp[lca(x, y)] for each query additionally, where dp[i] is the sum of a[j]^2 over all nodes on the path from 1 to i.

For C:

If $$$n=2$$$, why $$$[-1,-2,-1,3]$$$ isn't good array?

If $$$n=3$$$, why $$$[0,x,-x,0,-x,x]$$$ isn't good array?

Have I misunderstood the meaning of

good?Condition should hold for

everysubsequence, and -2*3 != -1 + -1Thank you, I thought that subsequence means that elements need to be continuous.

loved your c approach bro

Ahhhhh!I'm not good at number theory! I just find n=1 and n=2 during contest, but don't understand n>2

I didn't even think of coding brute force(4 for loops) for generating the good array of n = 4, and was stuck in finding the best good array of sample test 3. Will use the brute force for future questions next time when intuition and observation fails. Thanks :D

problem c wasn't that hard Sighs....

Hi just wanted to give my perspective as a tester

i solved abcde however c got changed and i solved the new c too in 20mins.

for C : there is really cute algebra solution, no need of bruteforce; first take any random set S1 and its complement S2, write equation, swap one element from S1 with one element from S2

Rewrite the equation, and cancel variables, you will easily get the necessary stuff

D : this problem has a complicated statement but i didnt expect it to become this hard. Quite a few testers solved it and most upsolved it atleast.

E : this problem also has a neat sqrt solution, you can check my submission

problem C was harder than usually, even two last examples were unclear for me

wtf..

Can anyone explain the solution for Problem C..

was it at all a constructive or observation based Problem too?..

I solved it by solving some equations

Can someone please explain why am I getting MLE in A? Submission: 197908525

This works perfectly fine in 256MB, so why would it give MLE with a higher memory limit?

MikeMirzayanov, looks like bug

Or whom to ping for things like this?)

`score = -roundNumber`

problems are a bit more difficult than div2 before.

waiting for editorial

https://codeforces.cc/blog/entry/114048

thanks for contest!!!this contest's C is harder than normal div2 C.F1 and F2 is excellent problem.

I had submitted my answer for problem B and it got accepted but now it is showing in queue . please fix it.

As a participant, akash bhora tara........:)

হোগা মারা সাড়া

As a member of these students,no one tell me the problems were from them.

please rejudge https://codeforces.cc/contest/1806/submission/197938565, test 25 is pretest but i can't pass it in maintest.

It may be the fluctuation of the evaluation machine. Please test it several times. thank you!

Problem E has a very tight time limit, which I think is unreasonable

My brute force solution for E got passed. submission: 197969099 The approach is: for every query (x,y) with depth d, brute force the first sqrt(n) pairs. Then memorize the rest d-sqrt(n) pairs. Unfortunately, I don't know how to prove or disprove it.

`unordered_map`

is so slow that I got TLE in problem E.I mean I got TLE with map.

i'm so sad , i know it can be solved by hash ,and tried with unordered map i'v tried lots of times but TLE which waste my time and i know i may pass it if i write a hash instead of using STL at the last 3 minutes

Problem C is a very interesting constructive problem.

excuse me, for problem C what is the answer of this input? " 1 3 1 2 3 1 2 3 "

"12"

why? isn't it 0?

$1\times 1\times 2 \neq 2+2+3$，did you read the statement?

pa na pa. my bad, got it totally wrong thank you

C was stupid adhoc problem T_T

I tried to read D after contest and couldnt understand the statement. So i asked someone to explain it to me, only to then notice that they also didn't understand the statement, lol.

So how can the statement be improved while being understandable for someone who does not know of DSU while not being ambiguous?

I think it would help if the statement was worded in a way that gave a more intuitive idea of what is happening.

For example, you could first say that the leader of a vertex is the vertex in its weakly connected component with no outgoing edges, and then say that the match will go out between $$$leader(p_i)$$$ and $$$leader(p_{i+1})$$$.

This way you show that $$$u$$$ and $$$v$$$ are a function of $$$p_i$$$ (which is important because at that point they could be 2 numbers that are given on input) and there is an intuitive interpretation of "leader" that can make you understand the statement even if something is unclear to you

You could also drop the graph definition entirely and go 100% ludical, for example by saying that when leader $$$a$$$ wins a game against another leader $$$b$$$, $$$a$$$ becomes the leader of $$$b$$$ as well as all the people that $$$b$$$ was a leader of, and then define which games would happen based on the $$$a$$$ and $$$p$$$ sequences.

Another thing that would certainly help was if the animated gif explaining the problem had a bigger example, what is happening is still very ambiguous even when looking at it.

I actually wanted to to with this.

alternate statement draftBut testers did not like because they claimed the current statement does not look like a mess of random operations.

Regarding the part about intuitiveness, I thought the title was a big hint into what the process was doing as we tried to explain DSU process in the most concise way possible.

Well, a lot of problems with topics on the title tend to have nothing to do with that topic so I typically don't consider that.

Anyways I also don't like that draft as well. I think the core problem is that the operations do have a very pretty and intuitive interpretation but it is hard to decode from the statement (someone is the leader of a group and if they win the game they become the leader of the group they won against).

For example, this was what that person that explained the problem to me said:

SpoilerEven though there is little to no mathematical rigor (and technically being wrong, as they also missed that it was the sum for 1 and not the overall winner), it helped me looking at the definitions of the original statement and saying stuff like "ahhh, that's why we have a permutation here" and "it makes sense now that we care about the vertice with no outgoing edges".

Just to be clear, I don't think that example should be the statement of the problem verbatim. However I think adding flavor text to problems like this helps a lot. That's why a lot of statements say stuff like "We're doing X. Formally, we will have Y." Instead of just saying the mathematical definition head on.

If someone is interested, I have explained my $$$O\left(n \cdot q\right)$$$ solution for problem 1806E - Мастер деревьев in this comment under the editorial.

Problem E is exactly the same as this problem.

I think the solution of E is a little rigid.But we can still learn something good from the contest.

You are wrong.Here is why.

fastest rating and editorial update, I have ever seen....

You don't need to control the constant for problem E, you can set the threshold to around 100, and you can run fast.

Here