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 Mar/18/2023 15:05 (Moscow time). 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, mtw, 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 finallybeing 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?
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!
As a grey tester I can say that div3 div4 participants will like the round.
Glhf!
Gray tester
who 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
Yes you are! Never believe anything else.
Runtime-Terr0r orz
Vipin orz
Runtime-Terr0r orz!
-is-this-ars- orz
Runtime-Terr0r orz
milind0110 orz
Runtime-Terr0r ORZ !!
1riddhi orz
My first contest as an expert. Definitely not dropping back to specialist
I will
My first contest as a master. Definitely not dropping back to candidate master
I won't
Big flex
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.
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 :)
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
HOW DO YOUR E'S SOLUTION WORK? I GET 10* TLE ON 10 NOW! TERRIBLE!
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!
Problem 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++
good luck!
WOW the score distribution...
Good luck everybody!Hopefully i will become pupil again.
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 any array 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...]?
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 got this by brute forcing on 3rd test case but how do we prove that this is sufficient for the given question?
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:
I 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.
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.
did you come up with [-1,-1,-1,...,n] by any mathematical proof or just by hit and trial?
no just hit and trial
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:)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?
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
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.
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!
I will
you can try CF-Predictor on Chrome to get the estimated rating changing
The Carrot is better than CF-Predictor.
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 every subsequence, and -2*3 != -1 + -1
Thank you, I thought that subsequence means that elements need to be continuous.
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
В русском условии задачи D написано:
В английской же версии написано по-другому:
Кажется, что две этих надписи имеют разный смысл — в английской версии четко сказано про сток, в русской же рассматривается вершина, в которую входит ровно одно ребро.
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://mirror.codeforces.com/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........:)
হোগা মারা সাড়া
please rejudge https://mirror.codeforces.com/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
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.
But 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:
Even 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 - 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