### shishin's blog

By shishin, 2 weeks ago,

Hello, Codeforces!

On Sep/12/2021 17:35 (Moscow time) we will host Codeforces Global Round 16.

It is the fourth round of a 2021 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 2021:

• 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 2021 supported the global rounds initiative!

The problems were written and prepared by shishin and Artyom123.

We would like to thank these people:

You will have 2.5 hours to solve 8 problems. As always, we highly recommend reading all problems. Moreover, we really hope you upsolve the problems after the round, there are some interesting things to find out!

One of these problems is interactive, please see the guide of interactive problems if you are not familiar with it.

Score Distribution:

5007501000(750 + 1000)2000250030003750

Editorial:

The editorial

Winners

System testing finished, congrats to the winners!

Announcement of Codeforces Global Round 16

• +692

 » 2 weeks ago, # |   +488 As a coauthor I need contribution
•  » » 2 weeks ago, # ^ |   0 why contribution on profile just showing +38 even when you just got +362 on this comment only.
•  » » » 2 weeks ago, # ^ |   +42 Law of diminishing marginal returns.
•  » » » » 2 weeks ago, # ^ |   +2 what is this?
•  » » » 2 weeks ago, # ^ |   +44 CTC vs In-hand
 » 2 weeks ago, # |   +170 As a devoted tester who tried to make the round better, I wholeheartedly invite you to the contest. Will be fun, I promise!
 » 2 weeks ago, # | ← Rev. 2 →   -70 [deleted]
 » 2 weeks ago, # |   +137 As a soon to be Candidate Master I need your love and support.
•  » » 2 weeks ago, # ^ |   +50 Agnimandur orz
 » 2 weeks ago, # |   +35 Looks like there won't be rickrolling here, thank god
•  » » 2 weeks ago, # ^ |   +16 One of these problems is interactive.
 » 2 weeks ago, # |   +56 This round is going to be awesome. How do I know? Well, shishin and Artyom123 made a round 6 months ago which unfortunately went unrated. That was one of the best contests I participated in on Codeforces. It had every single quality one could hope for. I even wrote about it after the contest https://codeforces.com/blog/entry/88750. If you also enjoy similar problems, you will love this one.All the best to every participant. And thanks a lot to the authors!
 » 2 weeks ago, # |   -143 As a participant, pls give me upvotes, its at -10 now ;-; wishing y'all high deltas!In case you're not aware of it, below are some backup links of codeforces in case the main site goes down during the contest! Safety Linksm1.codeforces.comm2.codeforces.comm3.codeforces.com
•  » » 2 weeks ago, # ^ |   +32 Oops, pressed downvote by accident
•  » » » 2 weeks ago, # ^ |   0 lol
•  » » 2 weeks ago, # ^ |   -30 don't try to earn contribution begging for upvotes unless you're a tester, as you can see people don't like it just a useful advice)
•  » » » 2 weeks ago, # ^ |   -53 This was all irony man was just trying to make someone laugh :D will share memes the next time
•  » » » » 2 weeks ago, # ^ |   -19 lol ok))
•  » » 2 weeks ago, # ^ | ← Rev. 3 →   -11 Will the universe balance my negative contribution with positive rating deltas? ;-;
 » 2 weeks ago, # |   +79 As a problem researcher, I hope my testing is worth some contribution and a t-shirt. And of course, what I desire most is, your memorable ​experience in the round!
•  » » 2 weeks ago, # ^ |   0 Can we testers expect for t-shirts ??
 » 2 weeks ago, # |   +1 Again, where are my pants
 » 2 weeks ago, # |   0 Get ready for a good contest!We hope it will
 » 2 weeks ago, # |   +29 Where memes??????????
•  » » 2 weeks ago, # ^ |   0
 » 2 weeks ago, # |   +21 As a tester, read all problems (and then solve everything).
 » 2 weeks ago, # |   +54 Hope I can become GrandMaster after this Round.
•  » » 12 days ago, # ^ |   +17 You did it orz
 » 2 weeks ago, # |   0 Ngl , the meme announcement>>the actual one ;)
 » 2 weeks ago, # | ← Rev. 3 →   -6 all the best:)
 » 2 weeks ago, # |   0 Hope to become Pupil after this round
 » 2 weeks ago, # |   +7 I hope I can change the color of my name in this round
•  » » 2 weeks ago, # ^ |   0 Best Of Luck
 » 2 weeks ago, # |   0 I wanna get high rating!
 » 2 weeks ago, # | ← Rev. 2 →   -65 nununu
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   0 i have a feeling that it is a rickroll.edit: yes it is, i checked using a link unshortenner https://unshorten.it/
•  » » 2 weeks ago, # ^ |   -7 Isn't it obvious that it is a rickroll? Please don't spam it here. This platform is not for pranks.
•  » » 2 weeks ago, # ^ |   0 how is this getting upvotes?
 » 2 weeks ago, # |   0 I will solve C this time. I will make my name green.
 » 2 weeks ago, # |   +64 As a tester, I found this round to be one of the most interesting rounds I've ever tested. Good luck and have fun!
•  » » 2 weeks ago, # ^ |   +9 Why does this makes me feel scared?
•  » » » 2 weeks ago, # ^ | ← Rev. 2 →   -8 Coward! :P
•  » » » » 2 weeks ago, # ^ |   +9 Coward are the persons who dont fight when they are scared....Brave are those who fight even in their most scary battles, they fight even if they know that defeat is waiting for them.... I am scared though... I am always a bit scared before every contest but I fight in every contest and give my best.... and will always do it and climb my ladder high up above... Those who are scared and dont fight are cowards...Those who are scared and fight are brave...Those who aren't afraid of anyone but consider other's abilities are fearless....Those who think are perfect and look down on others are over confident....I am afraid because there are several strong programmers participating in the contest... they all are working hard... all are ready to climb the ladder above... and I too have some goal... I am scared because if I haven't worked hard enough I may end up loosing my goal... this doesn't mean that I am coward... because I am working hard and will try my best doesn't matter if my rating increases or decreased... have a look at my profile... I have never stropped to strive even if I go down... because that's the way I will climb up.... And I am happy that I am scared of others and I am confident on my skills... because that keeps my confidence to the optimum level...
•  » » » » » 2 weeks ago, # ^ |   0 Nice! I was not serious though. :)
•  » » » » » » 13 days ago, # ^ | ← Rev. 2 →   0 I see, I look down on cowards. That's the reason it infuriates me sometimes. I aplogise if you've felt offended.
•  » » » » » » » 13 days ago, # ^ |   0 I am the one who should apologize for the bad joke. :(
 » 2 weeks ago, # |   0 there is no better feeling in the world than seeing a cf round announcement
 » 2 weeks ago, # |   +6 Why is the contest always at Sunday but not Saturday？
 » 2 weeks ago, # |   +5 My first round in around 40 days. Waiting for negative delta :'(
 » 2 weeks ago, # | ← Rev. 2 →   -28 I have a question why can't there always be a contest in one the two weekend days ? in other days I wake up early and I'm the type of a guy that if he wakes up early he spends the day like a zombie and when i come back from work I'm a exhausted and would do like shit in contests (I know I won't do that better if not but I'm doing worst than when I'm not tired) of course let's not only put contests in weekends but maybe if there's a contest in friday shift it to saturday so it depends on the authors time ? or others don't agree with me with making a contest in weekends for some reason
•  » » 2 weeks ago, # ^ |   -17 What's wrong in having a contest in weekends like do you prefer to come back from work/college/school and participate or wake up when you want drink a cup of tea do some yoga and then participate in the contest wouldn't you perform better in that case?
•  » » » 2 weeks ago, # ^ |   +3 For me, It is on Sunday night. And So, It's was good for me. You know, authors can't make everyone happy with time because of timezones. and different preferences. Try Atcoder maybe their contest timings suits you.
•  » » 2 weeks ago, # ^ |   +1 we dont care about you
•  » » » 2 weeks ago, # ^ |   +1 it's a universal holiday so that would fit others time I'm not talking about my own time noob
•  » » » » 2 weeks ago, # ^ |   0 noob boob
•  » » » » 2 weeks ago, # ^ |   0 Bro, majority of us ( the peoples who share similar time to that of IST) are night owls, therefore we prefer this time... For me this is the best time for the contests to be commenced, If it would have had been on some different time, I don't know wether I would have been able to appear for it in the first place.
•  » » » » » 2 weeks ago, # ^ |   0 I didn't mean what hour the contest is but which day if it's Saturday or Sunday which most people don't have work/college/school they would have better focus because they're not tired from what their work
•  » » » » » » 2 weeks ago, # ^ |   0 I can't say anything regarding this... On the days of contest I try to keep myself calm and try my best to keep my brain empty all day so that I can do best during the contest... I don't know whether it works or not but atleast I feel such... also, It is organised globally so It can't be on Sunday for everyone. Like it's Monday now in India but Sunday in America... so If you look closely, there are peoples who are giving the contests in adverse conditions, like at some places, maybe they need to wakeup at 3:30 am to give it... thinking about it, we are in much better position regarding the timing and days of the contests.
 » 2 weeks ago, # |   +4 I hope to return expert after this round . Good luck to all of us.
 » 2 weeks ago, # |   0 I hope to be Pupil after this round , Your prayers please
 » 2 weeks ago, # |   -112 why could this fucking stupid blue name so frequently hold contests?
•  » » 2 weeks ago, # ^ |   +9 Be like him
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   -14
 » 2 weeks ago, # |   0 Is this round going to be rated for everyone?
•  » » 2 weeks ago, # ^ |   +9 yes
 » 2 weeks ago, # |   0 Will this be rated for div3?
•  » » 2 weeks ago, # ^ |   0 yes bro
 » 2 weeks ago, # |   0 Will there be problems for noobs like me also to solve?
 » 2 weeks ago, # |   -9 Why all the big contests are in sunday. I am the only one who is watching Premier League? :))
•  » » 2 weeks ago, # ^ |   +2 Am I the only one watching Italian Grand Prix ? :)
 » 2 weeks ago, # | ← Rev. 2 →   0 I hope to be cyan after this round. Good luck to everyone!
 » 2 weeks ago, # |   -31 Who can tell me the range of rating in this game? I didn't see anything about rating in the game statement.
•  » » 2 weeks ago, # ^ |   +21 The rounds are open and rated for everybody.
•  » » » 2 weeks ago, # ^ |   -12 Thank you very much！
 » 2 weeks ago, # |   +6 I wished to participate in my first Global round but unfortunately, today is Navi vs Vitality finals : /. https://www.hltv.org/matches/2350388/vitality-vs-natus-vincere-esl-pro-league-season-14
•  » » 2 weeks ago, # ^ |   0 very Useful
•  » » » 2 weeks ago, # ^ |   0 thanks
•  » » 2 weeks ago, # ^ |   +8 that can help in cheating
•  » » » 2 weeks ago, # ^ |   0 No I don't upload any videos while contest
•  » » » » » 2 weeks ago, # ^ |   0 Do you see any videos uploaded while contest Mr Conan ??
•  » » » » » » 2 weeks ago, # ^ |   0 but what is the purpose of making such a vid on the contest? you should solve problems in that time
 » 2 weeks ago, # |   0 according to the score distribution This round looks like speed forces !!!! your opinions are appreciated
 » 2 weeks ago, # |   +3 hope don't see "in queue" !
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   +49 Do not make any submission. You are safe then :)
 » 2 weeks ago, # |   0 I'm really new to coding should I give this ?
 » 2 weeks ago, # |   -18 Is this hackforces!!
 » 2 weeks ago, # |   -19 Was stuck on A for 30 mins so ended up skipping the contest :( Hopefully next time I will do well.
 » 2 weeks ago, # |   0 can i register now
 » 2 weeks ago, # | ← Rev. 2 →   -10 I didn't solve anything but A.
 » 2 weeks ago, # |   -7 Amazing round well balanced quests.I personally felt first 4 quests easy.And so did most of the others according to number of submissions.over all well balanced quests. And indeed this round is for everyone
 » 2 weeks ago, # |   +29 Bruh speedforces
 » 2 weeks ago, # |   +7 who is sus
 » 2 weeks ago, # |   +43 This (div1 + div2) = div3
 » 2 weeks ago, # |   -14 congrats to radewoosh for getting first! but tourist's rating might decrease again :/
•  » » 2 weeks ago, # ^ |   0 It didn't :D
•  » » » 2 weeks ago, # ^ |   0 tourist is now rated higher than benq again :o
 » 2 weeks ago, # |   +4 Actually, it was a good round. :)
 » 2 weeks ago, # |   +12 Greedyforces
 » 2 weeks ago, # |   -11 Is this approach correct for EI got a silly runtime error in last minute.https://ideone.com/ngaPsL
 » 2 weeks ago, # |   +8 sample tests were quite good today :) ... lovely round authors
 » 2 weeks ago, # |   +18 It took me at least 1 hour to understand what exactly D2 is meaning for.
•  » » 2 weeks ago, # ^ |   +3 still, I don't understand what it's said.
 » 2 weeks ago, # |   +3 How to solve F?
•  » » 2 weeks ago, # ^ | ← Rev. 6 →   +42 Best end points b/w each $a_{i}, a_{i + 1}$ (till where $a_i$ goes right, and till where $a_{i + 1}$ goes left) is independent of any other end points, it depends only on whether points $a_{i}$ and $a_{i + 1}$ each go left and then right or vice versa. So we can just use an $n \times 2$ dp for this state (position, left then right / right then left), and just use two pointer to calculate the optimal split point between $a_{i}, a_{i + 1}$ in $O(n + m logm)$ time. Removing ranges that already cover some $a_i$ makes the implementation easier since every range is now strictly between some $a_i$ and $a_{i + 1}$. (consider $a_0 = -INF$ and $a_{n + 1} = INF$). Detailed explanation of 'use two pointer' Keep two sort arrays for left and right end points. Assume $a_{i + 1}$ takes all initially. Put all the segments $r$ values in a multiset. Iterate over the left endpoints in sorted order for what $a_i$ takes and erase the corresponding the right values from the multiset as you go. The minimum value in the multiset is the furthest right endpoint $a_{i + 1}$ for the given left point. This takes $O(log m)$ time for each segment endpoint, resuling in a total of $O(n + m logm)$
 » 2 weeks ago, # |   0 Can some explain how to do the C problem in brief . I was getting WA on pretest 2 :(
•  » » 2 weeks ago, # ^ |   +4 Its always worth it to either leave a element alone or merge it with an adjacent one. Elements with mex 2 will always be alone and 0 and 1 should always be paired if they are adjacent. In that case, you just need to iterate through the indices and see if the previous one is the opposite of the current one and if it wasnt paired before to merge them.
•  » » » 2 weeks ago, # ^ |   0 That's exactly what I did, but I still got WA on pretest 2 :(
•  » » 2 weeks ago, # ^ |   0 There are 2 rows of input store each row in a different string and consider one element from each row of the same column as a single character. We can have 4 characters at most which will be [1 by 1], [0 by 0], [1 by 0], and [0 by 1], where the first digit is taken from the first row and the second digit from the second row. Notice that for bi-table, we can have max MEX = 2. so taking one column bi tables will maximize our answer. The [1 by 0] and [0 by 1] characters will always give MEX 2 by themselves. // fo(i,n) = for(int i=0; i
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   +3 some observations are: column [1, 0] and [0, 1] are the best, and they shouldn't be combined with any other columns (it won't increase the MEX sum) column [0, 0] is okay itself, but combined with [1, 1] is better. column [1, 1] itself yields no MEX points, but with a [0, 0] they can contribute 2 so you can greedily scan the columns from left to right, if you encounter [1, 0] or [0, 1], just add 2 to your answer, if you encounter a [1, 1] ([0, 0], respectively) column, first examine whether the next column is [0, 0] ([1, 1], respectively)
 » 2 weeks ago, # |   +3 Is it just me or the questions were actually simple today. I solved 5 of them for the first time.
•  » » 2 weeks ago, # ^ |   0 Same here
 » 2 weeks ago, # |   +12 How to solve E?
•  » » 2 weeks ago, # ^ |   +1 Think about the composition of your tree into buds. The optimal solution is always taking all of the buds and putting them one on top of the other. Each time you do this, the number of leaves in total decreases by one. That way you just need to count the total ammount of leaves — the total ammount of buds+1.
•  » » » 2 weeks ago, # ^ |   0 In this case, the answer is 2, right? Sorry if I misunderstood, but doesn't your approach say it is 1?
•  » » » » 2 weeks ago, # ^ |   +5 It should be (total amount of leaves (including leaves in buds) after removing all buds) — (number of buds).
•  » » » » » 2 weeks ago, # ^ |   0 That makes sense. Thanks!
•  » » » 2 weeks ago, # ^ |   0 F
 » 2 weeks ago, # |   +76 Randomised strategy in G:Answer is minimum over Sum of three edges adjacent to a vertex Sum of two edges that are not adjacent The first is easy to compute. For the second, randomly pick 0 or 1 for every vertex, and take the sum of min-cost edge between two 0-nodes and the min-cost edge between two 1-nodes. I did offline dynamic connectivity to do this for every time step.Complexity is like $\mathcal{O}(100\ n \log n)$ for $1 - \left(\frac{7}{8}\right)^{100} \approx 1 - 10^{6}$ chance to answer a query correctly. Barely fits TL. Somehow I also passed pretests with 50 iterations, but resubmitted 100 because I was too scared.
•  » » 2 weeks ago, # ^ |   0 That sounds cool. My approach to find the two disjoint edges with smallest weight was:Let $(u, v)$ be the edge with smallest weight. Take the next two smallest edges connected to $u$ and the next two connected to $v$. Also take the smallest edge $(x, y)$ that is disjoint from $(u, v)$. Somehow I convinced myself that the answer will be a pair of these $6$ edges. The only thing remaining is to find $(u, v)$ and $(x, y)$ for each query. For that I threw everything in a horribly messy segment tree that got TLE, but I'm guessing there is a better way.
•  » » 2 weeks ago, # ^ |   +8 I don't understand, why do you need dynamic connectivity?
•  » » » 2 weeks ago, # ^ |   0 I guess you don't need it, but I don't see how to do this without the $\log n$ factor and guess it's faster than going through in order with sets.
•  » » » » 2 weeks ago, # ^ | ← Rev. 2 →   +10 You can solve it with DSU with union by size + path compression to make that logn go down to ackerman inverse (and easier to code).Basically instead of a set that gives you lower bound, use the DSU to merge the ranges and give you the lower bound.
•  » » » » » 2 weeks ago, # ^ |   0 I don't quite understand, how do you handle edge removals with that?
•  » » » » » » 2 weeks ago, # ^ |   +25 Before anything, have the edges ordered.Then pass through edges in order. If the edge is good, then take the untaken positions in the range [l, r] that are alive and make them have the cost of this edge. The dsu is over the time of the queries, if we want to know the next untaken position after l then it's just the rightmost position in the component of l. Use up that position and unite it with the next position while it's <= r.
•  » » » » » » » 2 weeks ago, # ^ |   0 Thanks, I get it now. Cool trick!
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   0 Resubmit solution with $100$ iterations was the right decision. Probability of accept is $(1 - (\frac{7}{8})^{iteration})^{test\underline{ }count}$. Problem have more than $750$ test. With $50$ iterations probability of accept is about $0.39$, with $100$ iterations is $0.998$.
•  » » » 2 weeks ago, # ^ | ← Rev. 2 →   +30 I don't understand one thing: isn't that the probability for 1 individual query? How does it pass, given that each test gives like 10^5 queries lolI think that means that the tests don't have much variety of pairs of edges pairing up to give the min answer but idk
•  » » » 2 weeks ago, # ^ |   0 I think it's worse than that, and even with 100 I was lucky to pass.If you have a case where initially there are some random 4 super expensive edges, then in query $i$ you add an edge between $2i$ and $2i + 1$ of cost $Q - i$, the optimal pair of disjoint edges to take changes after every operation, and for every one of those pairs you need some colouring where they are both monochromatic and different colours.The events that you get correct answers aren't independent, but every second one is, so probability to succeed is at most $\left(1 - \left(\frac{7}{8}\right)^{iterations}\right)^{queries / 2}$ which for $Q = 10^5$ is already just 0.92...
 » 2 weeks ago, # |   +22 A,B,C,D1 all felt like Division 3 level of difficult increments.
 » 2 weeks ago, # |   0 someone help me with A question ,this was my first contest
•  » » 2 weeks ago, # ^ | ← Rev. 3 →   +3 find the position of the median "pos = ceil(n/2.0)". before this position, consider all elements to be zero. So we have to distribute the sum s among the leftover places "left = n-pos+1". The answer simply will be "sum/pos". Since, if the sum can not be divided equally among the leftover positions, the remainder will be added to the positions greater than pos. As we are finding the median the array should be sorted non decreasingly at all times.
•  » » » 2 weeks ago, # ^ |   0 why is it we are taking zero before position of median?
•  » » » » 2 weeks ago, # ^ |   0 because we are trying to maximize our median and if we take other numbers in those positions the sum left to distribute among the leftover positions will decrease and our median's magnitude will decrease too.
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   +3 Inspired by the n=7, s=17 test case (optimal distribution: 0, 0, 1, 4, 4, 4, 4), My strategy is to put the largest possible value M over $\frac{n}{2}$ times. (to reach the median place)more formally, let's consider 2 cases: n is odd, which means we should put M $\frac{n+1}{2}$ times n is even, which (by the definition of median in this problem) means we should put M $\frac{n}2+1$ times so the largest possible median value M can be derived: $M\leq \frac{2s}{n+1}$, if n is odd $M\leq \frac{2s}{n+2}$, if n is even
•  » » » 2 weeks ago, # ^ |   +8 gogogofuxk & saichandan68 got it, thanks
 » 2 weeks ago, # |   0 can anyone tell why my this solution of C give tle https://codeforces.com/contest/1566/submission/128642893 ?
•  » » 2 weeks ago, # ^ |   0 probably big overhead of recursion + overcomplicated + O(n*8) instead of O(n) + maybe cache misses
•  » » » 2 weeks ago, # ^ |   0 n = 10^5 na so i don't think recursion stack can be big enough to give tle.
 » 2 weeks ago, # |   +76 Can we just appreciate this?
•  » » 2 weeks ago, # ^ |   +32 Frankly, it looks like div3 gradient and this is not particularly good. I don't complain though
•  » » » 2 weeks ago, # ^ |   0 -100 rating prediction here just because I overcomplicated myself on D2 and couldn't debug it. Amazing round.
 » 2 weeks ago, # |   -49 I guess pretest for D2 are very weak. My n*m*log(m) works in just 46ms. Expecting a lot of FST's there
•  » » 2 weeks ago, # ^ |   +20 Why would n*m*log(m) not work?
•  » » » 2 weeks ago, # ^ | ← Rev. 2 →   -19 n*m*log(n) definitely would. i mean, my friend uses something different and got 600ms and he will probably FST. I pointed on n*m*log(m) time just to show that samples are not that good, because it should work longer (but still pass) at max test, i think.
•  » » » » 2 weeks ago, # ^ | ← Rev. 2 →   +6 Why would it? $O(n * m^2)$ is just $300 \times 10^5$ = $3 \times 10^7$ operations which should easily pass consider its not even something heavy like modulo. My $O(n * m^2)$ soln also runs in 46ms on pretests.
•  » » » » 2 weeks ago, # ^ |   0 Ok, i was wrong, there is not much failed solution, but my friend got TLE, so i wasn't that wrong
•  » » 2 weeks ago, # ^ |   +1 but n*m*log(m) is like O(10^6), it should totally pass...
•  » » » 2 weeks ago, # ^ | ← Rev. 2 →   -19 read my reply above, you misunderstood me
•  » » 2 weeks ago, # ^ |   +3 According to me O(n*m*m) will also work on an average. Don't know whether I will fst or not.
•  » » 2 weeks ago, # ^ |   0 My O(n*m²) code works in just 62 ms: 128625308
•  » » 2 weeks ago, # ^ |   +3 Please don't spread fud, you will scare the noobs :(
•  » » » 2 weeks ago, # ^ |   0 Also even n^3 for n = 900 can pass in < 1 second on simple operations
 » 2 weeks ago, # |   -11 I think score for D2 should be at least 1250
•  » » 2 weeks ago, # ^ |   +12 But if score for D2 was 1250,the total score of D would be equal to score of E, but E is much harder than D.
 » 2 weeks ago, # |   -24 Is pretest too weak in D1 and D2 ? O(m^2) passed on D1 ?
•  » » 2 weeks ago, # ^ |   +51 Its strange that youre the second person saying that pretests were weak because a solution that should pass is passing
•  » » 2 weeks ago, # ^ |   0 Yeah D1 was Brute force
•  » » 2 weeks ago, # ^ |   +7 $n, m \leq 300$ in a given test. $O(n \times m ^ 2)$ is equivalent to $O((n \cdot m) \times m)$, we know the first term is bounded by $10^5$ and the second is bounded by $300$, the worst possible is $3 \times 10^7$.
•  » » » 2 weeks ago, # ^ |   0 yes, I have mistake in calculation
•  » » » 2 weeks ago, # ^ |   0 oh well, and I applied multiset pbds
•  » » » » 2 weeks ago, # ^ |   +3 I applied a separate Fenwick tree for each row :-)
•  » » 2 weeks ago, # ^ |   0 $t <= 100$
 » 2 weeks ago, # |   +15 Online judge is slow again today !!
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   +11 not just slow bro, it's actually frozen on 16% :/
•  » » » 2 weeks ago, # ^ | ← Rev. 3 →   0 yay it's going now
 » 2 weeks ago, # |   -8 Gread round solve 4 problems for the first tme ever
•  » » 2 weeks ago, # ^ |   +30 easy!=good...
•  » » » 2 weeks ago, # ^ |   0 I am agree with you
 » 2 weeks ago, # |   0 When is the rating coming out??
•  » » 2 weeks ago, # ^ |   0 Some time after the problems are tested. Unfortunately there were a lot of submissions this round so I think this might be slowing down the process.
 » 2 weeks ago, # | ← Rev. 2 →   -28 The first 5 questions of this contest (D1 & D2 separated) should be fine and easy to implement for intermediate coders.The sixth question E (tree problem) is a little complex since not all cases of bud-leave trees are shown in the test case, but it should also be fine (check the editorial for solution).
•  » » 12 days ago, # ^ |   0 Sorry if my comment was sensitive to you.They're my opinions on the difficulty of the problem.
•  » » » 12 days ago, # ^ |   +4
 » 2 weeks ago, # |   +124 Codeforces server right now
•  » » 2 weeks ago, # ^ |   +44 I'm at least happy it only went full potato mode now and not during contest :P
•  » » 2 weeks ago, # ^ |   0 Does that actually work?
•  » » 2 weeks ago, # ^ |   0 seems like there were many who are looking farward their positive and negetive deltas
•  » » 2 weeks ago, # ^ |   +44 Meanwhile, G having 630+ (and counting) tests..
•  » » » 2 weeks ago, # ^ | ← Rev. 2 →   +1 740+ and counting...is this the highest number of tests any problem on cf ever had :thonk: XD
 » 2 weeks ago, # |   +54 Problem G systests o_0
 » 2 weeks ago, # |   0 A nice contest,i feel very good.
 » 2 weeks ago, # |   +134 G has 753 tests but still I uphacked my solution...
•  » » 2 weeks ago, # ^ |   +36 And our beloved Systests have gone somehow. Take a look at the number of tests of this submission 128675942. Maybe something went wrong due to exceptionally large datasets? isaf27
•  » » » 2 weeks ago, # ^ |   0 I think that's why system testing was so slow
•  » » » 2 weeks ago, # ^ | ← Rev. 2 →   -30 We added 750 more random tests just to hack some random wrong solutions (aka while not TL) for that problem. On polygon, such solutions failed with good probability, but it doesn't help on Codeforces (maybe faster testing machines).To make it possible to upsolve the problem without 10 mins waiting we decided to remove these added tests.Maybe system testing was slow because of this, but the size of the package for that problem was normal (25 Mb).
•  » » » » 2 weeks ago, # ^ |   +90 I don't think that adding tests during the contest after reading competitors' solutions and aiming at them is nice (and should be announced).Also, mine and mango_lassi's solutions are provable (OK, mine is with greater TL), while in H I've implemented a poor heuristic, which maybe can be fairly hacked. I'm not sure that the priorities were good.
•  » » » » » 2 weeks ago, # ^ |   -37 In H we had pretests = tests and of course, we doesn't change tests, because they won't be random in this case.My opinion about changing tests: it is ok because it is the participant's problem, that their solution is incorrect. For example, we add all successful hacks to tests before system testing. Also, it is fairer to the participants who solved the problem correctly. In Codeforces with pretests format, you should understand that your solution may fail if it is incorrect (but passed pretests).After that case, I understood that there is a big minus of this: some good randomized solutions like yours (that works with probability 10^(-3) for example) may fail after such "stress testing". I don't want to do such things in the future (with many tests) and will add tests only in case of single counterexamples to the solution.
•  » » » » » » 2 weeks ago, # ^ |   +69 I strongly don't agree. After years of experience I can tell that "probably tests are weak and something not exactly correct will pass" is a good assumption and a part of strategy (at least on CodeForces) which worked many times.Of course, the best thing to do is to make this assumption wrong and make everyone forget about it, but adding tests during the contest is not a good way.In H I totally forgot that the statement says that the tests are random, sorry for that.
•  » » » » » » 2 weeks ago, # ^ |   +152 If you are a contest setter/admin, please don't add tests from reading submissions in any situation. This contradicts the objective nature of programming contests. It also encourages people to obfuscate their code so that a coordinator won't be able to understand it and produce a countercase.If you have ideas for tests to break bad random solutions, you should add them before the contest. Besides hacks (which are built into the contest rules) the tests should be finalized, and if there is an extreme need to fix the cases it should not be based on things realized during the contest.It is a bit sad that this needs to be stated, especially to someone who is supposed to be overseeing other problemsetters.
•  » » » » » » » 2 weeks ago, # ^ |   -14 IIRC obfuscating solutions are against the Codeforces rules.
•  » » » » » » » 13 days ago, # ^ |   0 Besides hacks (which are built into the contest rules) And which are limited to people in your room, making it practically impossible to gang up on someone.(And are almost non-existent recently, but that's another topic.)
•  » » » » » » 13 days ago, # ^ |   +38 This is so wrong.You're seriously damaging competitive integrity by interfering fair competition :(
•  » » » » » » 13 days ago, # ^ |   +57 it is ok because it is the participant's problem, that their solution is incorrect That's fucking stupid. I'll say it again to emphasise how fucking stupid it is: that reasoning is fucking stupid. Sorry, not sorry, there's no other way to put it because it's a topic that's been discussed to death.You can add tests that break one solution but not another. For one contestant, you thus say "incorrect solution? your fault", while for another, you say "it may be incorrect but it passed tests so it's fine xD :P". That removes any trust in impartiality of judging — why should we trust that you're not focusing on someone in particular? If you make sure e.g. tourist's wrong solutions fail no matter what, then it's not fair to tourist because he's forced to play under different rules than everyone else. It's called fairness.
•  » » » » » 2 weeks ago, # ^ |   +30 Both solutions hacked :|
•  » » » » 13 days ago, # ^ |   +39 Adding test data in the middle of a 2.5h contest is not OK.
 » 2 weeks ago, # |   +3 In the sample 3 of D2, how the minimum answer is 4. Shouldn't it be 2 if we arrange people in this manner — 1 1 3 1 4 4 1 1 2
•  » » 2 weeks ago, # ^ |   +3 persons with lower eye sight should be given seats with lower numbers but in your sequence 3,4 is bigger than 1,2 one should consider the total sequence not for each sequence
•  » » 2 weeks ago, # ^ |   0 As stated in the problem statement: for any two people i, j such that ai<aj it should be satisfied that si<sj. Therefore, the people can only be arrange in an increasing order.(similar to what tankala.msk said)
 » 2 weeks ago, # |   +37 We are sorry for a slow system testing.Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!
 » 2 weeks ago, # |   0 To easy D1 and C for global round, that's why it was fastforces, not code. But still, thank you for this round
•  » » 9 days ago, # ^ | ← Rev. 2 →   0 imo first 5 were too easy
 » 2 weeks ago, # |   0 I screwed up because under the influence of problem B I interpreted C as "each column value is in exactly one bi-table". lol
•  » » 13 days ago, # ^ |   +7
 » 2 weeks ago, # |   -60 only a fucking stupid blue name could make this fucking stupid contest
 » 2 weeks ago, # | ← Rev. 2 →   0 deleted
 » 2 weeks ago, # |   0 22k registered but only 11k submitted, this is not good :/
»
13 days ago, # |
Rev. 5   +93

Since the official announcement isn't here yet and I'm an impatient person, I've decided to find out who won the t-shirts for myself.

As always, you can do the following steps to get the t-shirts winners of Global Rounds:

2) Use it to compile randgen.cpp :

randgen.cpp

3) Run the Python script winners.py, replacing the number in contest = [] with the ID of the contest in question (in this case, 1566):

winners.py

Both of these scripts are taken from the official winners announcements in previous Global Rounds, but if you have any doubts you can always check these results against the official ones later.

With that out of the way, congratulations to the (unofficial) t-shirt winners:

List place Contest Rank Name
2 1566 2 tourist
3 1566 3 QAQAutoMaton
4 1566 4 jiangly
5 1566 5 ksun48
6 1566 6 Alice_foo_foo
7 1566 7 He_Ren
8 1566 8 Benq
9 1566 9 tatyam
10 1566 10 hitonanode
11 1566 11 hanbyeol_
12 1566 12 kotatsugame
13 1566 13 fivedemands
14 1566 14 sansen
15 1566 15 blackbori
16 1566 16 Ormlis
17 1566 17 maroonrk
18 1566 18 snuke
19 1566 19 duality
20 1566 20 mango_lassi
21 1566 21 aid
22 1566 22 Miracle03
23 1566 23 Argentina
24 1566 24 voidmax
25 1566 25 nick452
26 1566 26 ccf_n0i
27 1566 27 dorijanlendvaj
28 1566 28 huhaoo
29 1566 29 Geothermal
30 1566 30 Maksim1744
40 1566 40 m_99
69 1566 69 alireza_kaviani
168 1566 168 Kite_kuma
195 1566 195 emptyhope
234 1566 234 Plasmatic
256 1566 256 Seyaua
291 1566 291 foolishgoat
315 1566 315 tobias.glimmerfors
335 1566 335 usuyus
345 1566 345 nok0
348 1566 347 _dg_
367 1566 366 ButterflyDew
383 1566 383 dimdim
405 1566 404 fishy15
420 1566 420 JeffreyLC
447 1566 447 wh2005
448 1566 448 Jarif_Rahman
451 1566 451 suyiheng
483 1566 481 Aelhurn
 » 13 days ago, # | ← Rev. 2 →   0 Can somebody help me in finding a smaller test case in which this code is failing. This is the code for Problem D2. Thanks in advance:)
 » 13 days ago, # |   +30 Congratulations to snuke for returning to LGM(For not disturbing him I didn't ping his name)
•  » » 13 days ago, # ^ |   +77 thank you
 » 13 days ago, # |   0 I am so sad that I couldn't participate in the contest.
 » 13 days ago, # |   0 I just want to get a T-shrit
 » 13 days ago, # |   +103 Here is some feedback on the contest (a bit late). Median Maximization. Nice, clean, not trivial. A very good cakewalk problem. MIN-MEX Cut. An easy problem which still requires observations with a natural statement. Easy to implement. Very good. MAX-MEX Cut. The statement is complicated and not interesting, the solution is standard. This felt too easy for its position. Seating arrangements. Nice problem, I think it was a good idea to split it into two subtasks. The hard subtask required me to stop and think and I enjoyed implementing it. I like that the implementation is somewhat demanding (for the problem position). It was a good idea to use the constraint $n\le 300$ instead of $n\le 2000$ which would have been just a pain without adding anything to the problem. Buds Re-hanging. The sudden realization that one can create a "bud-decomposition" was satisfying. The solution is both very clean and unexpected. This one is the typical problem that, with 50% probability, I get stuck on (this time I was lucky). Points Movement. Standard but nice problem. I am pretty sure I had seen something similar, still it was cute and I enjoyed solving it. For experienced contestants, the vast majority of the necessary observations are standard. Four Vertices. The statement is not very interesting (the problem is not really about graphs), but the solution is nice and nonstandard. During the contest I was very close to solving this one, but I was too slow on the other problems and I didn't have enough time. I am quite disappointed that the tests were weak and you decided to add tests during the contest, please refrain from doing that in the future (for all the reasons explained here). I had fun participating. It was a well-balanced contest with good problems. Apart from adding tests to problem G, everything else was well prepared. Thank you to the authors.
•  » » 12 days ago, # ^ | ← Rev. 2 →   +15 Just a note about D2 — Looking at your submission (128615822) I think you overkilled the implementation. I felt it was much easier with regard to implementation than the average D level problem.Example of an easy way to implement it — 128621602.
 » 12 days ago, # | ← Rev. 2 →   +98 I was trying to hack this submission 128743016 to problem G, but it returned "Unexpected verdict" (hack 756413). I wonder if there are any problems in the system, or my input is invalid? Hack6 6 1 4 1 1 2 100 1 3 101 4 5 102 4 6 103 2 5 104 0 
 » 11 days ago, # |   0 Good contest GG :>
 » 11 days ago, # | ← Rev. 3 →   -9 My solution 128624580 for problem 1566C has been skipped due to some similarities found with other codes. I feel that such similarities are bound to happen in such types of questions. I compared my code with the people who have written similar codes, and I can definitely see some similarities, but these similarities are bound to happen, due to the nature of the question, as the logic was pretty straightforward, and not much can be done in order to write very distinct code. It is quite normal to use ans variable to store the final answer, run for loop to traverse through the string and update the ans variable. I don't think this is a case of any kind of plagiarism as this is highly possible when thousands of people are submitting their solutions. I have always been honest while submitting my solutions, and I can say that this is not a case of plagiarism. I request the admin to kindly accept my solutions, as they have been honestly written by me.
•  » » 11 days ago, # ^ |   0 Yes, Same happens with me
 » 11 days ago, # |   +1 Today I got a Notification that Your solution 128625122 for the problem 1566C significantly coincides with solutions milan0027/128625122, shalini_agrawal/128645632. I don't know why this happened. I didn't copy code from anywhere. I wrote my own solution. You may also compare the coding style of both the solution they are significantly different. If it's a system glitch kindly rectify it.
•  » » 11 days ago, # ^ |   -8 Exactly! Definitely there is some glitch that needs to be rectified.
 » 11 days ago, # |   +1 Today I got the notification that my solution 128612189 for the problem 1566C significantly coincides with solutions yashmittal19/128612189, ooz/128628009.Since ooz submitted solution around 25 minutes after me, so accusation is basically of sharing my solution. But I have not shared any of my code nor did I use sites like ideone. And even I don't know him. I don't know how to proof this but I have been giving contest regularly since last year and have never indulged in such malpractice. So I request admin to accept my solution.
 » 11 days ago, # |   0 I have a question .. for this round my rank decrease but now it increase to the previous position what is the reason?
•  » » 11 days ago, # ^ |   0 Hey, there is a notification snackbar on top of the website, could you please to read it for me *_*
•  » » » 10 days ago, # ^ |   0 I already read it but I want to know the reason :)
•  » » » » 10 days ago, # ^ |   0 to remove cheaters through plagiarism check
 » 11 days ago, # |   -8 I got notification that Your solution 128607740 for the problem 1566C significantly coincides with solutions Candidate_noob/128606285, deepanshu55/128607740. This is clearly a coincidence. I don't know how to prove that but problem logic was pretty straightforward and you can compare coding style with my previous submissions. I don't even know Candidate_noob.
•  » » 11 days ago, # ^ |   0 Agreed. This should be fixed.
 » 11 days ago, # |   +9 This is another comment about having received a notification of plagiarism in problem 1566C. I did not share my solution or use online code editors.
 » 11 days ago, # |   +1 Sir, I recently got a notification about plagiarism in Codeforces global round 16 and the problem is 1566C and the notification says I got the same answer as the other contested but I didn't copy and not even shared the solution and not even got it from any publicly available codes I wrote it on my own and I even want to say that problem is so simple that its solution may come same for some people in that large participants. Please think about this and that's all I want to say, So please accept my solution. I hope I will get my rating back soon.
 » 11 days ago, # |   0 I got the notification from Codeforces stating "Your solution 128612338 for the problem 1566C significantly coincides with solutions apoorv17/128612338, sajjad.h/128647926." I have neither shared my solution nor ran it on ideone. I don't know the other person in fact we belong to the different countries. Since the problem was trivial so it can easily happen that two person use a similar approach, I don't have any proof to prove this but such false plagiarism claims and reverting the ratings wastes all 2-3 hours of effort and demotivates for further round. I think Codeforces should improve their plagiarism checker algorithm so that in future no false positives occur.
 » 11 days ago, # |   0 This must be really difficult to decide when thousands of solutions are nearly similar luckily my code is always so shitty that no other code is similar to it :P
•  » » 10 days ago, # ^ |   0 yeah, but it's not our fault too that problem 1556C is that easy that people can think similar solution. and on this site you have to prove yourself to be not guilty but how can someone like me prove myself if people thought the same approach it really hurts when u just started cp and tried and got the solution correct and then they just say my answer matched to some dude and now I don't deserve the rating it's just too bad
 » 10 days ago, # |   0 It was a nice one to attempt
 » 10 days ago, # |   +25 MikeMirzayanov can you please update problem ratings of the last Edu and this Global Round? It's been 10 days.
 » 10 days ago, # |   -8 I am once again writing this comment for plagiarism flag for problem 1566C. My code was wrongly flagged. Kindly look into this.
 » 10 days ago, # |   0 why my ratings got deducted for this round and then never added? All my friends whose rating where deducted, their ratings are now back to normal , but why not mine?
 » 5 days ago, # |   -7 MikeMirzayanov Hey, in the last global round , my solution for problem 1566C was flagged for plagiarism. I want to clarify that by no means I have written some one else's solution, and it was my own code that I wrote honestly. I don't even know the people who wrote codes similar to mine. The code is so small that similarities with others is possible. Kindly accept my solutions, as I have always been honest while giving the contests, and if such false flags are given against me, it will discourage me from being honest in future. I can literally see many other codes similar to me that were not reported. Kindly look into this. Hoping for the best. I have been constantly trying to talk to you, but I have received no response yet. I won't accept this injustice against me, I would not let my original codes be skipped due to false theories. The people who were flagged with me have got their ratings back, but not me. How is this fair?
•  » » 5 days ago, # ^ |   -8 Just to let everyone know that I know this guy personally and that the issue he is addressing is 100% authentic. He gives contests honestly and I too feel that his submissions should not have been skipped. I understand that plagiarism check is a hard job. You can never know with certainty if someone has copied or not from someone else. So this small margin of error can happen. But I believe that if someone is constantly trying to reach out for clarification, he/she must be heard. I hope that MikeMirzayanov looks into this soon.