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, malachi_toney_goat, 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.
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!
Time to upsolve global round 11.
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
When my contribution exceeds a hundred, I will make an stream with an analysis of the 11th global round !!!
Good luck, sir :)
Good luck.
ivanz Hey! any plans for the stream? you have crossed 100
True!!!
True!
So I hate posting comments
So you thought people will read this comment and just hit the upvote button as well?
Your comment falls into fun category. Take my upvote!
Can we say "All hail our emperor Anton" here? :)
I'm a simple man. I see anton, I take part.
People be like: I'm a simple man. I see T1dus, I downvote.
Imagine banning someone for a ping
Imagine that ping being mulitplied 20 times as much.
So we will have 3hrs or 2:30? Cuz on the contest table it says that it lasts 2:30hrs. Thx;)
I guess it's 2:30 as per the contests table
Already fixed at 2: 45
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.
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.
bruh you are indirectly promoting that, better we talk less about it and more focus on learning from the round by participationg
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.
don't cry about it, just solve more problems than the distributor.
Just be faster, most cheaters take a long time to do even A, genuine coders can easily outpace them.
To perform better, should i solve the author's previous contests? Please give me some suggestions as i am a newbie.
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
warm and fuzzy feeling! you mean pain!!
Lol no wonder why a grandmaster gains satisfaction from solving all problems:)
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..
My first global round, exited to see the problems and maybe cry afterwards :)
So "exited" that you wrote "exited" instead of excited.
lol didn't notice that :) hahaha
good luck
🚀 Here we gooooooo
Why?
people showing there hate for recursion I guess lmao
I guess you're right.
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?
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.
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.
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.
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.
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.
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.
I think the number 250 is more "round" than 300.
256 is even rounder for contestants eyes
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.
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.
Same here. Regarding a problem, the only number I care about is how many people solve it.
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).
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.
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.
I explained it in the previous comment: we needed to choose a reasonable ratio between scores of different problems.
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.
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.
While we are at it, can I get +400 delta, I'm very hurt with my current rating.
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
As a tester, I recommend you to read all the problems. (just check the scoring distribution).
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.
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.
So, I am <1200 and I definitely will participate, because I’m absolutely sure that I’ll solve 2 problems at my worst.
As a tester, I must say the quality of problems are really good, all the best and have fun :)
Hope I will become expert in this round
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.
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.
just curious about the 250 points problem, why points didn't decrease after the first minute here ?
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.
I'm not a tester but I like past problems created by dario2994.
Errichto You will not be disappointed :)
will this round be rated.
Read the announcement :)
So the reason for this scoring distribution is the same as it was in Global Round 11 ??
Last time i saw a similar scoring distribution, C and D were 2000R and E was 2500R.
It was GR11.
The problems were nice for upsolving :)
250 has become fashionable, we expect 150.
I would propose that A will be worth 69 points and B 420 points. That is more fashionable.
Support!!!
As a tester, I enjoyed this round's problems. GLHF!
There is some problem in the testing of problem E.
For my solution: https://mirror.codeforces.com/contest/1552/submission/123763122
It 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.
It's equally sad and satisfying to read this "20 t-shirts are randomly distributed among those with ranks between 31 and 500, inclusive."
As a tester, I would recommend you try to solve the problems in the contest.
As a participant i would recommend all to upvote the above comment;)
I upvote only after the round ends
It seems that experts are going to solve the first six problems (A-F)
So much about that lol...
India won a medal in tokyo olympics . congrats!
This isn't the place to discuss these topics
When do you think competitive programming will be an official Olympic sport?
after chess is...
How many problems a newbie can expect to solve?
One and game over
Damn you bastard, you were right
Good luck, guys!
I bet today the new record will be written by tourist... 3800+ is coming guys...
Congratulations, you've won the bet.
Hardforces
D.E.A.D
Is this round meant for Div 0 participants?
No, its for Div -1 participants
single problem solvers make some noise!!
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!
your nickname really tells alot
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
It seems someone put the wrong title on this contest, the title should have been "Codeforces Round #735 (Div.0)"
Difficulty difference between A and B > length of the wall of china
Is this the sound of shattered dreams?
C is too hard to me:(
All questions are too hard for me.
there should be atleast 2 easy problem as it is a global round. maybe they can make b little bit easy :(
Instead of running for gold, pupils are running for newbie and specialists are running for pupil. :)
How on earth Tourist did first 4 questions in 8 minutes!!! I need that much time just to read those questions :( GOD LEVEL
and the last question in the next 6 minutes
As the round is rated for all, they should have made two easy problems.
Is the 3800-mark going to be breached?
First time we are going to see 3800 rating.
Problems are good but I am trash :(
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:
There is some problem in the testing of problem E.
For my solution: https://mirror.codeforces.com/contest/1552/submission/123763122
It 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.
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
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"?
Said an unrated user.
dude, alt...
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
try this 174+(-171) = 250+100.
Problem 407B - Long Path is very similar to problem F, especially main observation.
Why did none of the testers question this difficulty gradient?
Problem F saved me from going back to cyan :)
Is problem D just try 10! combinations? I am kinda afraid of system tests.
Gotta admire the confidence!!
Doing typing practice for 2 hours and 45 minutes would have helped my coding career more than giving this round!
I got my worst rank :(
Somehow I found F and D easier than B. Also RIP rating.
How to solve D? Got wa on pretest 2
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
It is enough to check if there are two disjoint non-empty subsets that have the same sum
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.
The most pretests I have seen
Can someone explain the approach to B?
Sort then check if a[0] is the winner.
Can you explain a little bit more how this will work?
Sounds intuitive, but how do you precisely sort the atheletes and why does it actually work?
sort with custom function. if a won >=3 rounds then true otherwise false.
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.
I used a comparator function for B 123741857
The key observation is, that if a>b and b>c, then a>c. So sort and check if first beats all.
It's not true, is it?
a > b and b > c but c > a
3
10 10 20 30 30
20 20 30 10 10
30 30 10 20 20
:/ Maybe that's why I needed 9 submission and 2:36h. What a sic problem.
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 )
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
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.
Compare No.(i) person with No.(i+1) person.(1<=i<i+1<=n)
If No.(i) person is lose,it illustrates that No.(i) person is not the champion (since he loses at least 1 round.)and No.(i+1) person will continue to compare with next person and vise versa.
After n-1 round comparation,you can get a person who is the candidate champion and he should compare with other persons to judge whether he is the real champion.
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.
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
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.
This contest made me realise again that you know nothing and you are stil a beginner who is meant to struggle .
Getting WA on pretest 127 is something new.
it's the opposite of last round I guess.
According to the standings (i.e. tourist), I believed that Problem I had appeared somewhere. Any links?
It's a typical PQ Tree problem.
https://mirror.codeforces.com/contest/243/problem/E
https://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.
Tourist actually gave two lectures at this 2019 Moscow Workshops camp (one was on Dominator Trees)! Congrats on the win today!
Sadly yes https://mirror.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).
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?
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).
Probably you reinvented PQ-tree by yourself. XD
Lmao copypaste PQ tree = free rating (Same problem was in Ptz Winter 2013)
Do you have some sort of archive with Ptz contests?
I just downloaded model solution from opentrains.
I had also done this problem previously (unfortunately I wasn't able to find it during the contest ...).
Eagerly waiting to ask this..... How to solve B?
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).
Actually just compare the $$$i^{th}$$$ and $$$j^{th}$$$ works fine. XD
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
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.
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
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)
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
BEST CONTEST EVER FOR ME GUYS. I GOT 200 RATING CHANGE FOR THE FIRST TIME
in negative.
What a coincidence! Me too
Me too
Me too
When you get -200 rating but your contribution increases by +2 due to that.
Looks like I'll only lose 130, not so bad then
200>130. I win.
Check this
Does that mean I'm one step closer to becoming a Master?
Failure ia the key of winning.
2.45 hours successfully wasted.T_T
Why O(n^2) was giving TLE in problem B :(
50000^2 = 2500000000 = O(10^9)
Please release the editorial ASAP! I'm trying to figure out B and C
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.
small-N forces :(
bruteforces
Really liked problem B.
I don't know how to solve E... so disappointed with myself
Am I the only one who found B unusually hard? :)
I couldn't manage to find any observation, so solved it using BIT lmao. Submission: 123734224
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
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.
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!
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.
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 .
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.
What is the solution for E?
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://mirror.codeforces.com/contest/1552/submission/123762454
humph I got MLE on problem B after system tests
o_O
this is a first
atleast you got pretests passed . I got TLE on pretest 2 and WA and 3. R.I.P rating
https://mirror.codeforces.com/blog/entry/70237#comment-750933
How to solve C?
How to solve D ?
Did anybody solve B using the randomization optimization mentioned in the hint in the editorial?
oops, so strict time for main tests of problem D. Correct algorithm got TLE on test 21 when code JAVA ???
Hope can increase a liitle bit time limit. Or is there any algo that can pass with Java?
Didn't come up with B solution, so implemented $$$O(n ^ 2)$$$. Adding shuffle before it makes solution run in 93ms 123733948
That's also what I did! B was so hard for me.
May you explain why it would run much faster?
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 ms
Can you please tell me was this luck or is there huge difference in implementation of both shuffle
https://mirror.codeforces.com/contest/1552/submission/123771484
https://mirror.codeforces.com/contest/1552/submission/123771261 (random_shuffle)
random_shuffleby default usesrand(), which is not very random on certain architecture such as Codeforces's machines. You can refer to this blog.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:)
you mean using random_shuffle didn't shuffle much. Many values were at their original position even after shuffling right ?
yes
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).
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?
my submission
Your comparator is just way too slow. I changed it a bit. 123770117
thanks!
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://mirror.codeforces.com/blog/entry/72525
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).
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.
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.
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!
Great Round, Thanks!
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://mirror.codeforces.com/contest/1552/submission/123748110
Strings and vectors are relatively slow so 4e6 times using push_back is slow!
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
Thanks IloveGoodness and YPK
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
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)
when are the t-shirts winners selected? will the list be publicly available?
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)
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)
I am feeling terribly dumb after this round :)
Congratulations to tourist for getting such a high rating at 3821 and to be the first reaching 3800!!!!!
I wonder how many t-shirts he has had from all these global rounds and competitions...
enough to open an online store lmao
2 problem is similar to find the celebrity problem which can be done using recursion https://www.geeksforgeeks.org/the-celebrity-problem/
MikeMirzayanov
a new color and naming should appear
"Nutella Instinct" for example,
DBZ fans gonna like this
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.
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).
Sure thing! I hope you'll get back to CM soon
Thank you! Come join me there ;)
will try my best! :)
I wrote (i<<j) instead of (1<<j) and it passed pretests(failed system test). What a blunder.
still 2800+ pog (but probably not after removing 2000 cheaters)
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
Your rating will be higher than these users with the lapse of time.
So don't worry lol
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.
ye codechef nahi hai
Hard, yet interesting!
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 .
I just did some modification to your code and it got accepted 123814544 Check this one out !
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.
I liked the contest. Hope to find more contest by same authors
Nyaan Can you Explain your Problem D solution?
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
reference:
https://mirror.codeforces.com/contest/1552/hacks?verdictName=CHALLENGE_SUCCESSFUL&chosenProblemIndex=G
https://i.ibb.co/YPDkbV9/hacks-1.png
Does anyone know who should I contact to if i had issue of receiving T-shirt prize in previous contest?
Hack it plz! 124202906
Give the test, and i'll hack you!
If I had one I'd hack myself.
Hmmmm... So are you sure that there is a bug in your solution that can be hacked?
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.
where is list of T-shirt winners ?
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.