Hello Codeforces!
We have a pleasure to invite you to Good Bye 2020, which will take place on Dec/30/2020 17:35 (Moscow time). You will have 3 hours to solve 9 problems. The round will be rated for participants of both divisions.
The problems for this round were prepared by gawry, Anadi and me.
We would like to thank everyone who made this round possible:
Nebuchadnezzar and KAN for the excellent coordination;
Omkar, 221, Manik, namanbansal013, prabowo, Saurabh_yadav, Gauravvv, Fly_37, Thaid, rkm62, neverblunder, Shinchan01, LazyPrime, Jellyman102, SecondThread, Origenes, PS41, antontrygubO_o, yarek and Rzepa for taking the time to test and providing useful feedback;
MikeMirzayanov for great platforms Codeforces and Polygon.
We hope you will enjoy the problem set! Good luck!
UPD: Score distribution: $$$500$$$ $$$-$$$ $$$750$$$ $$$-$$$ $$$1000$$$ $$$-$$$ $$$1000$$$ $$$-$$$ $$$1500$$$ $$$-$$$ $$$1750$$$ $$$-$$$ $$$2500$$$ $$$-$$$ $$$3500$$$ $$$-$$$ $$$4000$$$
UPD: Editorial
UPD: Congratulations to the winners!
New year magic when ?
Don't be sad, It's now available in your profile, have fun :)
As a tester, I recommend participants to say Good Bye 2020 with full energy so that year like 2020 should never come back. :)
Should this be considered a hint?
B+
I think so. It is a hint that the problems will be impossibly hard
Just put all your efforts today into this contest and you'll really see a beautiful 2021. Because the problems are easy!
In my personal experience goodbye(s) are insanely hard contests and this is goodbye f***ing 2020, which has been really a crappy year, so as a contestant i hope no less than an insanely impossible to solve contest :D.
No, that is not true. I have said it generally and there is nothing to preassume about the difficulty of the contest. Problems are really good and interesting.
You're extremely cute, lol :D I was clearly making a joke, but thanks for the reply. This is my first contest in a while so i may suck anyways :D.
Aren't you ready for Corona 2.0. The year 2021 may be worse. Although Programmers do not care about qurantine.
okay professor.
It's a mockery!!!
In January, after New year
I wait magic too, i wanna change nickname
me too bro
lol your name sounds funny in Russian
hahahah yes
So can I take yours then !
I don't mind
So cool bro . It would be great . Really excited !
You can't. As far as I know names stay reserved for the same person who once took them. Try searching for Raptor.L in the handle search bar to see what I mean by that.
From today ;)
more than glad to say good bye 2020 with more than a trifle of passion
Will there be a interactive problem like last year?
I was literally waiting for this contest since 10 months :)
Says someone registered 9mos ago xD
I meant to mark the time of start of pandemic by that
I'm already waiting for Good Bye 2021
Mike knows 2020 is THE END. He didnt even scheduled Hello 2021.
Or maybe he was waiting for you to comment this comment.
Who keeps downvoting me instantly? Is that a bot or something?
May be a group of moralizers
You have demoralized a lot of people. Maybe they are taking revenge. xD
..
:)
Very funny, maybe you should take the opportunity to change the handle
Yes, I'm thinking about that, so that their bot can't target the new handle
LMAO, maybe MikeMirzayanov should check if the bots exist and do something
Bots do exist, I know how they work. It used to be just too easy to make a new CF account, (there were no captchas).
I know that at least one of my enemies had around 30 accounts. It's easy to make a bot to downvote someone, because there are no captchas for login, so writing a bot is not a big deal for the people here, they're all coders.
Even we can create a bot to submit and solve the problems fetching submission of others post the contest and also down-vote Monogon. I am thinking of making the same kind of a script against Monogon.
You downvoted me, I did nothing.
You downvote Monogon, I'll take revenge!
This comment of yours didn't got downvoted , looks like your haters love monogon.
No, actually my haters are indian, and a lot of them are asleep by now.
Ok , My mistake , When I commented you didn't had any downvoted but now you have 6 (P.S.: I upvoted your comment before commenting the first comment)
I am still waking up :) Remembered me.
No, actually my haters are indian,
Actually they want dance performance.You are really cute and talented don't know what the hell kind of person can hate you. If anybody is a true coder they won't never hate a talented coder. Might be your haters are jealous of your achievement.
Anyways you keep up your inspirational journey. You are hell of a motivation.
You're the only person that ever called me cute since my teenage. Thankss a lot.
skip
If someone is in mood of down voting then please downvote this too. adhocers
I was literally waiting for 2020 to come because I wished to watch 2020 cricket match at 20:20 pm with my 2020 biscuits but unfortunately it did not happen so now I am waiting for the earth to destroy and start its counting again from 0.
Can't be more excited for an year to end. Thanks codeforces and all its team for being a constant part of our daily life even in such a pandemic situation.
I can smell the taste of rating loss :v (kidding)
As a tester, I would like to honor memory of Chester
If you struggle with depression, don't be afraid of reaching for help!
Have yourself a wonderful CF round!
Just curious how it is related
2020 and depression
it seems you have a serious antifanclub XD
why people are downvoating demoralizer??any reason??his streams helped me sometimes.please give respect to him.
Some stupid haters downvote the post as soon as he writes and then as you know that the future of the comment depends on it's starts people go on downvoting it.
I just think that MikeMirzayanov is great.
(Let's see if they have the balls to downvote this too)
.
Massive balls detected
idk, it starts being slightly annoying seeing a comment by him on almost all blog posts (not judging tho)
I get downvoted on CF because I don't have a life outside it? Well ok nice makes sense
edgy
downvoted you successfully:)
His comments are demoralizing.
This is my December...
Rename it to FUCK OFF 2020
As a tester, I would say that this contest is the only good thing happening in 2020.
Happy NewBye 2020 !
Will there be in this New year a nickname changing and New year magic?
just one thing i want in my life right now, is "NEW YEAR MAGIC" :3 wanna change my handle badly!
Good bye 2020
andHappy 2020-II
:))can i reach expert before 20201? what do you guys think?
you are already there mate! it's just one contest away! good luck :v
Try your best bro... All The best <<
I doubt if codeforces will exist till then :P (Year 20201)
it will
Rudraksh you will reach master by then!
spacetime I agree with you.
Rudraksh Orz
one day I will also reach candidate master. AMEN
"Shoot for the moon — If you miss, you'll end up in the stars."
Until you realize, stars are even higher.
SecondThread as you are one of the best coders who have experience with problems, what is your opinion about the contest?
Thanks! I don't like talking about problem sets before they are released (to anyone other than the authors of course), but I would definitely recommend participating if you can!
Please do upload your solutions for the contest on youtube after the contest is over.
Yep, will do :)
As promised, solutions to A-F are available here: https://youtu.be/GCfmxnrMdIc
Is it possible to upload a screencast of testing when the original contest is over for any contest upcoming? Curious to see how testing happens.
Check Errichto's channel. He has uploaded a video in which he is testing Div-4A
I am looking forward for this with huge interest!
I love coding but I want to gather with my family at the end of the year :((
Good luck to you and have a nice New Year's Eve <3
Will be there also Hello 2021 contest?
I WISH I WOULD HAVE GIRL FRIEND IN 2021
???: Can you date with me tomorrow?
No, I can't. I have a rated codeforces round tomorrow
You'll miss her forever :<
The best end
Then, lets write contest together
Try following all the things mentioned in this blog
I TOO MAN
Some coders with the name ---"I LOVE _______" are extremly waiting for 2021...xD
I_love_myself has nothing to worry about
I recommend to love yourself, it helps a lot!
I already love myself
I am too bro.My name is Roman.
I am gonna set my name to tanya_romanova_loves_me xD
This account actually exists
how do I change my handle name, please refer me to some blog or steps (I am asking since I think maybe we can change it at the end of a year, if I am wrong then just excuse me for asking)
I don't think you can do that.. You should have decided what you wanted as your handle beforehand. :)
Do KAN and Nebuchadnezzar coordinate together because they have the same name?
Smh. Alts.
Hope everything will be better in 2021
LazyPrime ORZ
I think that Goodbye 2020 is the only good thing in 2020
Hope everything will be better!
As a tester, I found the problems very interesting and enjoyed solving them. Good luck :)
Or enjoyed not able to solve them? :P
I must say these 3hrs rounds are usually more difficult :(
Yeah you are right
Hoping MikeMirzayanov to change his username as a new year gift :)
I hope that the design of Legendary grandmaster will be upgraded to New Year Magic. Look at the rating digits
Just curious, What is the strategy to be followed to increase rating in global rounds?
read all the problems
*solve all the problems
we don't do that here
Only red coders do that here :P
lol
Let your rating falls freely before any global round xD
How come rating of some coders directly start from 1500?
You may refer this Blog
Points Distribution?
I was waiting for this contest since I started competing on codeforces this year. Looking forward to correct the mistakes made in last 2 contests.
As a tester, Good Morning and Goodbye!
Maybe "Good Bye" would look better than "Goodbye", considering the round name? [Also, hoping that you can recover from sickness very swiftly!]
May Be it would.
: |
MainThread
:_|
I was waiting for this contest. Finally it's on tommowwrrow
I wish This Good Bye 2020 will not become good bye expert for me.
What about the Score-Distribution (or penalties for wrong submission) ?
I hope, the new year will erase the filth of this pandemic situation. Thanks a lot for creating Good Bye 2020 contest.
Can't be more excited for an year to end. Thanks codeforces and all its team for being a constant part of our daily life even in such a pandemic situation.
Thank you for all your help and guidance on YouTube! : )
yea and thank you and all other youtubers and streamers to help understand the solution better :)
Are you going to participate today ?
Codeforces to 2020 :) :)
As a tester I think you will enjoy these statements : )
We just enjoy short statements, are they?
Request : Dark mode/theme for codeforces in 2021
it feels better on eyes, continuously switching between text editor (which has dark theme) and codeforces Websites causes eye strain.
Just a small request to devlopers.
or just modify your text editor until they add it?
Tiresome way: change the CSS properties ,every time or add script(i don't know if this will work), till they add it?
refer to this blog
Is it rated?
Are you collecting downvotes??
XD
Is this contest suitable for someone in Div. 3. I am in grade 9 and have a decent understanding of CP up until this point.
You can try the first three problems.
3 hours, 9 tasks. it looks like good training for ICPC.
Can you allow team registration?
31 December: Am i joke to You! (*_*)
My First Good Bye Contest in Codeforces!
My first reply to gokulvaradan in codeforces!
This is most anticipated Good Bye Contest!!! 2020 good bye :)
:"
sed :"}
same here bro!!!
bro :"'''''''
The first contest I gave was Hello 2020. How soon a year passed
The main reason for my progress this year has been Codeforces
.
Anish Giri eliminated already so there is no point in watching anymore :/
I was cheering for dubov... The last game was orz
Dubov rocks , personally i don't prefer Giri . So that's not problem for me.
The way he eliminated Carlen was orzzzzzz so yeaaa... Dubov is <3
My two fav things from Russia 1. Codeforces 2. Daniil Dubov
Good Bye 2020!May the soul of all the deceased of this year find peace and 2021 be a great year for all of us!
I just miss monogon's comments :(
rated for both divisions? I think we have div1, div2, div3. which two are rated?
all of them
pog
hoping to be pupil before 2021 :)
good luck :"}
u too bro :)
Don't worry you will. Just keep practicing hard and your rating will definitely increase.
May god bless us in 2021!
I hope this last contest won't land me back into specialist. Fingers crossed :)
maa ki chut 2020 ki , me to nhi karega participate xd
Why waste time writing this then ?
Seems like this would become the contest with highest number of participants. 17k+ have already registered!
Yeah looks like everybody is free today
Holidays plus codeforces contest!
My rating is 2021, wondering if I should give this contest to spoil it...
Any advice to reach 1800+. I have practiced over 350 questions but still Iam newbie. Not even specialist or pupil.
I think that all code editor should change their welcome style--> "Hello world"-->"Hello 2021"
Dear Codeforces I am a newbie coder please make a contest on [contest:Hello 2021]
Today's contest will help me to reach pupil. AMEN
GoodBye rating!
May Almighty make all things right in 2021....
This is the last contest of year I hope this at least goes well for me
I really don't want to bring my orange name to 2021 . This is my last chance to reach red in 2020!
All the best
All the best!
Same :( i want to become red
Good luck
I really hope I can end 2020 as a blue
good luck
Sadly,I miss the chance.
I just forget to add a line of "reverse(ALL(s0))" in problem G and keep getting "wa on 4".This contest teaches me not to ignore every small detail .
Goodbye Rating`
~~~~~
cout<<"good bye rating"
~~~~~`I Love Second :(
Nice, I have been waiting for a long time. Thanks Codeforces !!!!
HAPPY NEW YEAR GUYS HOPE U ALL GOOD RATINGS :D
BYE 2020 : )
Why not be "Hello 2021"???
There will be another contest of Hello 2021.
2020 was the worst phase my life. Full of depression and suicidal thoughts. Literally I was striving to overcome. Luckily I survived and now I will be participating here in Good Bye 2020 :)
Hope this contest will make you a good memorize. All the best!
When is the contest "Good bye COVID-19"?
Never (-_-)
When covid will gone, it must be celebrated necessarily!
must and necessary in the same sentence, dab.
This makes me soooo happy. Finally 2020 is going :')
I've never had a positive delta in any Div1 Div2 combined round, let's see if I'm able to get out of this curse today :P
Goodbye, 2020! Hope this will be a good round with strong pretest, short and clear statement problem.
Good Bye 2020 on 30th Dec: MikeMirzayanov be like I can't wait till 31st to say good bye to 2020.
Good Bye 2020 :)
I have a feeling I'll have a positive delta in this round :-P
Rating Bye-Bye 2020?
This is my last comment in 2020
Those who start 2021 year with a rating of 2021 will be lucky :P
4 problems with scoring less than 1000, 6 less than 1750! Is it gonna be SpeedForces :\
I guess score distribution is a bit experimental like in GR11
Hoping this Good Bye 2020 doesn't turn out to be Good Bye ratings. Fingers crossed.
One Decade on codeforces will be completed by today's conntest for tourist
i wish i can change my rating instead of codeforces handle :_
does this distribution mean problems would be easier?
Apparently, yes
I know the authors and I have an idea. Let's not destroy their New Year's Eve and let's assume that the statements are correct, and not ask 500 questions this round, ok? This is a combined round, we can assume that if something is wrong, then, let's say, somebody orange+ will ask a question about this. OK? If you think that something is wrong with the statement — assume that you misunderstood it.
What do you think about this idea guys? Let's treat this as a gift for them.
Yes
There are already more than 1200 orange+ registered participants so I suggest that oranges like me should leave that responsibility for reds.
24000 vs 1200 is a huge difference :P
There are guys wid 1200 rating and who never reached more than 1400 are orange and black...
Will there be an interactive problem?
:)
this year thaught me many things, gave me many experience, but the best thing i ever experienced was that happiness when my first solution was accepted on codeforces contest. hello every coders out here, i love you all.
contest starts in 60....59.....58....57.....56.....55......54.......53......52......51......can't count more
Really enjoyed the statements! Thank you!
Something irrelevant, if I submit the correct solution twice do I get -50 as penalty for that?
yes.. count the last correct submission. others as penalty.
I thought the last contest of this year will bring a good rating changes for newbies like me. But alas!!.I couldn't even figure out problem A statements....After all it is year 2020(a cursed year).
Should've had one more problem between F and G :(
+1
Bye 2020 !!... Let's find out how will your 2021 be
click one of the options below...if u get Rick Roll ..Believe me your 2021 will be amazing
1.A
2.B
1.C
2.D
Jokes on you, the browser usually shows the url in the bottom left corner when you hover your mouse over a link.
Solve A,B and C fast and then see your rank fall.
How to solve E ??
I wish my knowledge like apollo or pan !
Yup, I was stuck on E too :\
Basically, you fix j and then you realise that the answer for all sums with that j is (sum of i&j) * (sum of j|k). Then you just use bitwise decomposition of the numbers to find those values quickly.
How exactly do you find the values quickly, if you could elaborate on that? I've realized the first observation and couldn't figure out the other part.
You decompose each number into its bit representation.
Then if bit x is on in j, you add 2^x * (number of bit x on across all numbers) to the sum of i&j and n * 2^x to the sum of j|k.
If bit x is off, you just add 2^x * (number of bit x on across all numbers) to the sum of j|k.
I pretty much did this but got TLE. Can someone tell me why? https://codeforces.com/contest/1466/submission/102858405
Your logic is correct but actually the time limit is strict. Check the constants that are responsible for TLE. And calling functions within functions causes too much overhead.
I think the function calc is the reason for TLE. It is an extra loop each time which can be computed in testcases function itself without any extra loop.
slow IO. Try using ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); on the begining
can you see my code and tell me where I made mistake?)
After skimming the editorial, it is clear to me how algebraically we can discover this fact (of separating the components as you did). When you solved in in contest, did you also do algebraic manipulations or is there an intuitive reason for why this is true?
I looked at the double sum after fixing j and realised it could be separated out into the product of two sums. It's somewhat intuitive if you have played around with a lot of summations, I guess, but I still did the algebraic proof for it.
You should split to bits all the numbers and count bits in each position out of 60, let it be
kb[i]
. Fix eachx[j]
then you can count the sum of all(x[i]&x[j])*(x[j]|x[k])
. In order to compute(x[i]&x[j])
, choose all positionsp
where bit ofx[p]
in this position is 1, then(x[i]&x[j])
= sum of2^p * kb[p]
for allp
. In order to compute(x[i]|x[j])
, choose all positionsp
where bit ofx[p]
in this position is 1 and all over positions p1, then(x[i]&x[j])
= sum of2^p * n
+ sum of2^p1 * kb[p1]
I'm like 50-50 on whether G is super brain observation or string algorithm, and either one is :(
Good contest though. A bit on the easy side for the first six questions, but nice problems.
test 7 on F
Try this..
Ans is
2 1
1
Isn't it?
Didn't statement say that the same vectors don't exist?
A good contest for me at the end of the year, solved 5, wish they pass the system testing :) Finally became specialist at the end of the year :)
any ideas/hint for D? i did dfs but can't recognized my bugs :/
EDIT: got AC right now, thanks guys for your insights chenreddy Liviu2000 rum3r Ogneopasno
DFS not needed. Try to solve the problem by observing the optimal edge distribution for small inputs. Try to make use of indegrees.
can you try D on this testcase?? 1 7 10 6 5 4 8 2 1 1 2 1 3 1 4 2 5 3 6 4 7 Ans-> 36 46 56 62 67 71 but i think instead of 46 it would be 42 it said sum of maximum of each colored compoment? can you correct me where i am getting wrong?
try to build an array of pairs {degree,weight} and then sort it.
No need for dfs bro. Just sort them according to $$$value$$$. And if the current vertex have $$$degree > 1$$$ then, we can add it's value to our answer until its degree gets exhausted or in other words we have to contest the node with the different values of k. So, that its value gets counted twice.
It's can make new subgraph of new color such way that the new subgraph is connected. New subgraph obtains from one of current subgraphes by splitting to 2 parts. Each time when k increasing by 1, the value of coloring is increasing by the value of such vertice where was splitted the old subgraph. So for each k choose maximum vertice of possible. Just count for each vertice the number of edges that adjacent this vertice
Cool NY contest, thanks!
This round was sexy AF. I really enjoyed the problems (like a lot!). This has been my best performance so far and I'm very happy that I was able to do so in the last contest of the year. It's been a rough year for many, a great time to grind CP for others and a somewhat meh year for me. Whatever it has been, happy new year to everyone! Hope everyone has a great year ahead!
I don't understand how F could possible have 1000+ solves as it seems way too orz than normal. If someone could tell me how to solve, I would be very happy about it. The problems this round were great (to say the least) and the difficulty ordering and level felt perfectly balanced. Thank you authors!
If you think about how xor of individual dimensions cancel out on F, we can reduce it to a minimum spanning tree problem. Edges will be connecting the two dimensions that are on in a matrix (or a dimension to 0 if the matrix only has one on dimension), and weights on the edges is simply the edge number. This produces lexicographical order.
It can be shown that all 2^|S'| possible sums produced are unique.
Was score decay adjusted for 3 hour duration?
Another shit of 2020 ended today lowering n to 10000 in C allows dp[N]*[26]*[26] solutions but memory limit exceeded due to tight constraints.
Maybe just changing 2/3 character long palindromes was enough.
Change that 26 to 2.
I wish you a happy new year Hoping for your increasing success and a world without corona virus in 2021!
If only I could have done D a bit faster :( with more accuracy :((
Why this code gives TL? https://codeforces.com/contest/1466/submission/102850721
maybe ios::sync_with_stdio(0)
How to Solve Problem C ?
You can always make a palindrome cease to exist if you change its middle character (if even length) or change 2 middle characters (odd length > 3). So we just need to find length 2 and 3 palindromes and change them so that they donot remain palindromic.
Iterate from 1 to n and if s(i,i+1) is a palindrome then replace s[i+1]. Else if s(i-1,i ,i+1) is a palindrome replace s[i+1].
Why is it always optimal to replace $$$i+1$$$ ?
Changing i+1 will rule out the possibility of i+1,i+2 and i+1,i+2,i+3 being a palindrome as well.
How to solve C, anyone?
You can always make a palindrome cease to exist if you change its middle character (if even length) or change 2 middle characters (odd length > 3). So we just need to find length 2 and 3 palindromes and change them so that they donot remain palindromic.
I came up with that idea, but couldn't proceed more than that. tried a way to remove greedily but was failing i.e. getting WA. Can you elaborate how to remove 2/3 len palindromes?
Check if the first two characters are same, then change the second one. Now run a loop form the 3rd character to last and check if it is equal to any of the previous two characters. If it is, change it. When I say change, consider to changing it to some arbitrary character which is not a lower case alphabet. This is because, since you have 25 choices to change the character, and a character from the string can only contribute to maximum 4 different palindromes, that is, i-2, i-1, i+1, i+2. There is always an optimal choice that doesn't affect other palindromes.
my second submission had exactly same idea, but smh it got WA and i thought that this idea is incorrect.
Yeah sure,
For len 2 palindromes, say at indices : (i,i+1) you have to set the second character(i+1) such that it does not equal to i,i+2 and i+3.
For len 3 palindromes, say at indices : (i,i+1,i+2) you have to set the third character(i+2) such that it does not match (i,i+1,i+3 and i+4).
Also there is a condition for len-3 here : (s[i]!=s[i-1]) which is explained below :
So we would first correct all 3 len palindromes and then proceed to filter all 2 len.
Explanation of condition:
Say there is some string of form "bbab". Here there is a 3 len "bab" substring. So according to our logic we would make the last b equal to some other valid character, say now it became : "bbax". Now we proceed to 2 len filter and find "bb". And now say we get "byax". So changes are 2, but answer is 1 as you can always change the second b. i.e "bxab" works here.
Lastly we count the new changes by storing the indices in a set.
thanks for the detailed explanation. got it. i did smthg similiar, will try to figure out what went wrong.
:)
Perfect explanation, thanks!! orz
:)
approach each adjaent 3 characters must be different. think of greedy/dp now
why did this submission get time limit :(
Because of question E, I learnt how to write and submit C++ code today. I have always been writing in Python.
It is a good start for 2021.
Because of question E, I learnt to be careful with mods
me too
I wish I found the bug quickly.
Can't believe I didn't find the overflow in n*xs[i]%MOD until after the contest. I spent more than 20 minutes double-checking everything except this.