as the mascot, give me contribution!

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

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

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

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

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

Perfect time for Chinese people

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.

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

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

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

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

OH,a bad time for me QWQ

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

18o3 orz

feecle6418 orz

omg subtask for problem F round

Another round with problem C of 1750 score

Hope rating ++ in Chinese rounds! Good luck!

Hope rating++

good luck!

WOW the score distribution...

Good luck everybody!Hopefully i will become pupil again.

Masterforces!

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 any array that satisfies the condition, let alone a minimum distance one. All I could think of was an array of all 0's.

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:)

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

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

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

 if(cntzero == 0 )
        {
        	out.println(0);
        }
        else if(cntnon_zero == 0)
        {
            out.println(1);
        }
        else if( cntzero-cntnonzero > 1)
        {
            out.println(min(non_zero);
        }
        else if(cntzero-cntononzero <= 1)
        {
        	out.println(0);
        }        

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?

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?

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!

Can anyone share some thought for problem E?

What I did in the contest was:

1. Set a constant B

2. 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.

3. 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.

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

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.

В русском условии задачи D написано:

Заметим, что после каждого шага можно показать, что каждая компонента слабой связности G имеет единственную вершину с единственным входящим ребром.

В английской же версии написано по-другому:

Note that after each step, it can be proven that each weakly connected component of G has a unique vertex with only incoming edges.

Кажется, что две этих надписи имеют разный смысл — в английской версии четко сказано про сток, в русской же рассматривается вершина, в которую входит ровно одно ребро.

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?..

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?

score = -roundNumber

problems are a bit more difficult than div2 before.

waiting for editorial

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........:)

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

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.

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 "

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.

If someone is interested, I have explained my $$$O\left(n \cdot q\right)$$$ solution for problem 1806E - Tree Master 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.

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