dario2994's blog

By dario2994, 19 months ago,

Hi!

On Jul/25/2021 17:35 (Moscow time) we will host Codeforces Global Round 15.

This is the third round of the 2021 series of Codeforces Global Rounds. The rounds are open and rated for everybody.

The prizes for this round are as follows:

• 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!

Problems for this round are set by cip999 and me. Thanks a lot to the coordinator antontrygubO_o, to the testers gamegame, ajit, golions, skydogli, McDic, rabaiBomkarBittalBang, nweeks, Marckess, HenriqueBrito, gratus907, bWayne, zscoder, TheOneYouWant, and to MikeMirzayanov for the Codeforces and Polygon platforms.

You will be given 9 problems and 2 hours 45 minutes to solve them.

The scoring distribution is 250-500-1000-1000-1500-1500-2500-2750-3750.

If you are tempted to make one more comment on the scoring distribution, read this.

Good luck and see you in the standings!

UPDATE 1: Thank you very much for participating, we hope you liked the problems (and sorry to top contestants for giving a not-so-fresh problem I).

Here you can find the editorial (with a bit of behind-the-scenes, some obscenely wrong preditions, and hints for all the problems).

UPDATE 2: Congratulations to the winners!

Announcement of Codeforces Global Round 15

• +823

| Write comment?
 » 19 months ago, # | ← Rev. 2 →   +277 Time to upsolve global round 11.
•  » » 18 months ago, # ^ | ← Rev. 4 →   +139 People be like: See a fun comment: upvote; See a comment discussing testers of a contest: downvote; See a red coder write a comment: upvote; See a comment with a lot of downvotes: downvote; See somebody praying to reach a higher level: downvote
•  » » » 18 months ago, # ^ |   +85 When my contribution exceeds a hundred, I will make an stream with an analysis of the 11th global round !!!
•  » » » » 18 months ago, # ^ |   +23 Good luck, sir :)
•  » » » » 18 months ago, # ^ |   +9 Good luck.
•  » » » » 16 months ago, # ^ |   +5 ivanz Hey! any plans for the stream? you have crossed 100
•  » » » 18 months ago, # ^ |   +9 True!!!
•  » » » 18 months ago, # ^ |   +5 True! SpoilerSo I hate posting comments
•  » » » 18 months ago, # ^ |   +20 So you thought people will read this comment and just hit the upvote button as well?
•  » » » 18 months ago, # ^ |   +8 Your comment falls into fun category. Take my upvote!
 » 19 months ago, # |   -56 Can we say "All hail our emperor Anton" here? :)
 » 18 months ago, # |   -95 I'm a simple man. I see anton, I take part.
•  » » 18 months ago, # ^ |   +200 People be like: I'm a simple man. I see T1dus, I downvote.
•  » » » 18 months ago, # ^ |   -93 Imagine banning someone for a ping
•  » » » » 18 months ago, # ^ |   +40 Imagine that ping being mulitplied 20 times as much.
 » 18 months ago, # |   +2 So we will have 3hrs or 2:30? Cuz on the contest table it says that it lasts 2:30hrs. Thx;)
•  » » 18 months ago, # ^ |   0 I guess it's 2:30 as per the contests table
•  » » » 18 months ago, # ^ |   +3 Already fixed at 2: 45
 » 18 months ago, # |   +175 As a tester who has not been yet added to the contest announcement, I can say that solving the problems will make you feel warm and fuzzy inside. I am very sad that I cannot participate in this contest.
•  » » 18 months ago, # ^ |   -48 I would like to say that some youtube channels provide solution code during contest is running it is totally unfair to most of the participants plz take proper steps to stop this.
•  » » » 18 months ago, # ^ |   +22 bruh you are indirectly promoting that, better we talk less about it and more focus on learning from the round by participationg
•  » » » » 18 months ago, # ^ |   -17 You're right but if the Authority of Codeforces shouldn't take proper step the day is not so far even high rated like >=1600 rated problem solution will also find during contest time.We all want a fair contest.
•  » » » » » 18 months ago, # ^ |   +52 don't cry about it, just solve more problems than the distributor.
•  » » » 18 months ago, # ^ |   +5 Just be faster, most cheaters take a long time to do even A, genuine coders can easily outpace them.
•  » » 18 months ago, # ^ |   +11 To perform better, should i solve the author's previous contests? Please give me some suggestions as i am a newbie.
•  » » » 18 months ago, # ^ |   0 authors usually give some variety to their problems, it will never be said enough: to get better don't cheat the system just train and keep practicing
•  » » 18 months ago, # ^ |   +17 warm and fuzzy feeling! you mean pain!!
•  » » 18 months ago, # ^ | ← Rev. 2 →   0 Lol no wonder why a grandmaster gains satisfaction from solving all problems:)
•  » » » 18 months ago, # ^ |   +39 Re: your original comment: I wrote "very sad" because it turns out I did quite decently in testing. If I didn't have to travel, this would have been my first H solved in contest + maybe IGM. Now, it is just another missed (possibly) LGM performance..
 » 18 months ago, # | ← Rev. 2 →   +31 My first global round, exited to see the problems and maybe cry afterwards :)
•  » » 18 months ago, # ^ | ← Rev. 2 →   +12 So "exited" that you wrote "exited" instead of excited.
•  » » » 18 months ago, # ^ |   +19 lol didn't notice that :) hahaha
•  » » 18 months ago, # ^ | ← Rev. 7 →   -103 good luck
•  » » » 18 months ago, # ^ |   0 🚀 Here we gooooooo
•  » » » » 18 months ago, # ^ | ← Rev. 2 →   -23 Why?
•  » » » » » 18 months ago, # ^ |   +15 people showing there hate for recursion I guess lmao
•  » » » » » » 18 months ago, # ^ |   -13 I guess you're right.
 » 18 months ago, # |   -57 I have 2 questions: Why is there a sudden drop of average difficulty(upto problem E/F) in recent combined rounds? There are 6 problems for div.3 participants (with difficulty <1600), which used to be 3/4. To div. 1 participants (2100+), how do you feel facing a 250 rated problem in a contest, that is rated for you?
•  » » 18 months ago, # ^ |   +82 Points and difficulties have no correlation whatsoever. Difficulty is determined after the contest ends, while point values are there to give us a rough approximation of relative level of these problems. E. g. If two problems both weigh X points that means they are similar in difficulty, but that difficulty could be anything from 800 to 3500 theoretically.
 » 18 months ago, # |   +87 I am also wondering why the starting score drops from 500 to 250 in joint rounds. I kind of understand that this will make the score’s meaning more similar to div. 1. But this actually hurts the feeling of div. 2’s participants, which is a much bigger group. So I doubt if the other direction is better. I remember that 15 years ago, most OI problems had exactly 10 test data, and each data was worth 10 points, and in total each problem had exactly 100 points. Then people ask Rujia Liu, one of the most famous problem setters in China at that time: “why we have 100 points for each problem instead of 10, we can give each test data 1 point, it’s the same, right?” And Rujia said: “because people are more excited to see large numbers, and giving 100 points makes people feel more comfortable and gives people more sense of accomplishment”.I think it's the same here, right? Doubling the points of all problems (and possibly making some adjustment), you won’t change/lose anything. But people will become more excited. When solving a 3000 point problem in the contests, regardless of its difficulty, the feeling is different than solving a 1500 point problem. I definitely do not mean that we should arbitrarily increase the points of problems. But always starting from 500 seems to be reasonable.
•  » » 18 months ago, # ^ |   +113 Hacks and unsuccessful submissions are still worth the same number of points though. And if you double every one of them, we will have a 5000, 5500 and 7500 problem.
•  » » » 18 months ago, # ^ |   +84 This is an even better argument for increasing the overall point values; 50 points is a steep penalty for an incorrect submission when A is only worth 250 and might not even be worth 150 points when solved at the end of the contest.
•  » » » » 18 months ago, # ^ |   +21 It probably has more to do with emphasizing the benefit of solving harder problems. You can check the scoring distribution from the author's last round (Codeforces Global Round 11). There was a 4500 point problem while the 1500 point problem was solved by only 267 people.
•  » » 18 months ago, # ^ |   -41 I think that having 300 points for the first problem would feel a bit better than 250. It's just a more round number. Also it's more than half of 500, rather than exactly half. Not that it really matters, but this might make people feel more comfortable. Especially complete beginners, for whom the first problem might be the only solved problem during the whole contest.
•  » » » 18 months ago, # ^ |   +65 I think the number 250 is more "round" than 300.
•  » » » » 18 months ago, # ^ |   +91 256 is even rounder for contestants eyes
•  » » » » 18 months ago, # ^ |   -14 Could you elaborate on this please? 300 is rounded up to the nearest hundred. There's also a well known marketing trick to set prices to something like 299 instead of 300, because this is somehow perceived as noticeably cheaper by humans (the first digit is smaller, yay!).And once again. Looking from a total beginner perspective, a very late solver of only the first problem will only get 75 points because of decay and possible WA penalties. The leaders of the contest may get around 16k points, based on what we could see in the scoreboard of the previous contest with a similar 250-for-the-first-problem points distribution. That's more than 200 times difference. With the older 500 max points reward for the first problem, the beginners would only have around ~100 times worse score than the leaders and this smaller difference may make them feel a bit happier (or less devastated). But of course, none of this really helps them to actually get a better position in the scoreboard, it's all just an illusion.My comments had been largely inspired by the CLDP's quotation of Rujia Liu about the magic of 100 points. I think that I already said enough and have no intention to push this further.
•  » » 18 months ago, # ^ |   +132 Personally, I have never paid attention to the raw amount of points I got in a contest. I was always focused on my ranking. Maybe I'm in the minority though.
•  » » » 18 months ago, # ^ |   +17 Same here. Regarding a problem, the only number I care about is how many people solve it.
•  » » 18 months ago, # ^ |   +90 I don't see how using 250 hurts the feelings of div2 participants. Will they be happier if we multiple everything by 10?There's currently an upper limit of 6000 points per problem in the Codeforces system. You would need almost twice that if you want to keep reasonable geometric progression — which is needed to allow solving problems in a different order, and not to penalize much for failing a medium problem (but solving a hard one instead and getting less points).
•  » » » 18 months ago, # ^ |   -90 I don't see how using 250 hurts the feelings of div2 participants. As a part of optimization efforts in some company, CEO and the other higher-ups mostly kept their salaries intact, but burger-flippers got their salaries halved. We surely didn't hurt the burger-flippers' feelings, did we? Don't worry, this is just a joke. Will they be happier if we multiple everything by 10? What kind of problem have you actually tried to fix when changing the problem A score from 500 to 250 in the first place? Now this is a serious question.We got a discrepancy between 500 points in Div2 contests and 250 points in Div1+2 contests for 800-difficulty problems. If any inexperienced grey participant watched their contest score to roughly estimate their individual progress (without comparing themselves to the others), then this change affected them. But only grey participants can provide useful feedback here. Most of them are shy and afraid of downvotes.
•  » » » » 18 months ago, # ^ |   +113 What kind of problem have you actually tried to fix when changing the problem A score from 500 to 250 in the first place? I explained it in the previous comment: we needed to choose a reasonable ratio between scores of different problems. If any inexperienced grey participant watched their contest score to roughly estimate their individual progress (without comparing themselves to the others) [...] Then I hope that they read this: total points or the number of solved problems doesn't matter. Maybe you got one more problem because it was easy. Only your rank says how well you performed.I don't think it's smart to mess up problem points distribution for everybody just because some inexperienced participants focus on wrong statistics.
•  » » 18 months ago, # ^ |   +115 Very good point.I think we should also set everyone's rating to 1500. It might hurt their feelings when their rating is stuck at 1000.
•  » » » 18 months ago, # ^ |   +26 While we are at it, can I get +400 delta, I'm very hurt with my current rating.
•  » » 18 months ago, # ^ |   0 I think I've been advocating starting from 250 for a long time already. It allows for better balancing of harder problems. Even with 250pts the ratio pts/needed time is still the lowest for the easiest problems
 » 18 months ago, # |   +46 As a tester, I recommend you to read all the problems. (just check the scoring distribution).
 » 18 months ago, # |   0 As a DIV 3 user , should I participate in this round or not because I think this round will be of div1 level and I will not able to solve such hard questions.
•  » » 18 months ago, # ^ |   +22 This round will have tasks of all levels, and the round itself is "GLOBAL", which also indicates that everyone can participate, so anyone can participate and it will be interesting for him.
•  » » 18 months ago, # ^ |   +2 So, I am <1200 and I definitely will participate, because I’m absolutely sure that I’ll solve 2 problems at my worst.
 » 18 months ago, # |   +13 As a tester, I must say the quality of problems are really good, all the best and have fun :)
 » 18 months ago, # |   -8 Hope I will become expert in this round
 » 18 months ago, # | ← Rev. 2 →   -13 Why do I feel like authors are meme-ing around after looking at the score distribution ? Edit : I dont have any problem with downvotes, but I would very much like to know the reason you people are doing so. I just said what I observed, atleast I have never seen a combined round F to be only worth 1500 points.
 » 18 months ago, # |   0 Just a simple question: If after system testing, my solution still shows 'in queue' status, so will it corrected itself. Or we have to report it somewhere. Btw, when I click on more details about submission, it shows all test cases to be OK.
 » 18 months ago, # |   +4 just curious about the 250 points problem, why points didn't decrease after the first minute here ?
•  » » 18 months ago, # ^ |   +19 The points decreased per minute is proportional to its starting score. A 250 problem ends at 150? I believe (either 3/5 or 2/5 of original), so each minute it's decreasing by 100 / (total_contest_time), which was 150 for that contest. This value is less than 1, so sometimes it'll round up I guess.
 » 18 months ago, # |   +187 I'm not a tester but I like past problems created by dario2994.
•  » » 18 months ago, # ^ |   +22 Errichto You will not be disappointed :)
 » 18 months ago, # |   -37 will this round be rated.
•  » » 18 months ago, # ^ |   +4 Read the announcement :)
 » 18 months ago, # |   -20 So the reason for this scoring distribution is the same as it was in Global Round 11 ??
 » 18 months ago, # |   -34 Last time i saw a similar scoring distribution, C and D were 2000R and E was 2500R. HintIt was GR11. AlsoThe problems were nice for upsolving :)
 » 18 months ago, # |   0 250 has become fashionable, we expect 150.
•  » » 18 months ago, # ^ |   +5 I would propose that A will be worth 69 points and B 420 points. That is more fashionable.
•  » » » 18 months ago, # ^ |   -19 Support!!!
 » 18 months ago, # |   +37 As a tester, I enjoyed this round's problems. GLHF!
•  » » 18 months ago, # ^ |   0 There is some problem in the testing of problem E.For my solution: https://codeforces.com/contest/1552/submission/123763122It shows colour don't match for 3rd interval in test case 3 despite colour are the same. Please look at this and accept my solution if it is correct.
 » 18 months ago, # |   +1 It's equally sad and satisfying to read this "20 t-shirts are randomly distributed among those with ranks between 31 and 500, inclusive."
 » 18 months ago, # | ← Rev. 2 →   +63 As a tester, I would recommend you try to solve the problems in the contest.
•  » » 18 months ago, # ^ |   0 As a participant i would recommend all to upvote the above comment;)
•  » » » 18 months ago, # ^ |   +23 I upvote only after the round ends
 » 18 months ago, # |   -42 It seems that experts are going to solve the first six problems (A-F)
•  » » 18 months ago, # ^ |   +3 So much about that lol...
 » 18 months ago, # |   +71 lighthearted meme
 » 18 months ago, # | ← Rev. 2 →   -145 India won a medal in tokyo olympics . congrats!
•  » » 18 months ago, # ^ |   +18 This isn't the place to discuss these topics
•  » » 18 months ago, # ^ |   +70 When do you think competitive programming will be an official Olympic sport?
•  » » » 18 months ago, # ^ |   +34 after chess is...
 » 18 months ago, # |   0 How many problems a newbie can expect to solve?
•  » » 18 months ago, # ^ |   +42 One and game over
•  » » » 18 months ago, # ^ |   +10 Damn you bastard, you were right
 » 18 months ago, # |   +1 Good luck, guys!
 » 18 months ago, # |   +29 I bet today the new record will be written by tourist... 3800+ is coming guys...
•  » » 18 months ago, # ^ |   0 Congratulations, you've won the bet.
 » 18 months ago, # |   +4 Hardforces
 » 18 months ago, # |   +19 D.E.A.D
 » 18 months ago, # | ← Rev. 2 →   +15 Is this round meant for Div 0 participants?
•  » » 18 months ago, # ^ |   +12 No, its for Div -1 participants
 » 18 months ago, # |   +45 single problem solvers make some noise!!
 » 18 months ago, # |   0 people like me Less than 1400 rating should exit the codeforces! its not for us. Try leetcode instead zero wasted of time and actually will learn something helpful Uselessforces!
•  » » 18 months ago, # ^ |   +5 your nickname really tells alot
•  » » » 18 months ago, # ^ |   +14 It is demoralizing to see this kind of contest though. I was aiming for CM this summer and now I'm dropping to specialist, though I got top 500 rank on ARC today. I definitely think ARC C should be harder than Global Round C, yet I struggle to solve even B here, just wasted 2 hours of my time and 150 points of rating on this one. :P
 » 18 months ago, # |   +26 It seems someone put the wrong title on this contest, the title should have been "Codeforces Round #735 (Div.0)"
 » 18 months ago, # | ← Rev. 2 →   +56 Difficulty difference between A and B > length of the wall of china
 » 18 months ago, # |   +22
 » 18 months ago, # |   +16 Is this the sound of shattered dreams?
 » 18 months ago, # |   +6 C is too hard to me:(
•  » » 18 months ago, # ^ |   +16 All questions are too hard for me.
 » 18 months ago, # |   +14 there should be atleast 2 easy problem as it is a global round. maybe they can make b little bit easy :(
 » 18 months ago, # |   +27 Instead of running for gold, pupils are running for newbie and specialists are running for pupil. :)
 » 18 months ago, # | ← Rev. 2 →   +39 How on earth Tourist did first 4 questions in 8 minutes!!! I need that much time just to read those questions :( GOD LEVEL
•  » » 18 months ago, # ^ |   +15 and the last question in the next 6 minutes
 » 18 months ago, # |   +7 As the round is rated for all, they should have made two easy problems.
 » 18 months ago, # |   +7 Is the 3800-mark going to be breached?
•  » » 18 months ago, # ^ |   +3 First time we are going to see 3800 rating.
 » 18 months ago, # |   +81 Problems are good but I am trash :(
 » 18 months ago, # |   +27 I decided to take this contest with 4 hours of sleep since I wanted to hit GM today :P seems like it didn't backfire. Thank you for the nice problems, E especially was very cool. Hopefully I don't FST now and it's time to have an irrational fear of participating in contests again D:
 » 18 months ago, # |   0 There is some problem in the testing of problem E.For my solution: https://codeforces.com/contest/1552/submission/123763122It shows colour don't match for 3rd interval in test case 3 despite colour are the same. Please look at this and accept my solution if it is correct.
•  » » 18 months ago, # ^ |   0 numbers a_i and b_i should both be in i-th color. In your case a_3 and b_3 are both in 2nd color
 » 18 months ago, # |   +12 To any gray writing that this should be called Div. 0: you don't even know what solving the first problem in Div. 1 means. Who the fuck are you to judge the difficulty besides saying "this is too hard for Div. 2"?
•  » » 18 months ago, # ^ |   +2 Said an unrated user.
•  » » » 18 months ago, # ^ |   0 dude, alt...
 » 18 months ago, # |   +1 man how the hell the 5th test case in D is YES there's no 3 numbers that can produce one of them I tried everything but I suck
•  » » 18 months ago, # ^ |   0 try this 174+(-171) = 250+100.
 » 18 months ago, # |   +1 Problem 407B - Long Path is very similar to problem F, especially main observation.
 » 18 months ago, # |   +31 Why did none of the testers question this difficulty gradient?
 » 18 months ago, # |   0 Problem F saved me from going back to cyan :)
 » 18 months ago, # |   +10 Is problem D just try 10! combinations? I am kinda afraid of system tests.
•  » » 18 months ago, # ^ |   0 Gotta admire the confidence!!
 » 18 months ago, # |   +47 Doing typing practice for 2 hours and 45 minutes would have helped my coding career more than giving this round!
 » 18 months ago, # |   +3 I got my worst rank :(
 » 18 months ago, # |   +60 Somehow I found F and D easier than B. Also RIP rating.
•  » » 18 months ago, # ^ |   0 How to solve D? Got wa on pretest 2
•  » » » 18 months ago, # ^ |   +4 There mush exist some i such that a[i] = sum(x*a[j]) for all 1<=j<=n and i!=j and -1<=x<=1
•  » » » 18 months ago, # ^ |   +17 It is enough to check if there are two disjoint non-empty subsets that have the same sum
•  » » » 18 months ago, # ^ |   0 The constraints are really small for n, so you can use bitmasks to represent the subsets and check if an element outside of this subset can be represented in terms of addition and subtraction of the elements in the subset.
 » 18 months ago, # |   +46 The most pretests I have seen
 » 18 months ago, # |   +7 Can someone explain the approach to B?
•  » » 18 months ago, # ^ |   0 Sort then check if a[0] is the winner.
•  » » » 18 months ago, # ^ |   0 Can you explain a little bit more how this will work?
•  » » » 18 months ago, # ^ | ← Rev. 2 →   +3 Sounds intuitive, but how do you precisely sort the atheletes and why does it actually work?
•  » » » » 18 months ago, # ^ |   0 sort with custom function. if a won >=3 rounds then true otherwise false.
•  » » » » » 18 months ago, # ^ |   0 This won't work exactly ig as this comparator doesen't imply transitivity. For ex,if A is superior to B and B is superior to C then we can't conclude that A is superior to C since something like below can be the results for the 5 races (A>B here means that A outperformed B in this race): A>B>C, A>B>C, C>A>B, C>A>B, B>C>A. Hence,a better strategy would be to first compare player 1 to 2,then the superior of them to 3,then superior of them to 4 and so on till player n. The remaining player will be the only candidate for gold,so just compare this player with all other players again to check whether it is indeed a valid answer.
•  » » » » 18 months ago, # ^ |   +1 I used a comparator function for B 123741857
•  » » 18 months ago, # ^ |   -44 The key observation is, that if a>b and b>c, then a>c. So sort and check if first beats all.
•  » » » 18 months ago, # ^ | ← Rev. 2 →   +9 It's not true, is it?a > b and b > c but c > a310 10 20 30 3020 20 30 10 1030 30 10 20 20
•  » » » » 18 months ago, # ^ |   0 :/ Maybe that's why I needed 9 submission and 2:36h. What a sic problem.
•  » » 18 months ago, # ^ |   +12 Assume the curr_winner is 0th participant. Now, iterate through all the remaining participants. If, the winner is superior to the ith participant, we are fine, otherwise, change winner as ith participant ( because i defeats curr_winner ) and continue checking till the end.Once done, we have a candidate for winner. We just need to iterate again through all remaining participants and ensure that he defeats everyone ( and there is not a cycle in which case return -1 )
•  » » 18 months ago, # ^ |   0 start comparing the first athlete with other athletes if he is superior then all of those who got compared to him are definitely not and if he's not superior to the current athlete being compared then this current athlete could be the one so start comparing from this athlete with the next athletes if you compare him with the previous athletes it will TLE so keep doing that until you have one possible athlete now compare him to all the others if he is superior then answer is that athlete if not there's no answer
•  » » 18 months ago, # ^ |   +3 Only one overall winner is possible. If an athlete is not superior to any other athlete, he cannot be the winner. Suppose prev[i] is the best choice for first i athletes, then prev[i+1] will be i+1 if i+1 is superior to prev[i] or prev[i+1]=prev[i] if prev[i] is superior to i+1. prev[1]=1. Now you just need to check whether prev[n] is superior to all.
•  » » 18 months ago, # ^ |   0 Compare No.(i) person with No.(i+1) person.(1<=i
•  » » 18 months ago, # ^ |   +5 Notice that for any two athletes a and b, either a is superior or b is superior. Since our goal is to have an athlete that is superior to all others, every time we compare any two athletes, we can remove the 'not superior' athlete from our list of candidates.So we can perform n-1 comparisons and have exactly 1 candidate left. Now, we can check if this candidate is superior to all others. If not, then there are no more candidates so we print -1. Otherwise, this candidate is our answer.
•  » » 18 months ago, # ^ |   0 Apply two pointer's approach, take initially l as 0 and r as n-1 now compare between them if l is winner,it means r is eliminated hence decrement r. and vice-versa, finally you will get the ans as l ,check whether l is the real winner or not
•  » » 18 months ago, # ^ |   0 My approach: Iterate through all the players and in each iteration compare two-player and eliminate one player, the one with fewer wins. first player 1 vs 2, second, winner of (1 vs 2) vs 3, and so on.So after a complete iteration, only one player will remain. Now just need to check if he is better than all others or not. So one more iteration through all other players and Check if the candidate won 3 or more previous games with all others or not.
 » 18 months ago, # |   +12 This contest made me realise again that you know nothing and you are stil a beginner who is meant to struggle .
 » 18 months ago, # |   +79 Getting WA on pretest 127 is something new.
•  » » 18 months ago, # ^ |   0 it's the opposite of last round I guess.
 » 18 months ago, # |   +98 According to the standings (i.e. tourist), I believed that Problem I had appeared somewhere. Any links?
•  » » 18 months ago, # ^ | ← Rev. 3 →   +71 It's a typical PQ Tree problem.https://codeforces.com/contest/243/problem/Ehttps://onlinejudge.org/contests/278-f2e8ebbf/problemset.pdf Rujia Liu Contest 3 G (which is exactly the same)Problem M from PreFinals Moscow Workshops 2019 Day 4, Division A: Moscow SU Red Panda Contest.
•  » » » 18 months ago, # ^ |   +32 Tourist actually gave two lectures at this 2019 Moscow Workshops camp (one was on Dominator Trees)! Congrats on the win today!
•  » » 18 months ago, # ^ | ← Rev. 2 →   +7 Sadly yes https://codeforces.com/contest/243/problem/E (and also somewhere else that we still don't know). Of course, we didn't know about it (even though I was a participant in that contest many years ago).
•  » » » 18 months ago, # ^ |   0 Was it intended as a hard data structure problem or a thinking problem where you need some good idea(s) and implementation is something any red should know?
•  » » » » 18 months ago, # ^ | ← Rev. 2 →   0 It was intended as a hard problem with a long implementation. No datastructure whatsoever.Noone who saw the problem said the word "PQ-tree" and I still have no idea of what a PQ-tree is (but I guess I will discover it in the next few days).
•  » » » » » 18 months ago, # ^ |   +94 Probably you reinvented PQ-tree by yourself. XD
•  » » 18 months ago, # ^ |   +81 Lmao copypaste PQ tree = free rating (Same problem was in Ptz Winter 2013)
•  » » » 18 months ago, # ^ |   +3 Do you have some sort of archive with Ptz contests?
•  » » » » 18 months ago, # ^ |   +3 I just downloaded model solution from opentrains.
•  » » 18 months ago, # ^ |   +22 I had also done this problem previously (unfortunately I wasn't able to find it during the contest ...).
 » 18 months ago, # |   +1 Eagerly waiting to ask this..... How to solve B?
•  » » 18 months ago, # ^ |   +19 Simulate any type of tournament (for example, a well-known tournament tree) and then check that the winner of the tournament (if such exists) is actually the answer (make an additional comparison of him with all of the other participants).
•  » » » 18 months ago, # ^ |   0 Actually just compare the $i^{th}$ and $j^{th}$ works fine. XD
•  » » 18 months ago, # ^ | ← Rev. 3 →   +8 Let's define a directed graph over the players, an edge exists from player $u$ to player $v$ if player $u$ defeats player $v$. It seems like the problem is similar to finding whether or not the directed graph has a universal sink (in-degree = n — 1, out-degree = 0). To find it, let's assume the first node is the sink, and for each next node, check whether it defeats the current sink. If it does, set it as the new sink, otherwise continue. Finally, there are two cases. Either we have found the sink, or there doesn't exist any. We can check this by testing whether it defeats every other player or not.Here is the classic problem: Problem 22.1-6
•  » » 18 months ago, # ^ |   +16 start out with a set of $n$ possible winners and at each step compare two possible winners, and discard on of them as a possible winner. At the end check if the only candidate is in fact a winner.
•  » » 18 months ago, # ^ |   +14 I probably had the dumbest solution to B in the contest.I looped subsets of 3 contests, then sorted by how well the contestants did in the first, and looped in this sorted order, maintaining in a set pairs of how contestants seen so far did in the second and third contest of the subset.This way, we can check in $\mathcal{O}(\log n)$ time if the person lost to someone in every contest in the submask. If they did, they cannot be the gold medalist. If someone could still be the gold medalist after handling all submasks, they are the gold medalist.Code: 123735962
•  » » » 18 months ago, # ^ | ← Rev. 2 →   +23 No it's me :) The graph is a tournament, and hamilton path exists. I computed the hamilton path in $O(n \log n)$ and checked if the start of the path satisfies the condition. Most of the code was, again, copypasted from Nine Judges problem by tourist. (I took 9 minutes to solve the problem, but most of the time was realizing that I made a mistake copy-pasting samples)
•  » » » » 18 months ago, # ^ |   0 Another dumb solution: take random player, remove everyone with worse results, repeat until you have only 1000 contestants. Then solve in O(n^2)Code
 » 18 months ago, # |   +110 BEST CONTEST EVER FOR ME GUYS. I GOT 200 RATING CHANGE FOR THE FIRST TIME Do not click this.in negative.
•  » » 18 months ago, # ^ |   0 What a coincidence! Me too
•  » » » 18 months ago, # ^ |   +6 Me too
•  » » » » 18 months ago, # ^ |   0 Me too
•  » » 18 months ago, # ^ |   +118 When you get -200 rating but your contribution increases by +2 due to that.
•  » » 18 months ago, # ^ |   0 Looks like I'll only lose 130, not so bad then
•  » » » 18 months ago, # ^ |   +17 200>130. I win.
•  » » » » 18 months ago, # ^ |   0
•  » » » » » 18 months ago, # ^ |   +5 Does that mean I'm one step closer to becoming a Master?
•  » » » » » » 18 months ago, # ^ |   +1 Failure ia the key of winning.
 » 18 months ago, # |   +8 2.45 hours successfully wasted.T_T
 » 18 months ago, # |   -19 Why O(n^2) was giving TLE in problem B :(
•  » » 18 months ago, # ^ |   +3 50000^2 = 2500000000 = O(10^9)
 » 18 months ago, # |   -7 Please release the editorial ASAP! I'm trying to figure out B and C
 » 18 months ago, # | ← Rev. 2 →   +5 Is there a more general approach to D? My proof relies on a graph with n edges on n vertices having a cycle, but I was also thinking of viewing the problem as a linear system on $n-1$ variables and $n$ equations where you select some summands of the $n-1$ values $c_i$ where $c_i = b_i-b_{1}$ that you want to equal each $a_i$, and for each system you want to check if it is solvable.
 » 18 months ago, # |   +52 small-N forces :(
•  » » 18 months ago, # ^ |   0 bruteforces
 » 18 months ago, # |   -17 Really liked problem B.
 » 18 months ago, # |   +46 I don't know how to solve E... so disappointed with myself
 » 18 months ago, # |   +118 Am I the only one who found B unusually hard? :)
•  » » 18 months ago, # ^ |   +1 I couldn't manage to find any observation, so solved it using BIT lmao. Submission: 123734224
•  » » » 18 months ago, # ^ |   +3 Well, it's still much better than nothing... In my case, all I did when thinking at B was to really question my problem-solving skills
 » 18 months ago, # |   +33 So I sat down to give Global Codeforces contest this night, Reached Specialist last round my confidence was at its height.Solved A like it was a piece of cake, Only If I knew it was a bait for me to take.Spent more than an hour thinking how to solve B, Couldn't find a solution I cried dario2994 have pity.Then I committed a mistake of looking at the standings, Tourist solved all problems with 1 hour remaining.Accepting my fate and leaving the contest like a bad memory of past, Waiting for Secondthread to show us the way through his screencast.
 » 18 months ago, # |   +257
 » 18 months ago, # |   0 Although 10k people passed problem B, I think it is the most difficult one(which I spent most of time thinking in different aspects QAQ).And the difficulty between C, D or E, F seems too werid since I saw lots of people passed the later one.Howerver, the problems are great(easy to understand and need some thinking). Nice job!
•  » » 18 months ago, # ^ |   +1 I think you looked wrongly. Only 4.6k people solved B during the contest. Which is a bit on the low judging the other globals (8k on global round 14, 6k on global round 13, 12k on good bye 2020). Though, as someone who had 2 hours for C and D and didn't figure out either of them I'm quite confused what skill I am missing.
 » 18 months ago, # |   +4 B is probably the most difficult problem with only 500 points to score .For some ,it was a decent contest, and for others it was a nightmare .
 » 18 months ago, # |   +29 Is point depreciation at the same rate as other contests despite lower point values? It certainly felt like the point values dropped rapidly during the contest.
 » 18 months ago, # |   +3 What is the solution for E?
•  » » 18 months ago, # ^ | ← Rev. 2 →   +8 get all the intervals, sort ascending from right point, keep track of the visited colors as the first interval must be color 1, second interval must be color 2, .... then just check if adding the current color will invalidate the n/(k-1) max condition or not, if it's ok to add it, add it to the answer and break once the answer size is n. my solution: https://codeforces.com/contest/1552/submission/123762454
 » 18 months ago, # |   +4 humph I got MLE on problem B after system testso_Othis is a first
•  » » 18 months ago, # ^ |   +4 atleast you got pretests passed . I got TLE on pretest 2 and WA and 3. R.I.P rating
•  » » 18 months ago, # ^ |   +20
 » 18 months ago, # | ← Rev. 2 →   -32 How to solve C?
 » 18 months ago, # |   +283
 » 18 months ago, # |   +6 How to solve D ?
 » 18 months ago, # |   0 Did anybody solve B using the randomization optimization mentioned in the hint in the editorial?
 » 18 months ago, # | ← Rev. 2 →   +15 oops, so strict time for main tests of problem D. Correct algorithm got TLE on test 21 when code JAVA ???
•  » » 18 months ago, # ^ |   +8 Hope can increase a liitle bit time limit. Or is there any algo that can pass with Java?
 » 18 months ago, # |   +27 Didn't come up with B solution, so implemented $O(n ^ 2)$. Adding shuffle before it makes solution run in 93ms 123733948
•  » » 18 months ago, # ^ |   +24 That's also what I did! B was so hard for me.
•  » » 18 months ago, # ^ |   +5 May you explain why it would run much faster?
•  » » 18 months ago, # ^ |   0 After seeing your comment, I tried with with random_shuffle it was giving TLE on TC 43 and then tried with shuffle you used, it passed in 77 msCan you please tell me was this luck or is there huge difference in implementation of both shufflehttps://codeforces.com/contest/1552/submission/123771261 (random_shuffle)
•  » » » 18 months ago, # ^ |   +1 random_shuffle by default uses rand(), which is not very random on certain architecture such as Codeforces's machines. You can refer to this blog.
•  » » » » 18 months ago, # ^ |   0 Actually it's not very random in most if not all architectures. There is a whole presentation talking about it here (i think it is pretty cool and recomend it c:)
•  » » » » 18 months ago, # ^ |   0 you mean using random_shuffle didn't shuffle much. Many values were at their original position even after shuffling right ?
•  » » » » » 18 months ago, # ^ |   +1 yes
•  » » » » » » 18 months ago, # ^ |   0 Hi I am not much used to random no. generators,but i tried to generate a random array for D. But no matter how many repetitions i gave (upto 10^5), 5th test case of sample test always gave 'NO' as an answer. Is there any specific reason to why its not working there / where will such randomness work ? PS: I was using uniform distribution bw lets say (4*min_element to 4*max-element).
 » 18 months ago, # | ← Rev. 2 →   +2 Problem B: I stored the 5 marathons information of each athlete in an array then sorted in descending order based on their superiority. after that checked if the array[0] is superior to all other. It got TLE in system test :'( Can someone please explain what went wrong?
•  » » 18 months ago, # ^ |   +2 Your comparator is just way too slow. I changed it a bit. 123770117
•  » » 18 months ago, # ^ |   0 You can't sort them based on superiority using std::sort. There may be testcases where athlete A has beaten B, B has beaten C and C has beaten A. But this breaks the transitivity requirement. You can find more information here: https://codeforces.com/blog/entry/72525 A: 9 9 2 1 1 B: 1 1 3 3 3 C: 4 4 1 9 9 
•  » » » 18 months ago, # ^ |   0 The funny thing is that it in spite of this still works. The sort function seems to not throw an exception (at least not in the given testcases).
•  » » » » 18 months ago, # ^ |   0 It's undefined behaviour, so anything may happen. For example, someone from stackoverflow complained about a segfault. And I'm pretty sure that it's possible to uphack the modified submission from another comment by feeding a specifically crafted input to it.
•  » » » » 18 months ago, # ^ |   0 I think it works since if you use merge sort to sort the players with respect to the given comparator,then in the implementation of the algorithm, every player other than a[0] was actually proved to be inferior to someone. Hence,the only possible candidate for gold is a[0]. All this is of course, assuming that merge sort is followed.
 » 18 months ago, # |   +24 I unfortunately wasn't able to take part in the contest officially, but I looked at the problemset and the problems I read were consistently inspiring. Congratulations, and thank you, for setting such a fantastic round!
 » 18 months ago, # |   0 Great Round, Thanks!
 » 18 months ago, # | ← Rev. 2 →   +12 For problem D, I used brute force approach to check if I can write an element of the given array as (sum of some elements) — (sum of some other elements). For that I made all the possible strings of length n-1 having '0', '1', '2'. If the character is '0', I am not using it, else if it's '1' I'm adding it, otherwise I'm subtracting it. If the final value matches the array element, then I'm printing "YES".So the time complexity should be O(T*n*(3^(n-1))), because I'm making all the strings of length (n-1) for every element of array. And T*n*(3^(n-1))=3936600, which is approximately 4e6. I don't know why my code failed on system testing and gave tle on test 21.Please help me, finding what I'm missing. Here is my code:https://codeforces.com/contest/1552/submission/123748110
•  » » 18 months ago, # ^ |   +3 Strings and vectors are relatively slow so 4e6 times using push_back is slow!
•  » » 18 months ago, # ^ |   +6 I did the same mistake. If you look carefully calculating all the possible subset sums and finding duplicates will yield the same result because. a = b-c+d-e => a+c+e = b+d
•  » » » 18 months ago, # ^ |   +3 Thanks IloveGoodness and YPK
•  » » 18 months ago, # ^ | ← Rev. 2 →   +3 Yeah as you said the time complexity will be O(T*n*(3^(n-1)))....but as you are using the push_back opertaion....which is genrally slow....that's why you got TLE
 » 18 months ago, # |   +1 If you are already frustrated from the contest that you tried so hard but still were not able to solve. Then check this and get more frustrate :'(PS: Report this channel (I know it won't make much difference but what else we can do)
 » 18 months ago, # |   +15 when are the t-shirts winners selected? will the list be publicly available?
 » 18 months ago, # |   +5 Problem I have made contest a bit worse. Many deserving Top-10 aren't in Top-10 due to that. It is a lot unfortunate that setters and testers didn't know problem before hand.Global Rounds are supposed to be very special. Unfortunately, it turned out to be very bad for me. I'm not sure if it should be considered Unrated. (May be this are just my emotions speaking)
•  » » 18 months ago, # ^ |   0 The funny thing is that dario participated on the contest that this problem was on, so maybe he even remembered it subconciously when making up the problem (or maybe he didn't upsolve the problem and because of that he didn't know that it existed)
 » 18 months ago, # |   +6 I am feeling terribly dumb after this round :)
 » 18 months ago, # |   +11 Congratulations to tourist for getting such a high rating at 3821 and to be the first reaching 3800!!!!!
•  » » 18 months ago, # ^ |   +11 I wonder how many t-shirts he has had from all these global rounds and competitions...
•  » » » 18 months ago, # ^ |   +3 enough to open an online store lmao
 » 18 months ago, # | ← Rev. 2 →   +8 2 problem is similar to find the celebrity problem which can be done using recursion https://www.geeksforgeeks.org/the-celebrity-problem/
 » 18 months ago, # |   +41 MikeMirzayanov a new color and naming should appear "Nutella Instinct" for example, DBZ fans gonna like this
 » 18 months ago, # |   +3 I wonder when would I become good enough to solve problem B, it's been 2 times in a row that I've not been able to solve problem B.
•  » » 18 months ago, # ^ |   +5 Hey man. I'd just like to say that there's bad days and good days, and brooding over the bad days is just a waste of time. Cheer up, watch a stand-up special or something, and practice! Good luck. (felt obliged to write this because it was a bad day for me as well).
•  » » » 18 months ago, # ^ |   +4 Sure thing! I hope you'll get back to CM soon
•  » » » » 18 months ago, # ^ |   +2 Thank you! Come join me there ;)
•  » » » » » 18 months ago, # ^ |   +4 will try my best! :)
 » 18 months ago, # |   +10 I wrote (i<
 » 18 months ago, # |   +13 still 2800+ pog (but probably not after removing 2000 cheaters)
 » 18 months ago, # | ← Rev. 5 →   -29 Too low rating allocated to the first-ever contest!!I solved 2 problems in this contest and my Rank was around 4.8k, but the rating allowed to me was 490 which is Highly Demotivating. Where I can see profiles with ratings starting from 1400 even when they get some 9-10k ranking this is something which shouldn't, It will take a long time for me now to even reach specialist when half of my college does.If it's the case then everyone's rating has to start from 0 then and also by default they show maxrating which is even more misleading if ones rating is starting from 1400 and ones 0
•  » » 18 months ago, # ^ |   0 Your rating will be higher than these users with the lapse of time.So don't worry lol
 » 18 months ago, # |   0 i made submission for sequence permutation. My solution was accepted and also it is matching with tutorial implementation but out of 250 i got only 162.Can anyone please tell where my score was deducted.
•  » » 18 months ago, # ^ |   0 ye codechef nahi hai
 » 18 months ago, # |   +3 Hard, yet interesting!
 » 18 months ago, # | ← Rev. 2 →   0 123760576 (Problem D) Can somebody pls help me out in this why i got wrong on test 15 , i searched the ranklist, and i didn't find anyone with the same test getting wrong .
•  » » 18 months ago, # ^ |   0 I just did some modification to your code and it got accepted 123814544 Check this one out !
•  » » » 18 months ago, # ^ |   0 I know bro , even i commented out few things and it got accepted. But i am not able to figure out why those conditions were wrong.
 » 18 months ago, # |   +41
 » 18 months ago, # |   +18 I liked the contest. Hope to find more contest by same authors
 » 18 months ago, # |   0 Nyaan Can you Explain your Problem D solution?
 » 18 months ago, # | ← Rev. 3 →   +5 Seems like sansen is hacking everyone's G and most of them are failing with TLE, does that mean the system tests were weak? Sorry if I'm getting this wrong
 » 18 months ago, # |   0 Does anyone know who should I contact to if i had issue of receiving T-shirt prize in previous contest?
 » 18 months ago, # |   +5 Hack it plz! 124202906
•  » » 18 months ago, # ^ |   +5 Give the test, and i'll hack you!
•  » » » 18 months ago, # ^ |   0 If I had one I'd hack myself.
•  » » » » 18 months ago, # ^ |   -8 Hmmmm... So are you sure that there is a bug in your solution that can be hacked?
•  » » » » » 18 months ago, # ^ | ← Rev. 2 →   0 That solution is genuinely shit — I'm picking a set to query but then querying a different set that I know to fail in at least one possible case. There's no reason why it should always work, in fact even less than for a random set.UPD: I realised I thought stupid thoughts and it might be actually correct. No idea.
 » 17 months ago, # |   +10 where is list of T-shirt winners ?
»
17 months ago, # |
+42

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 1552 1 tourist
2 1552 2 ksun48
3 1552 3 Benq
4 1552 4 Petr
7 1552 7 sunset
8 1552 8 Um_nik
9 1552 9 ko_osaga
10 1552 10 dreamoon_love_AA
11 1552 11 244mhq
13 1552 13 lumibons
14 1552 14 hos.lyric
15 1552 15 Egor
16 1552 16 kotamanegi
17 1552 17 Temotoloraia
18 1552 18 aid
19 1552 19 TLEwpdus
20 1552 20 renascencepjw0510
21 1552 21 gisp_zjz
22 1552 22 LayCurse
23 1552 23 duality
24 1552 24 scott_wu
25 1552 25 DmitryGrigorev
26 1552 26 Subconscious
27 1552 27 nuip
28 1552 28 tatyam
29 1552 29 jiangly_fan
30 1552 30 353cerega
45 1552 45 kotatsugame
62 1552 62 Maksim1744
66 1552 66 tute7627
92 1552 91 sugarrr
120 1552 120 dlalswp25
134 1552 134 torisasami
136 1552 136 MooNight
157 1552 156 Onjo
203 1552 203 TrivialMan
220 1552 220 chaeyihwan
231 1552 231 yao11617
274 1552 274 new_acc_
278 1552 278 Utkarsh.25dec
304 1552 304 Serval
317 1552 317 titia