¡Buenos días! (That's Spanish for "what's up homies")
On 06.12.2020 17:35 (Московское время) we will host Codeforces Global Round 12.
It is the sixth round of a 2020 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 2020:
- 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 2020 supported the global rounds initiative!
The problems were written and prepared by smart Cuban Devil and stupid Americans fivefourthreeone and Monogon.
We would like to distribute our thanks equally to the following people who made this round possible.
- Ernestico, McDic, Ari, gamegame, namanbansal013, coderz189, balbit, dorijanlendvaj, Retired_cherry, saurabhyadavz, arvindr9, kclee2172, AliShahali1382, BRCode, ffao, Kuroni for testing the round and
roastingproviding valuable feedback to the problems. Testers orz! - antontrygubO_o for inspiration!
- isaf27 for excellent coordination of the round, and improving several problems!
- MikeMirzayanov for the amazing Codeforces and Polygon platforms!
- You, for participating! Your participation will directly contribute to the end of the long-standing Cuban-American rivalry, and will lead to peace on Earth.
You will have 3 hours to solve 8 problems (and 2 subtasks). If you want to lose rating, then we encourage you not to read all the problems.
May rating be distributed from each according to his ability, to each according to his needs!
UPD: Here's the score distribution. Good luck, have fun!
UPD: Hope you enjoyed the problems! Editorial is posted.
UPD: System testing finished, congrats to the winners!
As a tester, Communism is a good and realistic economic and political system.
As a tester I just say that the problems are very interesting!
As a tester, I agree!
Hope for a great contest :D
Allah
using the religion to get contribution!
disgusting
Monogon
Don't try
Now I see why was every problem setter/tester was mentioning Communism and Capitalism.
As a communist, Testing is a good way to contribute to competitive programming community.
As a competative programmer, help me bring Monogon up to 200 contribution too.
Greedy capitalist pig
That's inswine! Please grant me hamnesty, for I wish to be a loyal comrade...
Now that you edited your comment to request upvotes for me, the state, I will grant you hamnesty.
I'm happy to see that this tail has a twist!
It's great to see that I've been reborn into a SecondThread. Just minutes ago, I was a lowly HamString...
OMG !! You are too close to become top contributor !!
Woah, Nice flow of contribution right there. Which algo did you applied here Monogon??
Dinic with scaling orz
mission complete
As a non-tester, I wish I knew more problemsetters to contact for testing.
Make your friends to write a contest and test it
@antontrygubO_o Is there any chance you are looking for new friends?
Do you want me to make you write a contest?
I dont intend to write a whole contest. Just testing for 1 single question would be more than enough for me.
.Its a (pupil)green flag from my side.
As a reader, I enjoy reading comments!!
How to improve contribution? Negative->positive
Don't write comments like this.
Ok.
Did you actually remember his username from his 20 months old comment?!
I think he first check my all comments why I have negative contribution and then he find it. actually the comment was 9 month ago and his post was 20 months ago
I didn't understand why I am getting downvote for saying 'Ok'.
You can break the ratism curse with good memes
An announcement written 4 days before the contest -> bad contest
As a tester,
Say no more
I'm afraid I can't participate in it because I have to go back to school to have classes then :(
Since fivefourthreeone currently refuses to post here and gain contribution, please give him contribution!!
He is very orz and write problem good.
If you want to gain rating on this global round, upvote his posts!
https://codeforces.me/blog/entry/80268#comment-664350
https://codeforces.me/blog/entry/82050#comment-687962
https://codeforces.me/blog/entry/82288#comment-691417
https://codeforces.me/blog/entry/82468#comment-693597
https://codeforces.me/blog/entry/82468#comment-693602
Forced Contribution xD
Hey dude, same pinch!!!! I also keep my dp color same as that of my handle.
As a tester, give me contribution
I cannot wait for the opportunity to generously hand out rating to the needy in this upcoming Global Round!
I live to serve the community!
I appreciate it, Agnimaster
As a sole Java user myself, I appreciate YOU. :)
Why doesn't fivefourthreeone make a comment asking for contribution?
Because he doesn't have two!
"Your participation will directly contribute to the end of the long-standing Cuban-American rivalry."
You assumed there's an end :).
I actually anticipated an "As a problem setter ..." comment :(
Contribution is overrated.
Are you angry at Santa or Monogon? Why don't you and other members of your family have the santa hat on?
[deleted]
As a non-tester, give me negative contribution.
Maybe, you should change it to "As a non-tester, give me non-negative contribution". xD
May the pretests be strong!
May the problem statements be short!
May the round remain rated forever!
I thought "Buenos días" is "Good morning" — from a terrible student failing Spanish Class xD
Good Morning!
Good morning . Congrats for 200 contribution.
I think saying Congrats or Good morning is not the reason for downvote. What's wrong ?
I have observed on codeforces people downvote by seeing your handle's colour. If you would have been red then even ur single "." can give you +50 upvotes.
I beg to differ.
I think you should thank me for +75 :P, seems like thats one of the exception.
May be.just look at my comments is it the reason for getting downvote.Is under yellow are not allowed for comments?if it's false then why downvote.
.
Power of red ! +++++++++++±
Hence proved!!!!
I thought "what's up homies" in Cuba is said as "Que bola asere!"
As a tester ... ( You know what's next [^-^] )
As a participant I also want to become tester :(
Your previous comments spiked the number of testers. Now as a participant you're doomed to remain one.
This is yet to be true, if you see number of testers in Educational round and Div-3 its' still the same. I requested for increase over there. https://codeforces.me/blog/entry/84957#comment-725498
As a tester, Monogon asked me to test just so I could write a comment in this blog saying that the problems are fun.
As a setter, I can confirm that you are a tester and I forgot to update the tester list.
I feel bad for namanbansal013. He has negative contribution just because he made video editorials for some problems. Come on people, he ain't getting monetary benefits for making editorials. Neither has he posted some random shit "as a tester" comment (that doesn't make any sense) just to farm contribution in any of the rounds he tested. No tester should have negative contribution
Hope not to become expert again XD
"one person's trash is another person's treasure". I want to become an expert.
"one person's trash is another person's treasure". I want to become a pupil.
So deep.
"one person's trash is another person's treasure".
I rarely write a comment but it is really annoying that people upvotes a comment just by seeing handle's colour
*color
Improve your coding not grammer
*grammar
relax dude his colour spelling is not wrong, colour is British English whereas the color is American English.
As a tester, Monogon asked me to test just so I could write a comment in this blog saying that the problems are fun.
Monogon is one of my favourite writers :)
Its weird how newbies and pupils most of the time gets downvoted because of their comments (which I agree are really bad sometimes) but from last few contests high rated beings just commenting literally anything like "As a tester" comments and still getting upvotes.
Like once errichto said- "This comment section is shit"
Congrats Monogon on 200 contribution!!
Whatafuck!!!
I am a newbie here and haven't given many contests yet. Can someone please explain what are subtasks that are mentioned in the above post. Does that mean we will have 10 questions in total?
It means that 2 of the problems will be split into an easy version and a hard version.
Glad to see saurabhyadavz as a tester of this contest from my city.
The problems were written and prepared by smart Cuban Devil and stupid Americans fivefourthreeone and Monogon
That's harsh XD
Downvote above comment and make downvoteception when someone click it
As a cuban, I am very proud of the cuban testers and writers & after living in "communism" for long time, I just wanna say that "It sucks" :)
You can't improve if you don't participate in the contests :)
As a non-tester,I am pretty sad that I missed my chance to get contribution with saying "As a tester".
Monogon orz!
We have actually prepared 2 entirely different problem-sets. One which Errichto will surely get huge +, and the other he will surely get huge -. The one we choose will depend on whether he gives in to my demands.
7 geometry problems?
Can you make some geometry videos in your YouTube channel ?
Personally I think some of competitive programmers see the geometry as the hardest thing in CP
It should be: from each according to his ability, to each according to his work!
Hello Comrade Problem-setters. It pleases me greatly that rating redistribution will finally become a reality on Codeforces. I'd like to ask how exactly each user's need for rating will be determined.
Sincerely, Comrade Contestant Darcy
can i get some upvotes/contribution please , today is my birthday !!
Happy birthday!
Thank you so much Monogon
Will the problems be available in Spanish?
"May rating be distributed from each according to his ability, to each according to his needs!" *his or her
I guess Karl Marx was sexist.
This is the first global contest that I am going to participate in. Is a global contest harder than Div.2? Can you tell me the difference between a global round and other rounds? Also, is a global round rated for me?
Global is rated for you. Typically, Globals are harder than Div. 2 because it is combined Div 1 and 2. Globals are known for their interesting high quality problems, although I'm not sure what differentiates them from regular Div. 1 + Div. 2.
Буду рад поучаствовать
For a Chinese primary school student, the start time is too late:(
This is the usual start time on codeforces!
What if SecondThread beats both of them ;)
it will be something very awesome Errichto u must post any blog or a meme :D
Why Errichto didn't Host a single contest on Codeforces in last one year.
Why do you think the default for me is to produce a CF contest every year? It takes new ideas and a lot of time.
Yea time is a big factor . sorry. But why downvote?
Now this actually strikes chills down my spine
Are you new to Global round ? Every global round has the same length of 3 hrs and total 8 problems (or maybe more)
yes
Now all makes sense ... He's the emo spiderman.
Why don't you all memers put your shitty memes inside spoilers. Just cluttering the comments section with shit
Well, hope the problems are not too difficult for me :)
By the way, when can we see the scoring distribution?
Alright .. Maybe E is still too difficult for me, not feeling good :(
I can smell maths from here .
I hope I am not going to mess it up again.
Aye my dude, All the best <3
dude that gave me a shock!! ALL THE BEST
Never mind I did it again :clown:
Really interesting to see you were stuck at B!!!
Best weekend for tourist
No Benq deny this
For me, this round was very tough. I don't even solved B even after 3 hours :(
So I couldn't solve C1, but on the bright side, I figured out how to make a sound while breathing inwards by making monkey noises for the past 20 minutes!
I hate every contest with subtasks specially in the first 3 problems.
What is probability of a person like Me(an average mind) thinking the same puzzle in same way as a Red coder thinking randomly in his Leisure time?? is that 1/6e4 like that??
Solve F in 20 minutes Can't solve C2 or D in 2 hours.
How it works???
I think a lot of people spent time with c or d so just a small group of contestans read problems up to F
I am not sure of the system tests at the moment, but binary search worked for $$$D$$$, with just checking for $$$k = 1$$$ separately (actually I did check for the first $$$10$$$ arbitrarily). Find minimum $$$k$$$ for which the goodness holds, then all $$$k$$$'s till $$$n$$$ from this point will hold. Checking for a permutation is trivial, and sliding window minimum is also very standard.
I hope system tests pass for me.
I did find $$$C$$$ much harder than $$$D$$$ though.
Update: Accepted
Solution: 100575348
I did the same but i got runtime error on pretest 2. 100569622 Please check if you can find the error
Complexity is $$$O(n)$$$.
My solution: https://codeforces.me/contest/1450/submission/100569194
This is really tough problemset :|
I agree, master Anus.
How to solve C2?
First, split the matrix on three groups:
where
group[i][j]=(i+j)%3Then choose such two different groups where number of 'O' in the first group + number of 'X' in the second group <= k/3. Such pair of groups always exists. Finally, in the first group all 'O' replace by 'X' and in the second group all 'X' replace by 'O'
I took all masks 1 <= mask <= 6(not all 0 and not all 1) and decided for each remainder MOD 3 of (i + j) what I want it to be(X or O). I simply computed how many cells I need to change and if it's enough, output. This doesn't always find solution and u can prove it by simple math. I didn't figure out that you could ignore one remainder. Oh well
Seriously now, who decides the difficulty for these contests?
Apparently the difficulty permutation has quite a high cost.
Am I the only one who thinks problems like F are not very interesting? They are very guessable (I was very disappointed to find out that my random hunch about what the answer might be was entirely correct) and reduce to a small number of pretty typical greedy arguments. Although it is an ad-hoc problem (which can be promising), it still is not a very interesting problem to solve.
What's your "easily guessable" hunch? I spent like at least half an hour in contest thinking of all the ways to get rid of dominant segment endings, before realising that most of them were no better than shoving them somewhere inside another segment and forgetting about them.
well i think it shouldnt be the F problem. and also yes i think the hard part of the solution was to actually build the answer. if the problem wants the actual permutation it could be nice problem for F in my opinion.
I don't know, that might be a quite painful implementation. But it would definitely redeem the guessability (and maybe the problem).
I Hate the
Tic-Tac-Toe gridUPD: after see the editorial., i understood that was a good learning problem. but c & d can be replace their place.
Interesting problem set, but I solved C1 and C2 in a very similar way to this problem
I thought of that problem but could't find the relation, can you elaborate?
Sure! In the other problem, you increase the numbers based on the parity of the sum i + j. In C1, you can do the same, but only for positions (i, j) that have (i + j) % 3 = 0. This does work, but sometimes can go over k / 3. So you can check all remainders and try to flip all position (i, j) that have (i + j) % 3 = r. C2 is very similar, I'll let you figure it out.
Thanks, the editorial is also out and I can understand the relation now.
Thanks for the reference, I also remember the similar problem but could not find it.
C1 and C2 spoiled this contest for me :-(
What the hell was up with this problem $$$C$$$ this time, huh?!
It has become hard these days to find a contest which feels fine in terms of difficulty distribution.
I loved the problemset, especially E was very interesting (for me, I have never seen such a reduction to shortest path before).
However, the contest was also very demoralising as I watch myself struggle to solve something more than a thousand people could do :(
Toughness == Trickyness
How do you solve C1?
That difficulty jump between B and C1 tho D:
Why not just call this a Division 1? Sucks when you bait contestants with a trivial A, and then bump up the difficulty level significantly (C appears to be insanely difficult). Oh well.
Me after coding all kinds of stupid stuff for C for 2 hours
Me not coding it at all:
Does greedily converting 'X' which provides most number of winning configs work in C1?
C2 was really beautiful.
Say you have $$$3$$$ colors $$$0$$$, $$$1$$$ and $$$2$$$. Color the cell $$$(i, j)$$$ with the color $$$(i+j) \text{ mod } 3$$$. Now, notice that any $$$3$$$ consecutive cells of $$$X$$$ are of $$$3$$$ different colors.
Used that for C1, couldn't prove that it'd work for C2. How to do that? I'm struck in this area.
Color $$$0$$$ -> $$$2$$$ X, $$$2$$$ O, Color $$$1$$$ -> $$$2$$$ X, $$$2$$$ O, Color $$$2$$$ -> $$$2$$$ X, $$$2$$$ O
Make sure that no cell with colour 1 contains a X, and no cell with colour 2 contains an O (or colours 2 and 3, or 3 and 1, with whichever one you need the least swaps).
What?? Damn.
During this contest, I proved strictly more than one of my solutions by stating "This sounds very elegant and passes pretests, QED".
the difference between a mathematician and a programmer
"And there is no hack in the first page"
I wish Lenin could participate in this round... Problem E ٩(╬ʘ益ʘ╬)۶
So, what did "antontrygubO_o for inspiration!" mean? I assumed some ideas for some problems ideas had come from antontrygubO_o, which is tiny (but nonzero) information, but I was kind of confused when I saw the standings showing that name.
The main idea that came from me was Communism I suppose
The "trygub" from problem A...
Pretest seems to be made very strong by the preparers! Thanks!
I guess this contest is made only for Legendary Grandmasters. Difficulty level at its peak!
The hardest Tic-Tac-Toe ever
Tic-Damn-Toe
Any heuristic which passed C1/C2 (different from editorial)?
Problem D
If number of occurrences of some number (let's call it
i) is 0 then all compressions for allk=1...n-i+1aren't permutationsIf number of occurrences of
imore than 1 then all compressions for allk=1...n-iaren't permutationsIf there are numbers to the left and to the right of
ithat both greater thanithen all compressions for allk=2...n-iaren't permutations. For this checking do the cycle and keeplandr— left and right bounds of subsegment of array that is not considered yet. If position of currentiis not equal tol+1orr-1then break the cycle. Else move the left or right bound.I used binary search + segment tree. have a look 100580701
I didn't complete my implementation yet, but with sparse table it can be done even simpler and faster. Still using binary search of course.
This is just 2-3 simple cycles, O(n)
Coincides with my solution
As a contestant I want rating++
.
where r the rating changes XD
Have a look at those videos.A person uploaded videos during the contest... A- youtube.com/watch?v=oKA9mzrEkJU&ab_channel=AbhinavKumar B- https://www.youtube.com/watch?v=PyBte0lSc6I&t=73s&ab_channel=AbhinavKumar
Shit. They might make the round unrated now...
No, similar things happened in the past
Liked and subscribed
It is a draw!
Not anymore. Congrats Monogon, waiting for Digon to appreciate the son's achievement. :D
D saved this contest for me, phew.
string solve(){ // CALM DOWN : — )
ret(""); }
I'm not sure , but in ~~~~~ if(cnt1<cnt2 and cnt1<cnt3) for(int i=0;i<n;i++) cout<<tvec1[i]<<endl; else if(cnt2<cnt1 and cnt2<cnt3) for(int i=0;i<n;i++) cout<<tvec2[i]<<endl; else for(int i=0;i<n;i++) cout<<tvec3[i]<<endl; ~~~~~ your ifs are wrong , because there is a possibility that cnt1 == cnt2 and cnt1 < cnt3 but your code will use 3 , while he should use 1 or 2.
Idk where is the mistake, I was just curious whether I can find a WA in less than three attempts. Here is my very first attempt lol :D
Global rounds standings may look like https://clist.by/standings/codeforces-global-rounds-2020-18730990/.
Top 3 position is same as facebook hacker cup.
CONGRATULATIONS Monogon for the top contributer
Congratulations to the t-shirt winners!
thank you!!
Does anyone know how to receive T-shirt? I haven't gotten any mail about it...
so do I. I want to know how to receive T-shirt either
So lucky！