### mazihang2022's blog

By mazihang2022, 8 days ago,

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:

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:

• +78

 » 8 days ago, # |   +88 as the mascot, give me contribution!
•  » » 6 days ago, # ^ |   -84 Negative contribution?
•  » » » 3 days ago, # ^ |   -30 .ComplaintFrame { display: inline-block; position: absolute; top: 0; right: -1.4em; } .ComplaintFrame a { text-decoration: none; color: #ff8c00; } ._ComplaintFrame_popup p, ._ComplaintFrame_popup button { margin-top: 1rem; } ._ComplaintFrame_popup button { padding: 0.25rem 2rem; } ._ComplaintFrame_popup ul { margin-top: 1em !important; margin-bottom: 1em !important; } so i give you downvote.
•  » » 3 days ago, # ^ |   0 Although -59,thank you for the contest!
 » 6 days ago, # |   +26 As a tester, I liked to test this round, and hope you will have fun participating :)
•  » » 4 days ago, # ^ |   +16 As a participant, I want to thank you for the contest!
•  » » 4 days ago, # ^ |   -27 Thanks very much, I hope this round will be fun
 » 6 days ago, # |   +42 As a grey tester I can say that div3 div4 participants will like the round.Glhf!
•  » » 6 days ago, # ^ |   -26 Gray tester Spoilerwho never was a specialist
 » 6 days ago, # |   +20 As a tester, I hope you enjoy the problems as much as I did.
•  » » 4 days ago, # ^ | ← Rev. 2 →   +6 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!
 » 6 days ago, # |   +25 As a tester, I enjoyed testing the round. Good luck to participants!
•  » » 6 days ago, # ^ |   +12
•  » » » 6 days ago, # ^ |   +11 False, WAtoAC2001 orz
•  » » » 6 days ago, # ^ |   +18
•  » » » » 6 days ago, # ^ | ← Rev. 2 →   +7
•  » » » » » 6 days ago, # ^ |   +13 SpoilerYes you are! Never believe anything else.
•  » » » » » » 6 days ago, # ^ |   +26
•  » » » » » » » 6 days ago, # ^ |   +10 vipin orz
•  » » » » » » » 4 days ago, # ^ |   +10 Runtime-Terr0r orz!
•  » » » » » » 6 days ago, # ^ |   +10
•  » » » » » » » 5 days ago, # ^ |   +15
•  » » » » » » » » 5 days ago, # ^ |   +18 milind0110 orz
•  » » » » » » » » » 3 days ago, # ^ |   0 orz
•  » » » » » » » » » 3 days ago, # ^ |   0 orz
•  » » 6 days ago, # ^ |   +31 Runtime-Terr0r ORZ !!
•  » » » 6 days ago, # ^ |   +9 1riddhi orz
 » 6 days ago, # |   +17 My first contest as an expert. Definitely not dropping back to specialist SpoilerI will
•  » » 6 days ago, # ^ |   0 orz. CM time
•  » » 6 days ago, # ^ |   +49 My first contest as a master. Definitely not dropping back to candidate master SpoilerI won't
•  » » » 6 days ago, # ^ |   +14 Big flex
•  » » » 4 days ago, # ^ | ← Rev. 2 →   0 My first competition to be held during the lessons. MY ANSWER!I will participate!
•  » » 3 days ago, # ^ |   0 lol
 » 5 days ago, # |   +25 Perfect time for Chinese people
•  » » 4 days ago, # ^ |   +17 Because this round is held by Chinese :)
•  » » » 4 days ago, # ^ |   0 meow.BUT I HAVE CLASS AT 8:00 meow.
 » 5 days ago, # |   +41 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.
•  » » 3 days ago, # ^ |   +8 which one?
•  » » » 3 days ago, # ^ |   +4
 » 5 days ago, # |   -16 As a user, this contest is one of the codeforces contests.
 » 4 days ago, # |   +36 As GPT-4, I will be participating in this Round :) Get Ready Humans.
•  » » 4 days ago, # ^ |   0 I'll focus on your performance.
•  » » 4 days ago, # ^ |   0 lemme know if you are able to solve div2c
•  » » 3 days ago, # ^ | ← Rev. 2 →   +3 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...
•  » » 3 days ago, # ^ | ← Rev. 2 →   +3 Got positive delta at least :)
 » 4 days ago, # | ← Rev. 2 →   0 What a great time!
 » 4 days ago, # |   +2 first time a round in which I know so many testers :hype:
 » 4 days ago, # |   0 What a good time!I love the writers very much!
 » 4 days ago, # |   0 Hope to get a positive delta!
 » 4 days ago, # |   0 I believe this contest is good
 » 4 days ago, # |   0 What should I write? ⚫⁔⚫ Can anyone help me? (◕.◕)
 » 4 days ago, # |   0 what can be reason to increase contest duration by 15 minutes than usual 2 hour duration ?
 » 4 days ago, # |   0 As a contestant, I anticipate this Chinese Round to be great one seeing the authors!
 » 4 days ago, # |   +16 Hope to become master again!..
 » 4 days ago, # |   +2 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 :)
 » 4 days ago, # |   +2 I wish I could do well in this div
 » 4 days ago, # |   +3 CN round, rating recycling round
•  » » 3 days ago, # ^ |   0 HOW DO YOUR E'S SOLUTION WORK? I GET 10* TLE ON 10 NOW! TERRIBLE!
 » 4 days ago, # |   0 OH,a bad time for me QWQ
 » 4 days ago, # |   0 Yet another bing chilling round!
 » 4 days ago, # | ← Rev. 2 →   -7 damn Dominater069 & milind0110 as testers But VIP tester must be Codula
 » 4 days ago, # |   0 As a newbie i hope to not be a newbie again...
 » 4 days ago, # |   0 As a human, I will be participating in this Round :) Get Ready chat-gpt.
 » 4 days ago, # | ← Rev. 2 →   +12 18o3 orz
 » 4 days ago, # |   +3 feecle6418 orz
 » 4 days ago, # |   +12 omg subtask for problem F round
 » 4 days ago, # |   +15 Another round with problem C of 1750 score
 » 3 days ago, # |   0 I didn't go to college and I missed classes to attend the contest
 » 3 days ago, # |   0 As a newbie, I hope you enjoy the problems as much as I did.
 » 3 days ago, # | ← Rev. 2 →   -7 :(
 » 3 days ago, # |   0 Chinese is to be considerate of Chinese and praise the game time.
 » 3 days ago, # |   0 Hope rating ++ in Chinese rounds! Good luck!
 » 3 days ago, # |   +46 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 treesI will be able to solve only ABC and will lose rating.Screen it! Will check after this contest.
•  » » 3 days ago, # ^ |   0 Similar to the real problems!
•  » » 3 days ago, # ^ |   +15 i feel that someone told you about the tags of the problems :)
 » 3 days ago, # |   +9 Hope rating++
•  » » 3 days ago, # ^ |   0 I didn't solve C.;(
 » 3 days ago, # |   +1 good luck!
 » 3 days ago, # |   +4 WOW the score distribution...
 » 3 days ago, # | ← Rev. 3 →   +3 Good luck everybody!Hopefully i will become pupil again.
 » 3 days ago, # |   0 How can I participate if I haven't yet registered for the contest?
 » 3 days ago, # |   +14 Masterforces!
•  » » 3 days ago, # ^ |   +5 This round is actually for Masters(Cries in C)
 » 3 days ago, # |   +3 I think I am going to have fun after solving A,B good luck in C am not interested :D
 » 3 days ago, # | ← Rev. 4 →   +1 speedforces is back !
 » 3 days ago, # |   +12 Now, this was completely opposite to today's Mathura ICPC prelims. :( Tooooo Tough.
 » 3 days ago, # |   +37 Hardest div2 C ever :)
 » 3 days ago, # |   +5 I saw names of all problems , ans i was like.....isn't it masters' round?!?!?! :)
 » 3 days ago, # |   +17 I can't solve Problem.B :(and I will 掉大分
 » 3 days ago, # |   +8 C hurts :(
 » 3 days ago, # |   +5 Dumbest C ever lol. So many cases
 » 3 days ago, # | ← Rev. 3 →   0 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.
•  » » 3 days ago, # ^ |   +3 if n is not odd then you can generate one number n, and all other -1
•  » » » 3 days ago, # ^ | ← Rev. 2 →   0 Is there any optimization for the odd case? Or is it just [0, 0, 0, 0...]?
•  » » » » 3 days ago, # ^ |   0 i think is 0000,but i got wa
•  » » » » 3 days ago, # ^ |   0 Then all q should be 0, however, only when n=1 then the answer is abs(p[0]-p[1])
•  » » » 3 days ago, # ^ |   0 what if n is odd then?
•  » » » » 3 days ago, # ^ |   0 then q should be all 0s
•  » » » » » 3 days ago, # ^ | ← Rev. 2 →   0 Damn, I got this right. Not sure why still WA.
•  » » » » » » 3 days ago, # ^ |   0 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.
•  » » » » » » » 3 days ago, # ^ |   0 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.
•  » » » 3 days ago, # ^ |   0 so if n is odd except n=1 ,all the a[i] is 0?
•  » » » » 3 days ago, # ^ | ← Rev. 2 →   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
•  » » » » » 3 days ago, # ^ |   0 i forget n%2=0,a[i]=00000
•  » » » » » » 3 days ago, # ^ |   0 same for me :(
•  » » » 3 days ago, # ^ |   0 how to prove this pattern is optimal?
•  » » » 3 days ago, # ^ |   0 I got this by brute forcing on 3rd test case but how do we prove that this is sufficient for the given question?
•  » » 3 days ago, # ^ |   0 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 :(
 » 3 days ago, # |   +17 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:)
•  » » 3 days ago, # ^ |   0 orz
•  » » 3 days ago, # ^ |   0 I think you are the luckiest person on the planet for a moment.Can you describe how you have done.
•  » » » 3 days ago, # ^ |   +8 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: Code#include using namespace std; #define int long long #define pii pair #define pb push_back #define rep(i,n) for(int i=0;i edge[500005]; vector q[500005]; vector all; bool vis[15]; void dfs(int x) { all.pb(x);vis[x]=1; for(auto v:q[x]) { if(!vis[v]) { dfs(v); } } } int find(int x) { memset(vis,0,sizeof(vis)); all.clear(); dfs(x); for(auto v:all) { if(edge[v].empty()) { return v; } } return -1; } signed main() { int t=read(); while(t--) { n=read(); rep1(i,n-1) { a[i]=read(); } rep1(i,n-1) { rep1(j,i) { p[j]=j; } int tot=0; do { rep1(j,i+1) { edge[j].clear(); } rep1(j,i) { rep1(k,i+1) { q[k].clear(); } rep1(k,i+1) { for(auto v:edge[k]) { q[k].pb(v); q[v].pb(k); } } int u=find(p[j]),v=find(p[j]+1); if(!a[p[j]]) { edge[v].pb(u); } else { edge[u].pb(v); } } rep1(j,i+1) { for(auto v:edge[j]) { if(v==1) { tot++; } } } } while(next_permutation(p+1,p+i+1)); printf("%lld ",tot); }puts(""); } return 0; } I found about the 0 cases and finally developed the right pattern. When I finished testing, i got pretest passed.
 » 3 days ago, # |   0 How C & E?
 » 3 days ago, # |   0 I like problem D, thanks.
 » 3 days ago, # |   +25 I think we should exchange D and E
 » 3 days ago, # |   +7 Hooooooow toooooooo sooooolllllllllvvvvvvveeeeeeeee EEEEEEEEEEEEE TwT too hard
 » 3 days ago, # |   0 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
•  » » 3 days ago, # ^ |   +1 [-1,-1,-1,2] works
•  » » » 3 days ago, # ^ |   +2 god damn it i literally thought of every thing except this.
•  » » 3 days ago, # ^ |   0 If n is divisible by 2, then the array of length 2n: [-1, -1, ..., -1, n] satisfies the condition.
•  » » 3 days ago, # ^ |   0 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.
 » 3 days ago, # |   0 How to solve C? I went through all possible patterns but still WA.
•  » » 3 days ago, # ^ | ← Rev. 2 →   0 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.
 » 3 days ago, # |   +3 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
 » 3 days ago, # |   0 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); } 
•  » » 3 days ago, # ^ |   0 the smallest non zero element as answerBut if you have numbers 0 3 0 0, then clearly answer is 1, not 3.
•  » » » 3 days ago, # ^ |   0 i even put one instead of min and still didn't pass just one doubt the answer is always 1 or 0 right
•  » » » » 3 days ago, # ^ |   0 for 0 1 0 0 answer is 2:)
•  » » » » » 3 days ago, # ^ |   0 i missed this ok thanks ....
 » 3 days ago, # |   0 Nice contest, I liked all tasks I tried (A, B, C, E)
 » 3 days ago, # |   0 Seems like Mo's algorithm was not enough for E (at least for me).
 » 3 days ago, # | ← Rev. 2 →   0 One of the toughest Div2 for me.Anyone, please help me in B?
•  » » 3 days ago, # ^ |   0 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.
•  » » 3 days ago, # ^ |   0 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 0else 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 1if 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 2if the greatest number is 0, you can obviously just pick 1
•  » » » 3 days ago, # ^ | ← Rev. 2 →   0 How do you get this approach?Can you please tell me more?And how it is correct always?
•  » » 3 days ago, # ^ |   0 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.
•  » » 3 days ago, # ^ | ← Rev. 3 →   0 The possible solutions for problem B can be either 0, 1 or 2.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.
•  » » » 3 days ago, # ^ |   0 Thanks a lot.
 » 3 days ago, # | ← Rev. 2 →   +5 In problem D Can someone explain why p=[2,1] and a=[0,1] has score 1?
 » 3 days ago, # |   0 For D, I don't think the answer for case30 1is 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 is1 2 7 31 167 1002 7314 60612for case90 1 0 0 0 1 0 0when k = 2 the answer is 2 instead of 1. Why is that?
•  » » 3 days ago, # ^ |   0 never mind. api not ai
 » 3 days ago, # |   +5 How to solve F1?
 » 3 days ago, # | ← Rev. 2 →   +3 I had to generate all possible sequence to figure out the last sample of C.
 » 3 days ago, # |   0 My first contest as a specialist!Definitely not dropping back to pupil! SpoilerI will
•  » » 3 days ago, # ^ |   0 you can try CF-Predictor on Chrome to get the estimated rating changing
•  » » » 3 days ago, # ^ |   0 The Carrot is better than CF-Predictor.
•  » » » » 3 days ago, # ^ |   0 Read the note given by the developer of Carrot in the overview section of the extension.
 » 3 days ago, # | ← Rev. 3 →   +8 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.
•  » » 3 days ago, # ^ |   +16 There is a Mo's Algorithm on Trees solution, you can check this blog if you are not familiar with the algorithm.
•  » » » 3 days ago, # ^ |   +5 Thank you for the reference, looking into it!
 » 3 days ago, # |   0 What the fuck is the brute force solution of E with just memorizing the queries getting pretests passed?
•  » » 3 days ago, # ^ |   0 how? i have tried using both map and unordered_map but failed.
•  » » 3 days ago, # ^ |   0 What's wrong with that?
•  » » 3 days ago, # ^ |   0 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.
•  » » » 3 days ago, # ^ |   0 You are right, I thought it was Mo's.
 » 3 days ago, # |   +7 Am i true that E is sqrt decomposition?
 » 3 days ago, # |   0 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 :(
 » 3 days ago, # |   0 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.
•  » » 3 days ago, # ^ |   0 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?
•  » » » 3 days ago, # ^ |   0 Condition should hold for every subsequence, and -2*3 != -1 + -1
•  » » » » 3 days ago, # ^ |   0 Thank you, I thought that subsequence means that elements need to be continuous.
•  » » 3 days ago, # ^ |   0 loved your c approach bro
•  » » 3 days ago, # ^ |   0 Ahhhhh!I'm not good at number theory! I just find n=1 and n=2 during contest, but don't understand n>2
•  » » 3 days ago, # ^ |   0 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
•  » » 3 days ago, # ^ | ← Rev. 2 →   0 problem c wasn't that hard Sighs....
•  » » 3 days ago, # ^ |   +3 Hi just wanted to give my perspective as a testeri 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 S2Rewrite 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
 » 3 days ago, # |   +13 problem C was harder than usually, even two last examples were unclear for me
 » 3 days ago, # |   0 wtf..Can anyone explain the solution for Problem C..was it at all a constructive or observation based Problem too?..
•  » » 3 days ago, # ^ |   +1 I solved it by solving some equations
 » 3 days ago, # |   +3 Can someone please explain why am I getting MLE in A? Submission: 197908525This works perfectly fine in 256MB, so why would it give MLE with a higher memory limit?
•  » » 3 days ago, # ^ |   0 MikeMirzayanov, looks like bugOr whom to ping for things like this?)
 » 3 days ago, # |   +27 score = -roundNumber
 » 3 days ago, # |   0 problems are a bit more difficult than div2 before.
 » 3 days ago, # |   0 waiting for editorial
•  » » 3 days ago, # ^ |   0
 » 3 days ago, # |   +2 thanks for contest!!!this contest's C is harder than normal div2 C.F1 and F2 is excellent problem.
 » 3 days ago, # |   0 I had submitted my answer for problem B and it got accepted but now it is showing in queue . please fix it.
 » 3 days ago, # |   0 As a participant, akash bhora tara........:)
•  » » 3 days ago, # ^ |   +7 হোগা মারা সাড়া
 » 3 days ago, # |   0 As a member of these students,no one tell me the problems were from them.
 » 3 days ago, # |   +6 please rejudge https://codeforces.com/contest/1806/submission/197938565, test 25 is pretest but i can't pass it in maintest.
•  » » 3 days ago, # ^ |   0 It may be the fluctuation of the evaluation machine. Please test it several times. thank you!
•  » » 3 days ago, # ^ |   0 Problem E has a very tight time limit, which I think is unreasonable
 » 3 days ago, # |   +2 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.
 » 3 days ago, # |   0 unordered_map is so slow that I got TLE in problem E.
•  » » 3 days ago, # ^ |   0 I mean I got TLE with map.
•  » » » 3 days ago, # ^ |   0 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
 » 3 days ago, # |   0 Problem C is a very interesting constructive problem.
 » 3 days ago, # |   +3 excuse me, for problem C what is the answer of this input? " 1 3 1 2 3 1 2 3 "
•  » » 3 days ago, # ^ |   0 "12"
•  » » » 3 days ago, # ^ |   0 why? isn't it 0?
•  » » » » 3 days ago, # ^ |   0 $1\times 1\times 2 \neq 2+2+3$，did you read the statement?
•  » » » » » 3 days ago, # ^ |   0 pa na pa. my bad, got it totally wrong thank you
 » 3 days ago, # |   -8 C was stupid adhoc problem T_T
 » 3 days ago, # | ← Rev. 3 →   +31 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.
•  » » 3 days ago, # ^ |   0 So how can the statement be improved while being understandable for someone who does not know of DSU while not being ambiguous?
•  » » » 2 days ago, # ^ |   +1 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 youYou 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.
•  » » » » 47 hours ago, # ^ |   0 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. I actually wanted to to with this. alternate statement draftYou a given an array A of length N whose elements are either 0 or 1. Define the value of a permutation P of length M by the following process: Create 2 arrays R and C of length M+1. Initially R[i]=i and C[i]=0. In the i-th operation, let (x,y)=(P[i]+1-A[i],P[i]+A[i]), then perform C[R[x]]:=C[R[x]]+1 and for all i such that R[i]=R[y], R[i]:=R[x]. Then the value is defined by C[1] by all N operations are performed. Find the value of all N! permutations P of length N. 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.
•  » » » » » 41 hour(s) ago, # ^ |   0 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: Spoilerimagine it as a contest and it's the winner of x bracket plays against the winner of x+1 bracketthe question is: how many wins did the overall winner won? sum for all permutations 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.
 » 3 days ago, # |   0 If someone is interested, I have explained my $O\left(n \cdot q\right)$ solution for problem 1806E - Мастер деревьев in this comment under the editorial.
 » 3 days ago, # |   +55 Problem E is exactly the same as this problem.
 » 3 days ago, # |   +10 I think the solution of E is a little rigid.But we can still learn something good from the contest.
 » 3 days ago, # |   +24 You are wrong.Here is why.
 » 3 days ago, # |   -10 fastest rating and editorial update, I have ever seen....
 » 3 days ago, # |   0 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