### Imakf's blog

By Imakf, history, 2 months ago,

Hello Codeforces!

On Nov/26/2022 17:05 (Moscow time) we will host Codeforces Global Round 24. Note the unusual time of the round.

It is the sixth round of a 2022 series of Codeforces Global Rounds. The rounds are open and rated for everybody.

The prizes for this round:

• 30 best participants get a t-shirt.
• 20 t-shirts are randomly distributed among those with ranks between 31 and 500, inclusive.

The prizes for the 6-round series in 2022:

• In each round top-100 participants get points according to the table.
• The final result for each participant is equal to the sum of points he gets in the four rounds he placed the highest.
• The best 20 participants over all series get sweatshirts and place certificates.

Thanks to XTX, which in 2022 supported the global rounds initiative!

The problems were written and prepared by Cocoly1990, waaitg and Imakf. 👀👀👀

We would also like to thank:

Round Information:

• Duration: 2 hours and 30 minutes 🔥🔥🔥
• Number of problems: 8 problems, one split into 3 subtasks 🤯🤯🤯
• Score distribution: $500$ — $1000$ — $1500$ — $1750$ — $2250$ — $2250$ — $(2000+500+500)$ — $3500$ 🤤🤤🤤
• There is an interactive problem, so please see the guide of interactive problems if you are not familiar with it. 🤭🤭🤭

As always, hope you all gain non-negative ratings $\Delta$ in this round! 🍾🍾🍾

UPD1: Editorial

Announcement of Codeforces Global Round 24

• +513

 » 2 months ago, # |   +18 Auto comment: topic has been updated by Imakf (previous revision, new revision, compare).
 » 2 months ago, # |   +10 As a participant, I hope the problems are interesting!
•  » » 2 months ago, # ^ | ← Rev. 2 →   +4 These were indeed interesting problems, the difficulty gap b/w D and E was a bit high tho
•  » » » 2 months ago, # ^ |   0 Yes, agreed!
•  » » 2 months ago, # ^ |   0 As a participant, I hope the problems are interesting!
•  » » 2 months ago, # ^ |   0 omg 3 subtasks round
 » 2 months ago, # | ← Rev. 2 →   +69 As a tester, Imakf 🤤🤤🤤
 » 2 months ago, # |   +41 omg 3 subtasks round
•  » » 2 months ago, # ^ |   +17 omg 3 subtasks round
•  » » » 2 months ago, # ^ |   +9 omg 3 subtasks round
•  » » » » 2 months ago, # ^ |   +9 omg 3 subtasks round
•  » » » » » 2 months ago, # ^ |   +9 omg 3 subtasks round
•  » » » » » » 2 months ago, # ^ |   +11 omg 3 subtasks round
•  » » » » » » » 2 months ago, # ^ |   +9 omg 3 subtasks round
•  » » » » » » » » 2 months ago, # ^ |   +9 omg 3 subtasks round
•  » » » » » » » » » 2 months ago, # ^ |   +10 omg 3 subtasks round
•  » » » » » » » » » 2 months ago, # ^ |   +11 omg 3 subtasks round
•  » » » » » » » » » 2 months ago, # ^ |   -63 Haha I break the order
•  » » » » » » » » » 2 months ago, # ^ |   +8 omg 3 subtasks round
•  » » » » » » » » » 2 months ago, # ^ |   0 omg 3 subtasks round
•  » » » » 2 months ago, # ^ |   +8 omg 3 subtasks round
 » 2 months ago, # |   +90 As a tester, I can say that the problems are all very interesting. Thank you for your participation.❤️❤️❤️
 » 2 months ago, # | ← Rev. 2 →   +44 As a tester, I must say that the problems are all very nice.
 » 2 months ago, # |   +4 Genius lgm problemsetter imakf, I'm a big fan of yours! orz imakf, orz waaitg, orz Cocoly1990!
 » 2 months ago, # | ← Rev. 2 →   +78 So basically everyone who solves $G2$ and $G3$ gets $150$ more points each.
 » 2 months ago, # |   +11 As we all know, a problem can be split into subtasks only when it's difficult to solve completely.
•  » » 2 months ago, # ^ |   0 I should have read this comment before the round xD
 » 2 months ago, # |   +3 No matter how the round turns out, had to upvote for the emojis 😌
 » 2 months ago, # |   +61 As a tester, I have to say that all the problems are very interesting!orz Cocoly1990, Imakf and waaitg!
•  » » 2 months ago, # ^ |   +6 Wait are you the guy who (up)hacked 120 submissions in my round?
•  » » » 2 months ago, # ^ |   +4 Yes, I uphacked some submissions using slow-output functions or languages in your round.
 » 2 months ago, # |   0 Note unusual timing
 » 2 months ago, # |   +203 As a writer,i want contribution.
•  » » 3 weeks ago, # ^ |   -6 stO Cocoly1990 Orz
•  » » » 3 weeks ago, # ^ |   0 downvoted/ng.
 » 2 months ago, # |   +5 omg emoji round
 » 2 months ago, # | ← Rev. 3 →   +8 As a tester I can say that you will really enjoy the problemset. I would suggest you to read all the problems. Problemsetters and errorgorn have tried their best to make statements easier to understand.
 » 2 months ago, # |   +45 As a tester, Orz Cocoly1990.
•  » » 2 months ago, # ^ |   +1 As a participant, Orz Cocoly1990.
 » 2 months ago, # |   +3 Editorial filled with emotes lol... My reaction for the Global Round as usual ^,^
 » 2 months ago, # | ← Rev. 2 →   0 Orz Imakf <《^,^》>
•  » » 2 months ago, # ^ |   0 Orz Imakf <《^,^》>
•  » » » 2 months ago, # ^ |   0 Orz Imakf <《^,^》>
 » 2 months ago, # |   +8 The last line is completely illegal, how will be the ratings gonna balanced than?
•  » » 2 months ago, # ^ |   +17 Everyone gets a 0 lol
 » 2 months ago, # |   +5 As a tester, i think that the problems are all very interesting.
 » 2 months ago, # |   +8 All the problems are very interesting!orz Cocoly1990, Imakf and waaitg!
 » 2 months ago, # |   +5 Consecutive rounds! :O
 » 2 months ago, # |   +49 Too many emojis, downvoted. Hope the contest is good tho.
•  » » 2 months ago, # ^ |   -22 you must be single.
•  » » » 2 months ago, # ^ |   +84 True
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   +9 Because I'm also, so True & True
 » 2 months ago, # |   +26 As a tester, I'm still curious how the authors found me for testing, I didn't know any of authors :D btw, don't miss this great, well prepared round from such awesome authors!
 » 2 months ago, # |   +31 As a first time tester, this is definitely the best round I ever tested
 » 2 months ago, # |   +3 Note :: UNUSUAL TIME OF CONTEST
 » 2 months ago, # |   +8 Brillant use of emojis
 » 2 months ago, # |   +139
 » 2 months ago, # |   +1 omg emoji round
 » 2 months ago, # | ← Rev. 2 →   0 Oops
 » 2 months ago, # |   0 I hope I can do at least a couple of tasks :3
 » 2 months ago, # |   0 as a participant I hope I will get +100 delta.
 » 2 months ago, # |   0 Ei contest e kupay dimu !!!
 » 2 months ago, # |   +3 I want another ConstructForces like 836 div.
 » 2 months ago, # |   +1 There are 10 subtasks, but I have a feeling only 4 would be doable by < master. Let's see, excited. Hopefully master tomorrow!
 » 2 months ago, # |   0 Thank you coddeforces
 » 2 months ago, # |   0 hoping to solve upto D!! :)
 » 2 months ago, # |   0 hopefully no choking this round
 » 2 months ago, # | ← Rev. 2 →   -12 Celtic /se
 » 2 months ago, # |   -8 Chinese round! /tyt
 » 2 months ago, # |   0 Hello everyone, I am a beginner programmer. I don’t know about the difficulty of Global round 24 . Anyone could explain about difficulty of problem in this round.
•  » » 2 months ago, # ^ |   -10 Very difficult
 » 2 months ago, # |   +5 Because of my university online exam in contest time. I can't participate in this round. Feeling sad.
•  » » 2 months ago, # ^ |   +4 Good luck with the exam. :(
 » 2 months ago, # |   0 omg 3 subtasks round Best of luck everyone
 » 2 months ago, # |   +22
•  » » 2 months ago, # ^ |   +58 Proceeds to fuck up both
•  » » » 2 months ago, # ^ |   0 Task failed successfully :)
•  » » 2 months ago, # ^ |   0 But, you should not leave the codeforces for the exams.
 » 2 months ago, # |   -18
 » 2 months ago, # |   0 Emojforces ☺️
 » 2 months ago, # |   0 Hope for fun with the interactive one and (3 subtasks) one .Best of luck everyone.
 » 2 months ago, # |   0 nice emoji
 » 2 months ago, # |   +11 Does score distribution imply that I should skip to G1 after D.
 » 2 months ago, # |   0 Everyone for good luck!
 » 2 months ago, # |   +3 omg Imakf round
 » 2 months ago, # |   +4
•  » » 2 months ago, # ^ |   +8 I lost this game. Though I will got $+\varepsilon$, my place is around 200 (without any FST).Anyway, the round seems good. Though some problems are typical, I love E! Thanks for the writers' and testers' amazing works!
•  » » » 6 weeks ago, # ^ |   +3
 » 2 months ago, # |   0 Unusual time ops;
 » 2 months ago, # |   0 im so hype im going to get a rating for once
 » 2 months ago, # |   +9 don't expect much you will do better.
 » 2 months ago, # |   +3 G1 easier than F, E .. intersting :)
 » 2 months ago, # |   0 So G has 3 subtasks? XD
 » 2 months ago, # | ← Rev. 4 →   0 All the best.
 » 2 months ago, # |   -10 I hate this round!
 » 2 months ago, # |   -8 please ban newbies
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 what wrong in this? I thought Global round is on par with Div1. 
 » 2 months ago, # |   +5 The problems are good quality.It suprised me very much.I am looking forward to more contests!
 » 2 months ago, # | ← Rev. 4 →   +7 Solution videos for problem B on youtube combined have over 1600 views.Unfortunately, people who uploaded videos didn't show their usernames, but one of them has to be vedantkakade.MikeMirzayanov
 » 2 months ago, # |   +41 The top standings in this contest are a good example of why the scoring system needs to be reformed, in my opinion.
•  » » 2 months ago, # ^ |   +22 Why is that? Looks like several top scorers were saved by the pretests which allowed them to resubmit. But the penalty put them beneath other submitters who didn't need as many resubmissions.
•  » » » 2 months ago, # ^ |   0 You have mentioned just penalty aspect when OP (brunovsky, correct me if I'm wrong) is talking about general scoring mechanism. Which is, basically, how many points you will get for solving particular problem at particular moment. The issue is well-illustrated by top-1 scorer who gets more points for speed-solving D (1666/1750) then for late solutions to much harder F (1523/2250) or G1+G2 (1536/2500).
 » 2 months ago, # | ← Rev. 2 →   -28 :|
•  » » 2 months ago, # ^ |   0 Contest is not over yet. Delete it.
•  » » 2 months ago, # ^ |   0 There are people who does cheat but using different ways but you my guy did this in the comment section....you could have waited for the round to be over
 » 2 months ago, # |   +14 Why is div1+2 D so hard again?
•  » » 2 months ago, # ^ |   +3 Yeah It was hard and was also interesting. Couldn't solve it though.
 » 2 months ago, # |   +17 the solutions to the first three problems were on youtube before the test was over, I think this interferes with the scoring of the round as many can copy and paste the solutions.
•  » » 2 months ago, # ^ |   0 How did you find these videos?
•  » » » 2 months ago, # ^ |   +3 haha lol!!
 » 2 months ago, # |   0 What was the logic in number B?
•  » » 2 months ago, # ^ |   0 If all the numbers have common divisor or factor, then the ans will be maxElement / commonFactor or else ans will be maxElement. Here you can find if the numbers have common factor by taking gcd of the whole array, and if gcd > 1 then it does have a common factor.
 » 2 months ago, # |   +9 How could C be approached?
•  » » 2 months ago, # ^ |   +8 You can think of dividing the vertices into 2 parts. eg. 1 2 2 3 3 4 4 4 5 6 7 7 9 can be divided into two part as following : IMP : sort the vertices by their weight1) 1 and 2 2 3 3 4 4 4 5 6 7 7 9, Now you can connect the left part's vertices to all the vertices of right part but you cannot connect any vertices of the same part, so total possible edges = len(left_part) * len(right_part) = 112) 1 2 and 2 3 3 4 4 4 5 6 7 7 9, but this configuration is invalid, as you can imagine that left's 2 is connected to right's 2 & 9 so basically you can go 2 => 2 => 9. So here you have to make sure that partition are done in such a way that there are no equal element in both partitions. left_part is strictly less than right_part elements.so best configuration we can find is : 1 2 2 3 3 * 4 4 4 6 7 7 9 which is 5 * 7 = 35Also edge case is when you can't partition the array. i.e all the elements are equal, so at that time just output n / 2 as you cannot connect more than 2 vertices
•  » » » 2 months ago, # ^ |   0 Thank you!Solution seems intuitive, too bad I couldn't connect the dots in time.
•  » » » 2 months ago, # ^ |   0 Best explanation and observation. Thanks.
•  » » 2 months ago, # ^ | ← Rev. 3 →   +7 Hintthe maximum number of edges can be achieved when the graph is only 1 connected component. SolutionFor each value a[i] , let A be the set having all values less than a[i] , and let B be the set having all values greater than a[i] note that you cannot make edges from a[i] to some x in A then from a[i] to some y in B because that will violate the condition in the statement ( you have edge from y to a[i] and edge from x to a[i] and (x <= a[i] <= y) from this point you can match every a[i] with every x in A then match every x in A with every y in B ORyou can match every a[i] with every y in B then match every y in B with every x in A and just handle the case when all elements are equal (every two nodes form a connected component)
•  » » » 2 months ago, # ^ |   0 Nicely explained, thanks a lot!
 » 2 months ago, # |   +6 Scariest problem D
 » 2 months ago, # |   +4 How to solve D?
•  » » 2 months ago, # ^ | ← Rev. 4 →   +14 Solution for D:Observe:when the deleted pegs firstly form a continuous segment with a length of $l \geq n/2$,we get a scheme.Enumeration length $l=n/2,n/2+1,...,n-1$,let's calculate the answer when the continuous segment's length is $l$.First,calculate $cnt$,which is the number of pair $(a,b)$ satisfying $a+1+b==l,a,b •  » » » 2 months ago, # ^ | 0 Thanks for your clear explanation!  » 2 months ago, # | 0 how to solve B? •  » » 2 months ago, # ^ | 0 basically take the gcd of whole array if it is greater than 1 than divide the max with gcd or else answer is max of that array •  » » 2 months ago, # ^ | 0 hint : think of gcd •  » » 2 months ago, # ^ | 0 GCD  » 2 months ago, # | +1 Anyone has the answer in D.(answer like O(1))?I mean an explicit formula  » 2 months ago, # | +1 What a tough contest :(((  » 2 months ago, # | +11 C was quite tough to spot the right answer. •  » » 2 months ago, # ^ | +1 I do agree •  » » 2 months ago, # ^ | 0 i was going in the direction of frequency and hashmap that how many smaller elements can be between 2 greater elements or how many greater can be between 2 smallerplease provide a hint •  » » » 2 months ago, # ^ | 0 The brief idea is to sort the array and split it in half then connect every edges between two halves. This won't violate the rule. Now you have to consider the case where there are same elements (which is a little bit complicate). •  » » 2 months ago, # ^ | 0 You're right.I spent an hour and a half doing problem C. •  » » 2 months ago, # ^ | 0 I guessed the solution but I can't prove it  » 2 months ago, # | +13 Solved problem F in a Div 1+2 Round for the first time! Yay •  » » 2 months ago, # ^ | 0 Why FST...sad  » 2 months ago, # | 0 How to solve Problem D when n % 2 = 1? In even cases, ig we had to consider diagonals, so, in the odd ones triangles? •  » » 2 months ago, # ^ | +3 In fact, it is wrong to consider diagonal.Consider$n=6$,$[1,3,5,6]$is a valid scheme,although$1,3,5$deleted all diagonals. •  » » » 2 months ago, # ^ | 0 Oh, I was thinking about calculating the ways in which the game ends with either a diagonal or a triangle 'breaking'. In the above case, the triangle 4-2-6 'breaks' in the end. I forgot to consider 'triangles' for even cases as well.  » 2 months ago, # | 0 D actually ended up being fun lol •  » » 2 months ago, # ^ | 0 how did you solve it? •  » » » 2 months ago, # ^ | +3 combinatorics •  » » » 2 months ago, # ^ | ← Rev. 2 → 0 after all operations we must be left with some chunk with size$\le (n + 1) / 2$(and possibly gaps in between).The last operation must've been removing a peg in the diametrically opposite chunk.Then just count the number of ways to do this using binomial coefficients and factorial  » 2 months ago, # | 0 Only solved till C but my best div 2 round so far.  » 2 months ago, # | 0 Any hint of problem C , (PLEASE DON'T GIVE COMPLETE SOLUTION) •  » » 2 months ago, # ^ | 0 You should think about the GCD. •  » » » 2 months ago, # ^ | +2 That's for problem B •  » » » » 2 months ago, # ^ | 0 ah my bad. sorry! •  » » 2 months ago, # ^ | 0 Quick sort partitions •  » » 2 months ago, # ^ | +8 Hint 1... How many roads can you make with n nodes of height 1 and m nodes of height 2? Hint 2... How many roads can you make with 2 roads of height 1, 4 nodes of height 2, and 3 nodes of height 3? If you need more help just reply!  » 2 months ago, # | 0 182673131what was the problem in this approach can anyone tell ? i was checking if all were divisible! if then ans is max/min else ans is max why i got WA in this approach didn't understand •  » » 2 months ago, # ^ | 0 answer is$\max(S)\div\gcd(S)$•  » » » 2 months ago, # ^ | 0 what if i don't go for GCD then? •  » » » » 2 months ago, # ^ | +3 then you get WA... •  » » » » » 2 months ago, # ^ | +3 got it [15, 20, 25] here 20 & 25 is not divisible by 15 but all are multiple of 5 so answer is 25/5= 5 that's why gcd works  » 2 months ago, # | -43 As a participant, I will thank you if you make this round unrated because of followings:1- The solutions to ABC where on network. 2- On the last minutes of the match, codes where up on some websites.And to other participants: if you are with me, upvote please.  » 2 months ago, # | ← Rev. 3 → +146 Here is some feedback on the problem set: A: Nice easy problem. First time in my life I submit without checking the correctness on the examples. B: Somewhat standard, but ok (set of integers, operations, what can you get? -> gcd). I enjoyed it. C: Ok problem. I did not prove my solution, though I think that I can prove it in 5 minutes. D: Standard problem, appropriate difficulty. I am not a fan since I knew what to do immediately after reading the statement (and then I did a mess... but that's another story). E: Wonderful. I sent 3 solutions, and I thought I had a proof for all of them. But the first two were wrong (not a bug, the algorithm was wrong). I really enjoyed this one. One is naturally lead to try and "get the biggest possible number" but the correct strategy is to go backward and I needed quite some time to understand it. F: Ok problem. The statement is far from interesting. The observation that we can understand if$i,j$are adjacent by looking at$f(i,\cdot)-f(j,\cdot)$is cool (I was lucky and it was the first thing I tried). Then, I passed the pretests with a randomized solution which I am not 100% should pass the tests (since it may be too slow). G: Thought about this one for 30 minutes straight. Not a single idea. I cannot solve it even with$n$queries. Truly seems impossible, great problem.  After reading the solution, I don't think anymore it is a great problem, still a very nice one though (because it seems totally impossible without the right idea). H: Not read. Overall the contest was very well prepared, the problems were nice, and the difficulties were on the spot. Congratulations to the authors! •  » » 2 months ago, # ^ | ← Rev. 2 → 0 On G, I had the following order of observations:1) You can find the maximum value in ~10 queries2) There are only at most two values which are unpaired with$k=2$:$1$, and potentially the maximum value.I couldn't finish from here in the contest, but someone gave me a hint afterward: The idea is that we can query$[a, m]$and$[m+1, b]$for a range$[a,b]$and$m = (a+b)/2$. This tells us how many unpaired values there are on the left and right; since there are atmost two unpaired values, we can go to the correct side.  » 2 months ago, # | 0 Auto comment: topic has been updated by Imakf (previous revision, new revision, compare).  » 2 months ago, # | +3 Please dont do cheating guys,it hurts alot especially in rankings and ratings •  » » 2 months ago, # ^ | 0 No one cheats in normal contests may be one or two who might want to freeze at CM or expert  » 2 months ago, # | 0 Why does taking gcd of the whole array and then dividing it by the last number work in Problem B? •  » » 2 months ago, # ^ | ← Rev. 3 → +2$\gcd(x,y) \vert x$and$\gcd(x, y) \vert y \Rightarrow \gcd(x, y) \vert (x - y)$Thus any element we add will still be a multiple of the$\gcd$of the entire set.However, by the Euclidean algorithm, we can always get$\gcd(S)$to be in$S$after some number of operations.Thus we can get$\max(S) - k\cdot\gcd(S)$to be in$S$for any$k=0,1,2,\cdots,\frac{\max(S)}{\gcd(S)}-1$(For greater k values the number would not be positive)Thus the max size of$S$is$\max(S)\div \gcd(S)$•  » » » 2 months ago, # ^ | +3 Thank you very much, great explanation!!! •  » » 2 months ago, # ^ | +1 It is kind of clever use of gcd algorithm that one learns in high school, i.e. gcd(x,y)=ax+by for some a and b.Note that if 1 is in array, then you can construct any element from 1 to a[n-1], and if you can construct 1 then also you can construct any element from 1 to a[n-1]. (basically you can construct 1 only if two elements have gcd 1 in the array).Similarly, you can work it otherwise. •  » » » 2 months ago, # ^ | +1 Bezout's Lemma! yay •  » » 2 months ago, # ^ | ← Rev. 2 → +1 I don't have a formal proof, but this is what I thought of :Base : If array has 1 or we managed to generate 1 then it is possible to generate each and every element from 1....max(array).Now let's do some case work :1) gcd is 1 for the whole array, so it means that there lies 2 elements which does not have common divisor, so let's assume it as 4 and 599, now you can generate values as 599 — 4, 599 — (4 * 2), ....., 599 — (4 * x), now this 599 - (4 * x) term will be surely < 4 as we already know that we can't reach to 4 as 599 is not divisble by 4. so any value of 1, 2, or 3. Now in case of 1 & 3, we can generate 1 by either (4 — 3) or (4 — 1) = 3 then (4 — 3) = 1. so we generated 1. Now if we have 2 then (4 — 2) is 2, but again 599 & 2 are not divisble, so 599 — 2, 599 — (2 * 2), and ..... we will get last value as 1. So in short whenever we have non divisible numbers we can go upto 1 for generation by successive subtraction.2) gcd > 1, let's say gcd is 5, so now whatever you do in the array your subtractions will result into a multiple of 5 as when you subtract two number which has x as common divisor, you will have a result that will also be divisible by x. so you have to output the number of multiple of gcd that you can fit in the arrayso ans is => max(array) / gcd(array)  » 2 months ago, # | -9 Who else agrees that the 2nd sample test case for problem C should be explained as well •  » » 2 months ago, # ^ | 0 that would give up solution  » 2 months ago, # | ← Rev. 2 → 0 So close to solving D.if n is even, go over all pairwise points, pretend this is the arc when it first touches the blue pin. We know that this can only happen with the smaller arch, and that the last point removed before it gets to this arc must be one of the opposite pin with the smaller arc. From there just do nCk and multiplies with factorial of two sets of points.if n is odd, solve similarly, except the outer arcs count before getting to this arc is the number of edges of adjacent pin instead of the number of points. •  » » 2 months ago, # ^ | 0 Don't loop over all pairwise points, but instead over all possible arc lengths when it touches the blue pin and then multiply by n.  » 2 months ago, # | +17 a similar problem as problem B: https://codeforces.com/contest/347/problem/C •  » » 2 months ago, # ^ | 0 A similar problem appeared recently but with lower constraints so you could simply add the missing numbers while you there's a missing number. I couldn't find it but I'm pretty sure it's in a CF round that happened durin 2020-2022. •  » » 2 months ago, # ^ | 0 mmm an even more similar problem lol https://mycode.prepbytes.com/problems/sorting/ELMT  » 2 months ago, # | 0 Thanks for the fast editorial! Also thanks for the round.  » 2 months ago, # | ← Rev. 4 → 0 Problem E:How can the answer of input 13 5 3 2 2 1 1 2be "YES"?I got WA2 and this is the case I failed :( •  » » 2 months ago, # ^ | 0 Use permutation [2, 3, 1], then 1, 3, 5 can be colored in this order.  » 2 months ago, # | 0 Well balanced round  » 2 months ago, # | +27 Thank you for problem G! Actually reloaded the page a couple of times to make sure it's$\le 30$queries, not$30 n$or something. The feeling of just how impossible the problem seems at first... priceless.  » 2 months ago, # | +18 Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!  » 2 months ago, # | ← Rev. 2 → 0 B is pretty hard for usual B imo. It’s an easier version of a 1800 rated problem. And that problem has negative numbersit’s so bizarre that B has so many submission. •  » » 2 months ago, # ^ | 0 it's not too hard to guess after looking at a few cases •  » » 2 months ago, # ^ | 0 Can you link that problem? •  » » 2 months ago, # ^ | +3  » 2 months ago, # | 0 finally a round i enjoyed :)...  » 2 months ago, # | +4 Completely forgot that on resubmission previous submissions are skipped, Resubmitted D for stupid reason, got -50 and +25 minutes.:(  » 2 months ago, # | 0 Thanks for the great problems and well-balanced round!The only negative thing I noticed is score distribution. Complexity jumps between A-B and B-C is definitely smaller then the ones between C-D and D-G1 (cannot say about other problems), but the point difference is two times bigger.Anyways, kudos to the problem setters and testers for an awesome job!  » 2 months ago, # | 0 Thanks for the round! I think F is incredible, and C is fun too.  » 2 months ago, # | +9 Problem D really pegged me.  » 2 months ago, # | 0 Hope everyone get prizes and get points❤️❤️❤️  » 2 months ago, # | 0 Intially I thought of Bipartite Solution">" -> Red edges, "<" -> blue edges and then For "=" I did not understand which color to assign and thought Bipartite wouldn't fit.To add Fire to above thought. I came up with a pattern which is giving solution for 2nd example1) sort the array 1 2 2 4 5 5 In Most of Hill and valley problems this pattern helps 2) And use the pattern [a1,a2,a3,a4,a5,a6] => [a1,a4,a2,a5,a3,a6] 3) In above pattern if we connect edges to adjacent and also connect each vertex with every vertex alternatively I got all the edges so dumped the idea of bipartite and tried to code the above approachWhat is that C question ?. I tried it for almost one day. I went nowhere •  » » 2 months ago, # ^ | 0 I did it considering a bipartite graph(maximum edges it can have is x^2/4 , x->vertices). Check out my submission for this problem.  » 2 months ago, # | 0 UnRated? •  » » 2 months ago, # ^ | 0 by somehow it's just rated again  » 2 months ago, # | 0 For me, E is very very easy, even easier than C. I can't understand why people struggle with it. When I saw problem E I was like, well, this problem can't be just a straightforward greedy problem, there must be something that I missed, but indeed it is. You just sort the colors by$x$and then find the maximum position that could be colored by colors other than$1$. I did struggle a lot on C and D. In C I didn't realize that the resulting graph could only be a bipartite graph, In D I ended up with a much more complicated approach using Inclusion-Exclusion Principle. To be clear, I'm not complaining, I'm just curious that maybe some people would have the same feeling as mine.  » 2 months ago, # | 0 I have written the whole code on my own and I have screen shots of my code and the details of the source code file which I created . I don't know how the code has coincidently coincided with someone [[Your text to link here...](https://github.com/chandan181singh/SOFTCRACKERS_Softablitz/blob/main/Screenshot%20(131).png)](https://github.com/chandan181singh/SOFTCRACKERS_Softablitz/blob/main/Screenshot%20(132).png).I am attaching the proof of the same with my comment .I request you to please restore my rating back .Thanks Shivam Kumar •  » » 2 months ago, # ^ | 0 Just copy the first link and paste in the browser to go to the first screenshot . And for the second link to work remove the last bracket and I from the link when pasting in the browser .Sorry for the In convenience.  » 2 months ago, # | 0 Is this reverse of problem C ?  » 2 months ago, # | 0 Why is there no contest till Dec 12? It's like almost 2 weeks from now.  » 2 months ago, # | 0 I think my F would be a little better than std.The beauty of this problem lies in$f(x,x)$. It is not difficult to find that the closer the point to$x$, the more times the point is repeated, and the different$x$, the different times each edge is repeated ~~ (isn't it obvious) . So we can actually figure out the distance between any two points based on this property. Here's an example (in the figure, the red number indicates the number of counts) : You will find that all the edges are repeated the same number of times except for the number of times that the edges between the two$x$are repeated, so you can consider the inclusion repulsion, which is actually$dis_{x_1,x_1}+dis_{x_2,x_2}-2 \times dis_{x_1,x_2}$. This should make sense, and when you're done, you actually find that the point between the two$x$has been calculated exactly$n$. In fact, it is easy to prove that for$2 \times dis_{x_1,x_2}$the middle of the two$x$must not be counted because it is already looped, And then$dis_{x_1,x_1}+dis_{x_2,x_2}$actually understands that every point is on the edge between these two$x$, so repeat the$n\$ calculation. So we've figured out the distance between any two points, and now we want to generate a tree, and in order to satisfy the distance that we figured out before, we need to minimize each edge, so we need to minimize the spanning tree.
»
6 weeks ago, # |
+32

Congratulations to tshirts winners! In a few weeks you will be contacted via private messages with instructions to receive your prize.

As usual, we used the following two scripts for generating random winners, seed is the score of the winner.

get_tshirts.py
randgen.cpp
List place Contest Rank Name
1 1764 1 QAQAutoMaton
2 1764 2 jiangly
3 1764 3 maroonrk
4 1764 4 fivedemands
5 1764 5 Vercingetorix
6 1764 6 ecnerwala
7 1764 7 gyh20
8 1764 8 GoRed
9 1764 9 p_b_p_b
10 1764 10 Ormlis
11 1764 11 duality
12 1764 12 Maksim1744
13 1764 13 neal
14 1764 14 353cerega
15 1764 15 emptyhope
16 1764 16 Egg_Tart_Forest
17 1764 17 dlalswp25
18 1764 18 hank55663
19 1764 19 Y25t
20 1764 20 ugly2333
21 1764 21 budalnik
22 1764 22 antontrygubO_o
23 1764 23 Sol1
24 1764 24 Endagorion
25 1764 25 ko_osaga
26 1764 26 turmax
27 1764 27 Kapt
28 1764 28 1092515503
29 1764 29 yuto1115
30 1764 30 liuhengxi
32 1764 32 arvindf232
43 1764 43 hitonanode
107 1764 107 hos.lyric
138 1764 138 jinmingli
140 1764 140 socpite
178 1764 178 Noam527
197 1764 197 physics0523
221 1764 221 US3RN4M3
243 1764 243 pavement
248 1764 248 ghoul932
364 1764 364 realcomplex
374 1764 374 yulik.daniel
388 1764 387 HollwoQ_Pelw
414 1764 414 Muelsyse
425 1764 425 SorasakiHina
426 1764 425 bcollet
434 1764 434 CRH380BL
464 1764 464 EnAnimant
492 1764 492 lmqzzz
495 1764 495 kriepiekrollie
•  » » 6 weeks ago, # ^ |   +8 WHOOOOOOOOOOOOOOOOOOOOOOOOO
•  » » » 6 weeks ago, # ^ |   +3 Yoooooooooo