### SerezhaE's blog

By SerezhaE, 3 years ago, translation,

Hello Codeforces!

We are glad to invite you to the Codeforces Round 586 (Div. 1 + Div. 2). Yes, it is rated!

The problems were invented and prepared by Alexponomarev7, adamant, lesswrong, wrg0ababd, VeryLonelyRaccoon, I_love_QMsh, msmlkm and me, SerezhaE. A lot of thanks to 300iq and cdkrot for help in contest preparation, and also we want to thank MikeMirzayanov for Codeforces and Polygon systems.

The contest starts on Wednesday, September 18 at 16:05 UTC and you will have 2 hours to solve the problemes. I believe everyone will find interesting problem for themselves :)

UPD. Editorial is published!

Good luck!

• +263

 » 3 years ago, # |   +10 is it rated?
•  » » 3 years ago, # ^ |   0 I think copy pasted part has been skipped.
•  » » 3 years ago, # ^ |   +114 I asked the question when post didn't mention it. Now it's updated.
 » 3 years ago, # |   +1 2 back to back contests! Reason we all like codeforces.
•  » » 3 years ago, # ^ |   +46 More like 4 except for a one-day gap.
•  » » » 3 years ago, # ^ |   -6 Right! :))
 » 3 years ago, # |   +45 This will be what, the 4th combined division round in a row for me? 5th if I count virtual Global Round 4.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +18 Did you account for up coming round "Dasha Code Championship"? :)I think combine round is different from separating them. People usually earn more and lose less rating. :)
•  » » » 3 years ago, # ^ |   +16 Only accounting for rounds I know I can participate in.You can't have everyone earning more rating if the sum of ratings is non-increasing (which it should be, extra rating comes from new users). It should be that high-rated contestants can lose more rating if they clearly underperform and low-rated can gain more thanks to that. There are more participants, which allows for more extreme situations.
•  » » » 3 years ago, # ^ |   +147 But one clearly advantages of Div.1 + Div.2 combined rounds is to prevent people from quitting the rounds. In Div.1 only rounds, some guy can read a problem, find it too difficult and quit the round without losing any ratings. While in combined rounds, he always solved some very-easy problems first and can't quit the round.
•  » » 3 years ago, # ^ |   +185 Combined rounds should be used only for events (usually with prizes). Normal rounds are much better. Problems fit participants more and hacking is more balanced.
 » 3 years ago, # |   -81 too late
 » 3 years ago, # |   -159 The time really fits Chinese! I love it!
•  » » 3 years ago, # ^ |   0 It's literally midnight (i.e. 12 AM) in China when this starts
 » 3 years ago, # |   0 I hope the statement will be short and nice like the announcement :D
 » 3 years ago, # |   -44 Why does a new problemsetter prepare a Div.1+2 contest?
 » 3 years ago, # | ← Rev. 2 →   -9 Good luck to all particopants and thanks for the contest!!!
 » 3 years ago, # |   +70 How many problems?
•  » » 3 years ago, # ^ |   -42 Maybe around 8, I guess.
 » 3 years ago, # |   -13 Fast tutorial plz.
 » 3 years ago, # |   0 It will be a fun contest! :)
•  » » 3 years ago, # ^ |   -65 There are known knowns, there are things we know we know. We also know there are known unknowns, that is to say we know there are some things we do not know. But there are also unknown unknowns, the ones we don't know we don't know.
•  » » » 3 years ago, # ^ |   +18 :|
 » 3 years ago, # |   +44 What about score distribution?
 » 3 years ago, # |   0 Hi everyone, today we are going to play HungerGames mode in Minecraft. Guys, would you like to join us????
•  » » 3 years ago, # ^ |   0 Hypixel is waiting for us
 » 3 years ago, # |   +22 1AM over here in Korea! Willing to give up tomorrows class for this contest :)
 » 3 years ago, # |   +24 I guess "problemes" is not the appropriate word!
 » 3 years ago, # |   +5 300iq <3 contest .
 » 3 years ago, # |   -27 this is my best contest ever !!!!!!!!!!! :)))))))) thank you so much SerezhaE
 » 3 years ago, # |   0 How to solve B ?
•  » » 3 years ago, # ^ | ← Rev. 3 →   +6 you have the results of: a1*a2,a1*a3,a2*a3a1*a2 = r1a1*a3 = r2a2*a3 = r3a1*2 = r1*r2/r3 --> a1 = sqrt(r1*r2/r3)Hope it works after test
•  » » » 3 years ago, # ^ |   0 Can we use gcd?
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   -15 I think GCD would give an approximation for each column, could you provide the context of using GCD?using GCD I think would have to do special work for 1EDIT: I mixed GCD and LCM :(
•  » » » » » 3 years ago, # ^ |   0 (For n=3 example)The first row is 0 a*b,a*c so if we get gcd(not including 0), we at least get a, but this is the problem here, if gcd(b,c) is not equal to 1, it becomes a problem. I could not figure it out for bigger value of n
•  » » » » » » 3 years ago, # ^ |   +1 Thinking in solving 3 unknown variables using 3 equations is much simpler, but for GCD you would need to do second iteration to validate values, I think you could do it that way
•  » » » » » » » 3 years ago, # ^ |   0 Thank you.
•  » » » » » » » » 3 years ago, # ^ |   +1 you are welcome
•  » » » » 3 years ago, # ^ |   0 I have used GCD of a column... but then also to avoid some corner cases I have checked all the divisors of the GCD value for which the matrix becomes valid... https://codeforces.com/contest/1220/submission/60795097 Here is the code.
•  » » » » » 3 years ago, # ^ |   0 Your codes are very well written i wish only if i could also write such codes.
•  » » » » » 3 years ago, # ^ |   0 Thanks
•  » » » 3 years ago, # ^ |   +1 Thank You. IslamOmar
•  » » » » 3 years ago, # ^ |   0 You are welcome
•  » » 3 years ago, # ^ |   +8 why im so stupid to use gcd ?
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 What do you mean? I couldn't understand. Do you think that using gcd is stupid? (Sorry for my bad English)
•  » » » 3 years ago, # ^ |   0 i used the most stupid form of gcd ( gcd all of the line thing ). then make up my mind and skipped B.
•  » » » » 3 years ago, # ^ |   0 I think you shouldn't think like that. This is not a stupid form. Maybe you could get to solution from that. And sorry for confusion, my English is bad :D
•  » » » » 3 years ago, # ^ | ← Rev. 4 →   0 You are not the only one. Same happened with me. I had almost given hope on it.Happens when our way of thinking solutions is Depth First instead of Breadth First, it's our way of thinking.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +3 Well. You're not... because I've also used GCD and actually solved B using it... The only extra part was, I checked all the divisors of the GCD value for which the matrix can be valid... https://codeforces.com/contest/1220/submission/60795097 So the idea was not wrong, just needed a little modification... This is the fun of problem solving, there are so many ways to solve it. So never underestimate that. ^_^
•  » » » » 3 years ago, # ^ |   0 my hero
•  » » » » 3 years ago, # ^ |   0 I used cgd too but I got WA on test 21. Can you look at my code please? 60891456 It is a short input but I got WA and couldn't figure out why.
 » 3 years ago, # |   0 How to solve D?
•  » » 3 years ago, # ^ |   +1 I'm not sure but... If we have A and B, where A is odd and B is even we can create a cycle with odd length. So we will use recursion There are two possible ways: delete all even numbers in an array and leave recursion or delete all odd numbers, divide all numbers left by 2 and do recursion again. We continue recursion and divide by 2 because there can be something like this: 2, 4. We can create cycle 0 — 2 — 4 — 0. So we can solve this problem with O(n log n)
•  » » 3 years ago, # ^ |   +1 you have to realize that:A and B can be in S if and only if the maximum power of 2 that divides A is equal to maximum power of 2 that divides B.
 » 3 years ago, # |   0 why problem D example 1 i can't simply delete vertex 1 and 3, the problem only states that we can connect 2 vertex if it absolute value after subtract each other belong to set B, so if it in the example we should have a triangle and it doesn't matter which vertex we choose cause it gonna turn into a bipartite graph anyway
•  » » 3 years ago, # ^ |   0 It asks you to delete the minimum number of vertex, so you could delete either 1, or 2.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +6 You can't delete vertex 1 and keep 3.Draw the graph for vertices 2, 3, 4, 5, 6 and B = {2, 3} and you will see it's not 2-colorable.
•  » » 3 years ago, # ^ |   +4 It's not a traingle. 3 elements in set B doesn't mean there are 3 vertices. There are infinte vertices actually
•  » » » 3 years ago, # ^ |   +3 prabalsingh24 are there infinite vertices marked from $-\infty$ to $+\infty$. I am misunderstanding the statement.
 » 3 years ago, # | ← Rev. 2 →   +5 how to solve D. I only know O(n^2)
•  » » 3 years ago, # ^ |   +3 Can you please tell O(n^2) approach?
•  » » 3 years ago, # ^ |   +6 One fact is you can only pick two numbers that are divisible by same power of two (for example you cant pick 6 and 40 but you can pick 10 and 22).
•  » » » 3 years ago, # ^ |   -9 Start from a arbitrary number and find the next time that two integers from B can both reach to another number. that number is LCM of those two number and simply you can see if they are not divisible by same power of two then you can find an odd loop.
•  » » » » 3 years ago, # ^ | ← Rev. 4 →   +27 If they are not divisible by same power of two then you can find an odd loop.We want lcm(a,b)/a + lcm(a,b)/b to be an even number, so either both terms should be odd, or both should be even. let a = 2^x * ..... and b = 2^y * ....If x > y then (lcm(a,b)/a) = 2^(x-x) * ... and (lcm(a,b)/b) = 2^(x-y)*.. so, the first number is odd, while second number is even.If x < y then (lcm(a,b)/a) = 2^(y-x) * ... and (lcm(a,b)/b) = 2^(y-y)*.. so, the first number is even, while second number is odd.If x = y then both are odd number.
•  » » » 3 years ago, # ^ |   0 Hi , is this an observation or is there some mathematical proof behind this? Why cant 4*a and 2*b (where a and b are odd numbers) be in the set? sorry if its a noob question , but i am not able to find a proof for this.
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   0 Consider this example :0 2b 4b 6b ... 4ab (Theses 2a numbers make a path because of having 2b in the set)0 4a 8a 12a ... 4ab (Theses b numbers make a path because of having 4a in the set)So you can see it makes a loop with size of 2a+b and that's an odd number so graph is not bipartite. The loop is like this : 0 2b 4b ... 4ab 4a(b-1) 4a(b-2) ... 4a 0 .
 » 3 years ago, # |   +11 how to solve problem D?
•  » » 3 years ago, # ^ |   +8 in the set there can only be numbers of the form 2 ^ s * i , where i — any odd number, and we can iterate s
•  » » » 3 years ago, # ^ |   +4 Can you explain why
•  » » » » 3 years ago, # ^ |   0 I explained it here .
 » 3 years ago, # |   +25 Wow, second round in a row I'm f**king with epsilons in geometry for no good reason. Just wow.
•  » » 3 years ago, # ^ |   +55 AAAAAAAAARGHMaybe it's finally time to write a geometry library using bigints only. Or something. -.-(At least it's gonna be useful on GCJ geometries.)
•  » » 3 years ago, # ^ |   +13 I tried something like: consider several small primes, get possible values of X and Y modulo them, combine it using CRT. I didn't have enough time to think it through but maybe it is the intended solution.
•  » » » 3 years ago, # ^ |   +22 Can it solve the problem for n=2? If so, it seems reasonable to be (part of) the intended solution.
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   0 Just doing all calculations mod $MOD=10^9+7$ suffices. Suppose that we want to find the intersection of two circles in the form $(x-a_i)^2+(y-b_i)^2=c_i\pmod{MOD}$ where $i=1,2.$ First subtract the two equations to find the radical axis. Then substitute for $x$ in terms of $y$ (unless $a_1=a_2$) and solve the resulting quadratic with modular square root. (Code: 60845080)
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   +10 Better way (No quadratics) to find intersection of circles: Wolfram link From Wolfram link you can find how to calculate intersection $(x;\pm y)$ if centers are $(0,0)$ and $(d,0)$. If centers are $A$ and $B$, treat them as complex numbers, then intersection points are $A+(B-A)*(x/d\pm i*y/d)$. I have doubt about my solution, because I only checked 20 distances to other points (if it is subset of given multiset it passes). How it doesn't get WA? (Code: 60952855)
•  » » 3 years ago, # ^ |   0 Checking if distance from center of mass is exactly as needed makes solution faster. After this check you can try about 100 points around the intersection and not get TLE.
•  » » 3 years ago, # ^ |   0 Having finally solved this, I want to strangle the next person who mentions geometry to me in person. I tried so hard to make calculating cos() from cosine theorem precise enough, but in the end, I gave up and did all subtraction in bigints.
 » 3 years ago, # |   -9 thanks for weak pretests for B! 4 hacks, yay!
•  » » 3 years ago, # ^ |   +15 I'm scared for system tests now.
 » 3 years ago, # |   0 Can someone tell me what is the 12th test in problem D ? :(
•  » » 3 years ago, # ^ |   +8 No.
 » 3 years ago, # | ← Rev. 2 →   +76 In problem D. when you finally notice $i,j\in N$. not $\in B$... :(
•  » » 3 years ago, # ^ |   +2 What? Really? Noticed it right now :)00)
•  » » 3 years ago, # ^ |   0 I think the statement was very poor in problem D :/
•  » » » 3 years ago, # ^ |   +3 I agree. And I talk the statement to people knowing nothing on math and programming, they think that's for integers in B. By the way, I have checked manually the first example during the contest, the result is OK for this understanding as well...
•  » » » » 3 years ago, # ^ |   0 I would say its nothing about knowing math or programming, its about the confusion that the problem statement has. Notice that even a lot of candidate masters were confused.But you are absolutely right, the statement supports the both way of thinking.
•  » » 3 years ago, # ^ | ← Rev. 3 →   +9 [Deleted]
•  » » 3 years ago, # ^ |   +9 I spent 1 hour thinking a different problem :c I didn't notice that until now xD
•  » » 3 years ago, # ^ |   0 Ow maan, but, $i, j \in \mathbb{Z}$...
 » 3 years ago, # |   +5 Awesome problems, really like them.Nice job!
 » 3 years ago, # |   +6 How to solve E? My idea was to continuously remove vertices with only one remaining neighbor (except the source), compress the rest of the graph into one component, then restoring the removed vertices find the path with largest sum starting from the component/vertex where S is. What is wrong with this or did I just do something stupid?
•  » » 3 years ago, # ^ |   +6 any node in a cycle or in the path from $s$ to the cycle, can be always taken by $s$->cycle back-> $s$. all the nodes can be treated as $s$. so remaining graph is a tree. find longest path to some leaf.
•  » » » 3 years ago, # ^ |   0 Yes, that's what I do. Probably I have some stupid implementation bug ...
•  » » » » 3 years ago, # ^ |   +24 What do you do in this case?The optimal path is (s) -> (compressed graph) -> (node on the left). Are you sure you don't for example count the weights between (s) and (compressed graph) twice?
•  » » » » » 3 years ago, # ^ |   +5 No, I (at least in theory) compress S, the middle node, and the compressed part together. So the final graph looks likeA — B — (S+middle+compressed)
 » 3 years ago, # | ← Rev. 2 →   -19 What a huge gap between C and D !!
 » 3 years ago, # |   0 How to solve F ?
•  » » 3 years ago, # ^ | ← Rev. 5 →   0 Notice that element $a$ is an ancestor of an element $b$ when it's minimum on a subsegment from $a$ to $b$. Count amount of ancestors for every element in initial permutation. Now, when you remove element $l$ from the left, all elements between it and the leftmost element smaller than $l$ now have one ancestor less. When you move it to the right, all elements between it and the rightmost element smaller than it have one ancestor more. You can store amounts of ancestors in a segment tree with lazy propagation. Solved.
 » 3 years ago, # |   0 How to solve C??? Use suffix array???
•  » » 3 years ago, # ^ | ← Rev. 2 →   +20 Just consider the smallest char already seen. The game will not last longer than 1 move :)
•  » » » 3 years ago, # ^ |   0 Hi, I understand that there will be only one move in the game. Can anyone clarify why we are comparing only the first character with the substring?
•  » » 3 years ago, # ^ |   +9 Only thing that matters is the first character on the left that is smaller than s[k]
•  » » 3 years ago, # ^ |   +9 The game either has 0 moves or 1. If a smaller alphabet occurs before the start pos, ans is Ann, else Mike.Not sure though.
•  » » 3 years ago, # ^ |   -11 Thanks everybody. It was seriously difficult problem...
•  » » » 3 years ago, # ^ |   0 Instead of choosing smallest alphabet, what about choosing smallest suffix before current index? Doesn't it work similarly?
•  » » » » 3 years ago, # ^ |   +16 It does, but it's harder than intended solution
•  » » » » » 3 years ago, # ^ |   +5 I think it doesn't as I first used suffix array and failed on test "abas" for k = 3.
•  » » » » » 3 years ago, # ^ |   +4 Well actually it didn't...
•  » » 3 years ago, # ^ |   +8 I first used suffix array but failed on test as "abas" as for k = 3 the answer is Mike not Ann but using suffix array would print Ann as suffix "as" is bigger than "abas" but after that I realized the simple solution considering the minimum char already seen!
•  » » » 3 years ago, # ^ |   +1 That's absolutely right!!! Now I understood why my approach got WA. Thanks a lot!!!
 » 3 years ago, # |   +91 Couldn't you give some actual samples in F? Especially in order to distinguish rotating to left and right xd.
•  » » 3 years ago, # ^ |   0 ^ This.
 » 3 years ago, # |   +15 I think I've seen F in a atcoder round, not sure. I do remember the trick of storing $X_{i} + Y_{i}$ in a segment tree, where $i$ is the longest decreasing sequence starting from $i$ to the left, and $Y_{i}$ is the longest decreasing sequence starting from $i$ to the right. Then the depth of the cartesian tree is the maximum of $X_{i} + Y_{i} - 1$ in the interval, and $X, Y$ are easy to update.
•  » » 3 years ago, # ^ |   0 Seems completely doable without that to me. Duplicate the permutation, then for each index, calculate the depth the tree rooted here would have if it covers everything between the closest smaller elements to its left and right (excluding these). Finally, for each index, calculate the depth of the tree we'd get if we took everything from the closest 0 to the left up to this element, using these precomputed simpler depths; same for closest 0 to the right.I almost managed to code it in those 20 minutes I had left after getting E passed... damnit.
•  » » 3 years ago, # ^ |   +46 Another solution — if we add an element to the right, the depth can only increase and if we delete one from the left, depth can only decrease. So we can binary search to find the points where the depths of the left and right subtrees are closest.
•  » » 3 years ago, # ^ |   +19 The answer is non-decreasing with respect to expanding the interval. So, you can binary search on the answer, and for a fixed $k$ find the maximum interval to the right of $1$ that has depth $k-1$. Now simply check whether the rest (to the left of $1$) can also be done with depth $k-1$. Complexity is $\mathcal O(n \log^2 n)$, but quite fast in practice.
•  » » 3 years ago, # ^ |   +13 We can actually simulate the entire process as well and get depths of all cyclic shifts.Moving from one cyclic shift to the next will require simple range updates.
 » 3 years ago, # |   +7 Made one wrong assumption for D, got stuck the whole contest: I assumed that the set of elements taken finally for forming bipartite graph,say has minimum element k, so all other numbers of set must be odd multiples of k. Anybody made the same mistake ? :(
•  » » 3 years ago, # ^ |   0 yes
 » 3 years ago, # |   +50
•  » » 3 years ago, # ^ |   +29 And which version is better? I know people preferring either.
•  » » » 3 years ago, # ^ |   +45 I prefer second version but without weird version of $\leq$.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +13 I don't care too much about scientific notation vs lots of 0s, but I think the horizontal line ≤ and ≥ look much nicer.
 » 3 years ago, # | ← Rev. 2 →   0 Is WA in case 49 (problem B) an overflow? (using Int instead of Long Long Int)
•  » » 3 years ago, # ^ |   0 Yes probably. You need 64-bit integers to solve the problem.
•  » » 3 years ago, # ^ |   0 I took me 15 minutes to find out from my first submission :v
 » 3 years ago, # |   +10 What is test 46 in E?
•  » » 3 years ago, # ^ |   +8 It is generated test with a tree and many loops of size 3 added to it.
•  » » 3 years ago, # ^ |   +10 It contains some cycle with zero weight.
 » 3 years ago, # | ← Rev. 2 →   -7 In problem E statement, this sentence make me confuse:"Alex believes that his trip will be interesting only if he will not use any road twice in a row."and the phrase "in a row" can be viewed as "continuosly". So I totally misunderstanding this problem (I think a edge can be use twice)
 » 3 years ago, # |   +5 for alex and julian question d, for given input 5 10 20 ,erasing 10 is sufficient but why answer is 10 and 20
•  » » 3 years ago, # ^ | ← Rev. 2 →   +8 It's not sufficient to erase 10. 5 & 20 create odd cycle which is not bipartite: 0 -- 5 -- 10 -- 15 -- 20 | | \--------------------/ 
 » 3 years ago, # |   +3 My solution for B: 60809853. I get the gcd of all elements in first row, this results in $a_1 * constant$. For every divisor of this value, I try to see if this is "valid".The validation assumes that the divisor is $a_1$, I can get $a_2$, ... $a_n$ from the first row. then using these values, I check if $a_i * a_{i+1}$ matches the given table. Could somebody tell me why this is sufficient?
•  » » 3 years ago, # ^ |   0 Maybe because of when the n gets bigger, gcd is getting closer to the a.
 » 3 years ago, # | ← Rev. 2 →   0 Can anyone explain how do we decide a substring is lexicographically less or not in problem C? Please help.
•  » » 3 years ago, # ^ |   +3
•  » » » 3 years ago, # ^ |   +8 Thank you very much
•  » » » » 3 years ago, # ^ |   +8 Can you clarify why we are comparing only the first character with the substring?
•  » » » » » 3 years ago, # ^ |   +1 Since the first substring to use is $s[k,k]$ it's just a letter, and it can only be beaten by a string that differs in the first letter. Thus, if no $s[i,i]$ can beat $s[k,k]$ in the possible range ($[1,k-1]$ or empty set if $k = 1$), then there is no possible move (Mike wins). Otherwise, our best choice is to move to the minimal $s[i,i]$ since the other player won't be able to make a move from there (because it's the minimal) (Ann wins).
 » 3 years ago, # |   +4 How to solve D?
 » 3 years ago, # |   +55 nice contest! There is one problem with no solves while all the other problems were solved by the top contestants in under 40 minutes.
 » 3 years ago, # |   -14 I have got an message from codeforces telling that one of my answer is matching with some other user. But I have not copied or not given my code to any other user. As far as I can understand maybe the other user has copied my code from ideone.com, i have valid proof of that. If someone can help please let me know and what would be the consequences that i have to face if it's not resolved.
•  » » 3 years ago, # ^ |   +8 I don't understand, did you publish your solution? But why
•  » » » 3 years ago, # ^ |   0 i tried to test my code on ideone.com
 » 3 years ago, # | ← Rev. 3 →   0 Some contestants hacked in problem B after contest and before rate change by dorijanlendvaj and the scoreboard does not change for them .Could anyone explain me why ?
•  » » 3 years ago, # ^ |   0 https://codeforces.com/blog/entry/68204Hacks made after the contest has ended don't affect the verdict(probably so that the scoreboard stays the same as at the end of system testing)
•  » » » 3 years ago, # ^ |   0 So, B has bad test cases and now I can ask you to check my code for B
 » 3 years ago, # |   0 Got WA on D in test 54 because I didn't know (1<
•  » » 3 years ago, # ^ |   +14 1ll<
•  » » 3 years ago, # ^ | ← Rev. 2 →   +3 (1ll<
 » 3 years ago, # |   +14 When will be the editorial?
 » 3 years ago, # | ← Rev. 3 →   +7 I think problem D is one of the coolest C/D problems of CF rounds. So, I just want to put a detailed solution here :P, if anybody is interested...Take two numbers $x$ and $y$. When two numbers cannot be in a bipartite sequence (the complement of required output)? If they both are in the bipartite sequence, we can find a cycle of length $\frac{x}{\gcd(x,y)}$ + $\frac{y}{\gcd(x,y)}$, which must not be odd. Also, both of the terms cannot be even (otherwise gcd could be doubled). Only fuss is when one of them is odd and other one is even. This essentially means that their least significant bits are different. Now, we already have a necessary condition — group numbers by their least significant bits, if two numbers are in the bipartite sequence, then they have to be in the same group. Wait, but can this be sufficient, meaning, can we take a whole group (the maximum sized one)? Trying not to be saviour of the human race, seeing that this is a Div2D, I quickly infer(?) that this has to be sufficient! Voila, AC! After the contest I proved it as follows: Let the chosen bipartite sequence be $S$ and $k$ be the lsb of all numbers i.e. $\forall x \in S, 2^k \mid\mid x$. Suppose, there is an odd cycle $c_1, c_2, c_3, \ldots, c_m$. Take a look at the values of $c_i \mod 2^{k+1}$. This value must be alternating between $0$ and $2^k$. So, if there is an odd cycle, it has an odd number of nodes, thus that cycle cannot afford this alternating property. Contradiction.
•  » » 3 years ago, # ^ | ← Rev. 4 →   +16 It can be proven more easily.If two numbers in the set are $(2a+1), (2b)$, then $2*(2a+1)*b$ makes contradiction. That means that all numbers are either odd or even. If odd -> we have a bipartite set of odd/even numbers. If even -> divide all numbers by 2.
•  » » » 3 years ago, # ^ |   +16 As for me, memento's proof is more interesting as it has some reasoning on how such an answer was obtained. In author's solution we as well started from $x/gxd(x, y) + y/gcd(x, y)$ to see that any pair of numbers with different lsb give contradiction and then we saw that if lsb is same, we can divide all numbers with it.Yours is, indeed, simple, but once again I'm confused with the fact that someone who tried to explain something and didn't make any mistakes while doing so gets downvoted.
•  » » » » 3 years ago, # ^ |   +5 But the short proof also has reasoning. You start by looking for an obvious case where we get an odd-length cycle (odd+even), which gives two cases you need to analyse and notice that one is "ok" and the other can be solved recursively. I'm confused with the fact that someone who tried to explain something and didn't make any mistakes while doing so gets downvoted. CF.
 » 3 years ago, # |   -51 mathforces
 » 3 years ago, # |   +13 G has a lot in common with P5 from Romanian Master of Mathematics 2011: https://artofproblemsolving.com/community/c6h393848p2188641Namely, following the same reasoning as in that mentioned problem (which is basically using a Steiner theorem or as some would prefer to put it — simple tricks on formulas) we get a conclusion that all candidates lie on a circle whose center is center of mass of antennas with some known radius.
•  » » 3 years ago, # ^ |   0 They're pretty similar indeed. Well, I'm not any kind of maths Olympiad guy, so I totally missed it. And yes, simple tricks on formulas is the way I prefer to call the intended solution :DBtw, are you talking about parallel axis theorem?..
•  » » » 3 years ago, # ^ |   0 Yes, I am talking about exactly this theorem. When we shave off all that physics blabbering about some moments of inertia what we get is that $\sum d(P_i, Q)^2 = \sum d(P_i, C)^2 + n \cdot d(Q, C)^2$where $P_i$ are some points on the plane and there are $n$ of them, $C$ is their center of mass and $Q$ is some arbitrary point what immediately gives us $d(Q, C)$, what means that all hypothetical candidates for point $Q$ are on some fixed circle.
•  » » » » 3 years ago, # ^ | ← Rev. 3 →   0 Hey, moments of inertia are cool actually! Why would we shave them off? >:(I knew the theorem from the Physics, by the way, but couldn't relate it with the problem this time. Kind of shame for me, since it seems to be third programming challenge I give somewhere based on something near inertia moments :D
•  » » » » 3 years ago, # ^ |   0 Well, yeah. Moments of inertia are just symmetric bilinear forms after all, getting to a circle from that isn't tough. Even in experimental physics, if you want to know moments of inertia for any axis, you just need to measure 3 principal ones (corresponding to eigenvalues+eigenvectors) and use the fact that all moments of inertia lie on an ellipsoid.
 » 3 years ago, # | ← Rev. 2 →   0 .
 » 3 years ago, # |   +20 Is the editorial published??
•  » » 3 years ago, # ^ |   -19 Yes
•  » » » 3 years ago, # ^ |   0 Sorry, but where can i find it? Could you share the link, please?
 » 3 years ago, # |   +12 Now I realized that I misinterpreted D. I read "let all integer numbers be vertices" as "let all integers in the set $\bf B$ be vertices," and struggling with completely different problem...
•  » » 3 years ago, # ^ |   +5 Really? I understand the same as you. Waiting the editorial for the analysis ...
 » 3 years ago, # |   +37 Will the editorial be published?
 » 3 years ago, # |   +10 I hacked my solution E after the contest. submission:60808754(https://codeforces.com/contest/1220/submission/60808754)
•  » » 3 years ago, # ^ |   +3 I hope everyone is able to picture the meme that should be posted as a reaction and we can move on. You can save your upvotes for the poor.
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 Can you please tell which case was missing?? k24
•  » » » 2 years ago, # ^ |   0 Got it!
 » 3 years ago, # |   +15 Please make an editorial. Or at least answer whether there will be an editorial.
•  » » 3 years ago, # ^ |   +10 Editorial is out now. Thank you!
 » 3 years ago, # |   0 how to solve problem C?
•  » » 3 years ago, # ^ |   0 the thing is when is you start with L=R=i you can never make R=R+K,K>0 as it will always increase the sequence lexicographically, also you only move to any L=L-K,s.t., a[L-K]
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 thank u navneet.h for explanation
 » 3 years ago, # |   0 Hello everyone, I was wondering how accepted solution of problem D is solved. I was going through teh solution and noticed that i cannot come out with the same output as those accepted solutions. I think test cases are too weak for this problem. 2 1 4 My answer is 0 as both are disconnected and hence bipartite. But accepted code's output is : 1 4... Can any please explain where am i getting it wrong? SerezhaE
•  » » 3 years ago, # ^ |   +1 Perhaps you are making the same mistake as me. Maybe you are thinking about a graph consisting from two vertices (1 and 4) and no edges, right? Actually, it's wrong. You have to think a graph with infinite vertices, among whom every pair of vertices whose difference is 1 or 4. Therefore, there exists a cycle of odd length, $0 - 1 - 2 - 3 - 4 - 0$, which means that this graph is not bipartite. I think the problem statement was ambiguous for some participants, and it was virtually impossible for those who misread to realize it, because sample cases on the problem statement was too small and has no explanation.