By Radewoosh, history, 2 years ago,

Hello coders! I hope that you are enjoying the New Year as much as me. To make its beginning even greater, Codeforces is going to host a contest and I will be an author of all tasks. Hello 2019 will take place on Friday.

Using the opportunity, I want to thank to:

• Lewin and mnbvmar for testing the round.
• cdkrot and KAN for round coordination and help with preparation.
• MikeMirzayanov for such great platforms (you know which ones :P).

The round will consist of 8 problems and you will be given two and a half three hours to solve them. Yes, the round will be rated.

There will be no interactive problems, but if you want you can read this document anyway, it's always good to learn new things.

Good luck and see you during the contest!

UPD1: Editorial

UPD2: I'll be on the Discord channel after the contest, so you will be able to ask me about the problems.

UPD3: You're probably wondering what the statements will be about. I hope that it will be another great year for Codeforces. As it's the community that creates it, I decided to write statements about the people who already have or had their part in Codeforces' history. As I wanted to be objective, the statements will be about 8 people who triumphed the most times in CF rounds. Using the opportunity, I want to invite these 8 people to take part in the contest. Let's say that the first person who will guess the set in the comments wins some free contribution. Good luck!

UPD4: The round will be 3 hours long.

UPD5: The drain will be adjusted and the scoring will be 500-1000-1500-2000-2750-3000-3500-4000.

UPD6: The round is over, congratulations to the winners!

And to the first-to-solvers!

UPD7: Editorial

Announcement of Hello 2019

• +1910

 » 2 years ago, # |   +550 You accidentally uploaded the ediotiral, but i am honest and don't look there
•  » » 2 years ago, # ^ |   +453 Well, thanks for that, but you shouldn't worry so much :P
•  » » 2 years ago, # ^ |   -12 you changed your handle from numb. So many quora links are gonna be dead now
•  » » » 2 years ago, # ^ |   0 I have seen a new name in my friend list and wondering about who is this guy... Finally I understood...
•  » » » 2 years ago, # ^ |   +17 If you change your handle the links refered to the lastwill redirect to the new profile page
•  » » 2 years ago, # ^ |   0 I wish everyone as honest as you.World Would be Better Place to Live
 » 2 years ago, # |   +22 Nice editorial tho.
 » 2 years ago, # | ← Rev. 3 →   +1 I can neither confirm nor deny that editorial without Radewoosh's approval
 » 2 years ago, # | ← Rev. 2 →   -225 lol
 » 2 years ago, # |   +44 That editorial, haha, so funny!
•  » » 2 years ago, # ^ |   +248 I hope that you won't die laughing ;_;
 » 2 years ago, # | ← Rev. 3 →   +70 this.handle+" 2019!";
•  » » 2 years ago, # ^ | ← Rev. 2 →   -92 // It should be this->getHandle() + " 2019!"; 
 » 2 years ago, # |   +239 Thanks for fast editorial.
 » 2 years ago, # |   +90 I really hope noone is enjoying the New Year as much as you.
•  » » 2 years ago, # ^ |   +144 For their own health.
 » 2 years ago, # |   +228 Can you please reupload the editorial? It is not available in my country and now I feel at disadvantage.
•  » » 2 years ago, # ^ |   +98
•  » » 2 years ago, # ^ |   +89 tfw youtube blocks education... Sad day for science.
•  » » 2 years ago, # ^ |   +74 Since you like numbers you'll enjoy this https://youtu.be/BipvGD-LCjU
•  » » » 2 years ago, # ^ |   +1 that's so funny, thanks for that!!
 » 2 years ago, # | ← Rev. 2 →   -24 One of the best editorials ever seen. Nice one.. Haha:P
 » 2 years ago, # | ← Rev. 2 →   -10 Why aren't you blue anymore? Also, what is the blog gonna look like when you upload the real editorial?
 » 2 years ago, # |   +10 too excited about the first contest in this year and as well as a contest by Radewoosh.
 » 2 years ago, # | ← Rev. 3 →   0 Awesome editorial! :P
 » 2 years ago, # | ← Rev. 2 →   -27 -
 » 2 years ago, # |   +1 By the way, why isn't the Rating of the problems in Goodbye 2018 shown yet?
 » 2 years ago, # |   +24 could you explain in more detail div2a? including official solutions also helps.
 » 2 years ago, # | ← Rev. 2 →   0 Nice editorial :P
 » 2 years ago, # | ← Rev. 2 →   -30 LOL HAHABA SHIT JOKE=))))
 » 2 years ago, # |   +184 Me: Oh, an editorial... let's to see!(wild video appears...) Me: ;;;;;;;;;;;;::;,.,xOOOOOOOkdoc;,,;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;,,'''',,,,,,,,,'',,:cloo:'. ;;;;;;;;;;:ccccc,'lOOOOOOOOOOOxoc;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;,,''''''''''',;cloxkOOOOl.. ;;;;;;;;;:cccccc:,;xOOOOOOOOOOOOOxoc;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;,''''''';:loxkOOOOOOOOk:.. ;;;;;;;;;:cccccc::,ck0OOOOO0OO00OOOOxl:;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;,'',;codkO0OOOOOOOOOOOo'.. ;;;;;;;;:cccccc:::;,ck0OOOOOOOOOOOOO0Okoc;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;:cloxOOOOOOOOOOOOOOOO0x;..' ;;;;;;;:ccccccc::;;,,:xOOOOO0OOOOOOOOOOOkdc;,;;;;;;;::::ccccccccc:::::cldkOOOOOOOOOOOOOOOOOOO0k:..'' ;;;;;;;:cccccc::;;,,,';dO0OOOOO0OOOOOOOOOOkdodddxxxxkkkOOOOOOOOOOkkkxkkO0OOOOOOOOOOOOOOOOOOO0kc''''' ;;;;;;;::::::::;;,,,''',cxOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOxc,,,,'' ;;;;;,;;;;;;;;;,,,,'''''',lkOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOko:;;;;,,, ;;;;,,,,,,,,,,,,''''''''''.,lkOOkxkOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOkoc:c:::;;,, ;;;;'''''''''''''''''''''''..;lodkO0OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOkxk0Okxocccccc:::;,, ;;;,'............'''''''''''..;xOOOOOOOOOOOO0OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOkxdol::::cccc:::;;,, ;;,'..............''''''''''';dOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOko;;::::::::;;;;,, ;;'................'''''','',dOOOO0OOOxdoccxOO0OOOOOOOOOOOOOOOOOOOOxdoclxOOOOOOOOOOOo;;;;;;;;;;;;,,' ;,'................'''''',,,lOOOOOOOOoo00c.;xOOOOOOOOOOOOOOOOOOOOOll0O:.:k0OOOOOOOOOOo,,;;;;;;,,,,'' ,'..................''',,,,ckOOO0OO0Ol,::,.,d0OOOOOOOOOOOOOOOOOOOOc,::,.;x0OOOOOOOOOOkc',,,,,,,,,,'' ,'..................''',,';dOOOOOOOO0kc,,,;oOOO0OO0OO0OOOOOOOOOOOOkc,,,:dOOOOOOOOOOOOOd,',,''''''''' '...................''',,,lOOOOOOOOOOOOkxxkOOOOOOOOxdddkOOOOOOOOOOOOkxxOOOOOOOOOOOOOO0kc'''''''''''' '...................''',,;xOOOkkkOOOOOOOOOOOOOOOOOxo:;:dOOOOOOOOOOOOOOOOOOOOkkkkOOOOOOOd;''''''''''' '.................'''',,,ckxollllldkOOOOOOOOOOOOOO0OkkOOOOOOOOOOOOOOOOOOOkdlllllodkOOOOOc'','''''''' ''''...........'''',,,,,;odccccccccokOOOOOOOOOOOOOOO0OOOOOOOOO0OOOOOOOOOxlcccccccclk0OOOd;,,,,,,,,'' '''''''',''',,,,,,,;;;;;;ddcccccccclxOOOOOOOOOOOOkxdddddooddkOOOOOOOOOOOdccccccccclx0OOOOl,;;;;,,,,' ',,,,,,;;;;;;;;;;;:::::;:xOdolclllokOOOOOOOOOOOOxllodddxdddllkOOOOOOOOOOkocccccccldOOOOOOd:;:;;;;;,, ,,,;;;;:::::::::::::::cc;lOOOkkkkOOOOOOOOOOOOOOOdlodxxdxddxdcdOOOOOOOOOOOOkxdoddxkOOOOOOOOl:::::;;,, ,,;;::::cccccccccccccccc::dOOOOOOOOOOOOOOOOOOOO0kolldxxxxxxoldOOOOOOOOOOOOOOOOOOOOOOOOOOOOd::c::;;,, ,,;;:::cccccccccccccccccc:cxOOOOOOOOOOOOOOOOOOOOOOkxoooooooodOOOOOOOOOOOOOOOOOOOOOOOOOOOOOkc:c:::;,, ,,;;::::cccccccccccccccc:c:cxOOOOOOOOOOOOOOOOOOOOOOOOOkkkkkOO0OOOOOOOOOOOOOOOOOOOOOOOOOOOOOo;:::;;,, ,;;;;::::ccccccccccccccc:::;ck0OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOx::::;;,, 
 » 2 years ago, # |   +19 Your editorial sucks! The video isn't available in my country!
 » 2 years ago, # |   +173
 » 2 years ago, # |   +63 clicked on the EditorialReally Radewoosh? Thanks for being the first one doing that to me in 2019 :D
 » 2 years ago, # |   +11 The most unique editorial I have ever seen. Hoping for a nice contest now (paradoxical I guess, waiting for the contest after editorial)Also, Thanks a lot for suggesting us to learn about new things :)
 » 2 years ago, # |   +3 Looking forward to it, hopefully I will finally become green again :P
 » 2 years ago, # |   -64 Radewoosh you can't beat tourist
 » 2 years ago, # |   +12 Not gonna lie, I thought I badly missed the contest..Until I swiped left my mobile screen..
 » 2 years ago, # |   0 I've been looking forward to a round prepared by a single expert, but, however..
 » 2 years ago, # |   +1 wulalalala is it rated?
 » 2 years ago, # |   +1 what is the rating of the contest ?
•  » » 2 years ago, # ^ |   +11 If the question is, Is it rated? then answer is YES. or, if the question is Rated for which division? then answer is Everyone who will attend the contest.
 » 2 years ago, # |   +46 Fastest editorial in my codeforces history. Thanks Radewoosh
 » 2 years ago, # |   0 Well-written editorial ^^ but I think you forgot to link the statements that go with it :\
 » 2 years ago, # |   +5
 » 2 years ago, # |   +12 I've already read so many editorials that I know this gXcQ by heart.
 » 2 years ago, # |   +12 Fastest editorial ever!!! Also that's one of my favorite songs to cheer me up too.
 » 2 years ago, # |   +28 Is it just me, or does Radewoosh look really similar to Rick? o.O Radewoosh vs Rick
•  » » 2 years ago, # ^ |   0 I thought you were thinking of Rick Sanchez and was like no, Rick is more similar to Um_nik...
•  » » » 2 years ago, # ^ |   +5 Or maybe LanceTheDragonTrainer.
•  » » » » 2 years ago, # ^ |   +5 Rick Astley
 » 2 years ago, # |   0 Never gonna give you uuuup! I like this editorial :)
 » 2 years ago, # |   +20 How to solve D ?
•  » » 2 years ago, # ^ |   +33 You can view the editorial linked in the blog for the answer
 » 2 years ago, # |   0 Exceptional Editorial :P
 » 2 years ago, # |   -80 Me: Wow! An Editorial, before the contest! (Let's see... I don't want to miss the chance today!)Clicked the EditorialHope I can dance like him after the first contest of the year!
 » 2 years ago, # |   -35 The past Hello contests: Happy New Year!!
 » 2 years ago, # |   0 Wow, early editorial. When are you gonna update the ratings?!.
 » 2 years ago, # |   +7 Goodbye 2017;Hello 2018.:D
•  » » 2 years ago, # ^ |   +59 Hi Internet Explorer
•  » » 2 years ago, # ^ |   +22 Ping : 999
•  » » » 2 years ago, # ^ |   -11 lol
•  » » » 2 years ago, # ^ |   0 lol
•  » » » 2 years ago, # ^ |   0 Hello // Do you know the solution of C
 » 2 years ago, # |   0 I'm gonna listen to this editorial everyday
 » 2 years ago, # |   0 Thanks for the video editorial , really educational !
•  » » 2 years ago, # ^ |   0 Rusian braindead
 » 2 years ago, # |   0 Just hope, everyone has high ratings with this new year. Tough competition though :P
 » 2 years ago, # |   0 OMG, Radewoosh contribution +200. Thats so much!
•  » » 2 years ago, # ^ |   -15 are u stupid
 » 2 years ago, # |   +45 Fuck U Radewoosh.My New Year Resolution was not to Open Youtube(Personal Reason).And Bcoz of u it is broken now.
•  » » 2 years ago, # ^ |   +15 You should have blocked youtube then.
 » 2 years ago, # | ← Rev. 2 →   +10 this will get me out of master :^D
•  » » 2 years ago, # ^ |   -30 Noob
 » 2 years ago, # |   +8 Everyone says that he hopes to be green, gray and other color. I hope to become Double Legendary Grandmaster SuperJava
•  » » 2 years ago, # ^ |   -27 are u noob??
 » 2 years ago, # |   -13 lol
 » 2 years ago, # |   -21 Is it rated??
•  » » 2 years ago, # ^ |   0 "Yes, the round will be rated"
•  » » » 2 years ago, # ^ |   +3 Sorry cant read can u give it to me in voice mesage
 » 2 years ago, # |   0 ArepitaDePernil will never tell a lie and hurt you!!
 » 2 years ago, # |   0 Hope to reach green this contest :)
 » 2 years ago, # |   +8 it would be cool if pressing the downvote button would also redirect u to smth funny
 » 2 years ago, # |   0 Lets see if this post gets more upvotes than Hello 2018. Radewoosh you are my favorite.
 » 2 years ago, # | ← Rev. 5 →   +6 I think that the set of people will be: tourist Petr Radewoosh Um_nik rng_58 OO0OOO00O0OOO0O0…O PikMike Vovuh
•  » » 2 years ago, # ^ |   +19 Errichto has never won a round, sorry :/
 » 2 years ago, # | ← Rev. 2 →   0 Challenge in UPD3 is pretty simple using Codeforces API but I'm too lazy so let me guess. Let me spare them these mentions: Petr, tourist, Radewoosh, OO0OOO00O0OOO0O00OOO0OO, Um_nik, rng_58, V--o_o--V, YuukaKazami
•  » » 2 years ago, # ^ |   +8 Looks almost correct :P
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 You forgot Swistakk :)))
•  » » » 2 years ago, # ^ |   0 He won once, I doubt it's enough to be in top-8
 » 2 years ago, # |   0 I wonder what is the number of participants who won at least one rated(for div1) contest. Too lazy to check using API and/or by opening results, of course.
 » 2 years ago, # |   0 UPD3 challenge: tourist, Radewoosh, OO0OOO00O0OOO0O00OOO0OO, Um_nik, V--o_o--V, LHiC, Petr, encerwala
•  » » 2 years ago, # ^ |   +8 Not this time :C
 » 2 years ago, # |   -24 UPD2: I'll be on the Discord channel after the contest, so you will be able to ask me about the problemsI can't enter the server ((
 » 2 years ago, # | ← Rev. 2 →   +302 Egor it was very tricky from you to hide on 158th place in overall standings with these 11 wins of yours :PPetr tourist Radewoosh Retired_MiFaFaOvO Um_nik rng_58 V--o_o--V Egor — be aware that Radewoosh invites you to take part in this contest :)
•  » » 2 years ago, # ^ |   +65 And we have a winner!
•  » » 2 years ago, # ^ |   -6 Seems cool, he's just after tourist and Petr, not sure about OO0OOO00O0OOO0O00OOO0OO, but all in all, 11 is too much!!!
•  » » 2 years ago, # ^ |   +20 I'm not saying that V--o_o--V is not cool, but among his 8 wins 2 are schoolboys competitions and 3 are VKCup rounds, so 5 wins with huge restrictions on participants.
•  » » » 2 years ago, # ^ |   +107 V--o_o--V showing Um_nik who's the boss.
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   +10 I'm not saying that V--o_o--V is not coolSmooth on Um_nik's part to write this. Otherwise this comment will not have aged well at all. :D
•  » » » » 2 years ago, # ^ |   -17 why are you so happy? you don't care who's the boss or not
•  » » » 2 years ago, # ^ |   +1 You lost, V--o_o--V win
•  » » » » 2 years ago, # ^ |   -18 what about you? tell us how you lose the rounds always to thousands people
•  » » 2 years ago, # ^ |   +6 Radewoosh invites himself to take part in his own contest? :thinking:
•  » » 2 years ago, # ^ |   +36 includes unofficial participation gimme some of the left over contribution
•  » » 2 years ago, # ^ |   +81 Anyone wants to create Codeforces version of this?
•  » » » 2 years ago, # ^ |   +10 Something like this? Link
•  » » » » 2 years ago, # ^ |   +1 Thank you, looks nice :)Maybe we shouldn't mix d1/combined matches and d2/d3/unrated matches?
•  » » » » » 2 years ago, # ^ |   0 You're welcome. I will try to modify the UI a bit later separating divisions into different tables. :)
•  » » 2 years ago, # ^ |   +86 Only reason I failed last several rounds is to deceive everyone in anticipation of this
 » 2 years ago, # |   +8 I just want to tag dreamoon_love_AA sorry_dreamoon :P.
 » 2 years ago, # |   +15 In UPD 3 , I think they are (in sorted order from number of contests winning)1 — tourist 2 — Petr3 — OO0OOO00O0OOO0O00OOO0OO 4 — rng_585 — Egor6 — Um_nik 7 — V--o_o--V 8 — Radewoosh9 — YuukaKazamiand since you said that you invite first 8 to take part in contest...so I think that maybe you mean 9th which is YuukaKazami
•  » » 2 years ago, # ^ |   +52 Unfortunately there are two persons on 9th place, so I'm also inviting myself to take part (and I will, but from the other side :P).And sorry, but our contributionboy was faster.
•  » » 2 years ago, # ^ |   -12 you forgotten: 0 _ Wael.Al.Jamal
 » 2 years ago, # |   0 I cant understand the editorial, anybody can explain with more details? :D
 » 2 years ago, # |   +42 It sure will be the best 2019 contest so far.
•  » » 2 years ago, # ^ |   +3 i don't think so
•  » » 2 years ago, # ^ |   +210 I don't believe in him, I bet it will be the worst one so far.
•  » » » 2 years ago, # ^ |   +10 We have a winner here :P
 » 2 years ago, # |   +40 Change the start time to 20:19 ! :D
•  » » 2 years ago, # ^ |   +4 Taking part in a contest begins at 22:35(UTC+8) is usual for me now, but if it lasts for 3 hours...
 » 2 years ago, # |   0 I had thought the editorial is not standard but I really can't stop myself from clicking it!
 » 2 years ago, # |   +14 I hope there won't be solutions in the problems.
 » 2 years ago, # |   +8 Even Problems In an Odd Year will Make My Day !!!
 » 2 years ago, # |   +2 One of the Best Editorial ever.Thanks for the Motivation.Another Editorial if you wanna take a look.
 » 2 years ago, # |   0 finally.. someone generous. Three hours !
 » 2 years ago, # |   +1 Really enjoyed this editorial.
•  » » 2 years ago, # ^ |   -11 I love You too.
 » 2 years ago, # |   +13 If you can't see the editorial, you can try this. It's the same video.
 » 2 years ago, # |   0 The 8 people will not includes OO0OOO00O0OOO0O00OOO0OO because it's too hard to write.QAQ
 » 2 years ago, # |   0 Nice editorial. Hahaha.
 » 2 years ago, # |   0 Outrageous editorial!
 » 2 years ago, # |   -68 Why those stupid early contest times for this and Goodbye 2018? I'm not a shut-in with nothing to do except programming contests at any time!
•  » » 2 years ago, # ^ |   +7 Actually it's a little too late for Asian. It's hard to meet everyone's need. So it's better to enjoy those you can participate in and stop complaining about everything.
•  » » » 2 years ago, # ^ |   +17 It's hard to meet everyone's need. Yeah, which is what two consecutive big rounds with the same starting time don't do. If you look at the contest list, the last 8 rounds including this one (some div1) had an early starting time.There are countless things I'm not complaining about, so how about you don't try to dismiss a valid point? Which rounds can I enjoy if it's been almost a month since one didn't start in the early afternoon?
 » 2 years ago, # |   +22 PM 11:30 to AM 02:30 in my country 8ㅅ8
•  » » 2 years ago, # ^ |   0 AM 00:35 to AM 3:35 in my)
•  » » » 2 years ago, # ^ |   0 cheer up!
 » 2 years ago, # |   0 First time I have watched any Editorial before contest..... it' like Boost up..hahahaha
 » 2 years ago, # |   0 welcomeBack();
 » 2 years ago, # | ← Rev. 2 →   +78 Adjusted drain, please. Nobody wants their C-D to be worth more than G-H.
•  » » 2 years ago, # ^ |   +44 Pls pls pls!!! It lasts 3 hours (not 2.5), so it is even more important!
•  » » 2 years ago, # ^ |   0 it is adjusted
 » 2 years ago, # |   0 I believe it will be very cool!
 » 2 years ago, # |   +15 I Have a Farsi exam tomorrow, I know Im going to fail but F*** that, I waited a year for this.
 » 2 years ago, # |   0 Very exclusive tutorial.Following the tutorial most of the contestant including me become legendary grandmaster without participating any contest :D
 » 2 years ago, # |   +4 Never gonna give you up =))
 » 2 years ago, # |   +88
 » 2 years ago, # | ← Rev. 2 →   +43 Score distribution? Updated Now
 » 2 years ago, # |   +9 Good luck to all! Wish you to see lot of "Happy New Year!" verdict!
 » 2 years ago, # | ← Rev. 4 →   +1 Before start, delayed by 10 mins :|
 » 2 years ago, # |   +17 why delay 10 min ?
•  » » 2 years ago, # ^ |   +29 Finally my time travel machine worked, I moved everyone 10 minutes in the past
 » 2 years ago, # |   0 10 minutes delay means now I will skip the last 30 minutes of the round, not a good thing :(
 » 2 years ago, # |   +22 PING : 600000ms
 » 2 years ago, # | ← Rev. 2 →   0 I'm confused because the contest was suddenly delayed a few seconds before the start of the competition.
 » 2 years ago, # |   0 JEBAITED XD
 » 2 years ago, # |   -6 Is it another DDOS attack???
•  » » 2 years ago, # ^ |   +12 Maybe expecting more participation, I guess.
 » 2 years ago, # |   0 What an Anti-Climax (Delayed by 10 mins)
 » 2 years ago, # |   +3 There should be a notification when a contest is delayed. We press OK and suddenly get shocked to see delay :/
 » 2 years ago, # | ← Rev. 3 →   +34 Radewoosh, You want to crack the 12K record?
 » 2 years ago, # |   -13 UDP5 : 10 min delay.
•  » » 2 years ago, # ^ |   +8 (UDP5 -> UPD6)
•  » » » 2 years ago, # ^ |   0 i am hacked just before the contest :P
 » 2 years ago, # |   +38 Trying to get 12k registrants and beat Goodbye 2018 with that delay? haha
 » 2 years ago, # |   +9 I think the delay was for beating the record for the most registered people in a contest.
 » 2 years ago, # |   +5 About +600 participants. Good luck :)
 » 2 years ago, # |   +16 It's great idea from you to put a link to your song in the blog, nice advertisement man
 » 2 years ago, # |   +8 Starting new year with 10 minutes delayed contest, it gonna be legen wait for it dary year.
 » 2 years ago, # |   +46
•  » » 2 years ago, # ^ |   0 wtf, almost the same problem indeed!
•  » » 2 years ago, # ^ |   0 Yes, it was common for a lot of us.... :p
 » 2 years ago, # |   -30
 » 2 years ago, # | ← Rev. 2 →   +118 Setters be like:  A: lets make an A-level problem  B: lets make a B-level problem  C: lets make a C-level problem  D: let them lose their mind :O 
 » 2 years ago, # |   -30 What is TC4 of Prob C?
•  » » 2 years ago, # ^ |   0 This was a useless question...
 » 2 years ago, # |   +129 Radewoosh unbalanced contest
•  » » 2 years ago, # ^ | ← Rev. 2 →   +17 no sh*t
 » 2 years ago, # |   +97 Why does E have only 1 correct submission? Overkill or wrong official solution?
 » 2 years ago, # |   +185 For Div-2 Coders, it was a 1/2 hour contest.
 » 2 years ago, # |   0 very funny statements
 » 2 years ago, # |   +11 The test case 2 of D is killing me for past 1 hour. For some reason, I can't seem to figure it out (in fact n=6, k=3 provides me with the given output). However, as there has been nobody raising that issue, the only explanation is that I have forgotten all my maths.
•  » » 2 years ago, # ^ |   +3 It was strange for me too The problem with me in this problem that I didn’t even understand what is the statement Also no explanation for the output of the second test . When i asked the author he repeated the statement for me I thought it is only my problem
•  » » 2 years ago, # ^ |   +1 Well I had the same problem at the beginning The problem is that you take into account the number of divisors of a divisor of N to calculate the probability for each k
•  » » » 2 years ago, # ^ |   0 Oh Damn! I really forgot all my maths. Thanks for clarifying.
 » 2 years ago, # |   +4 oh god I understood C wrongly wasted 1 hour until I read it again it's way easier than what I was trying to solve :/ I will never read problems quickly again
• »
»
2 years ago, # ^ |
0

# MeToo

 » 2 years ago, # | ← Rev. 2 →   -80 [DELETED]
 » 2 years ago, # | ← Rev. 2 →   +23 Maybe, one day, Science will be able to answer why div2 coders like me keep on refereshing the standing page for 2+1/2 hours, even when they are done with the problems in 1/2 hour (-_-)
 » 2 years ago, # |   0 The strange thing that my rank keeps increasing if that i didn’t solve a problem after the first 40 min
 » 2 years ago, # |   +215 Yeahhh!!!
•  » » 2 years ago, # ^ |   -7 without taking part in the contest how did you solve A, B, C?
•  » » 2 years ago, # ^ |   0 i dont know how many times i saw this in 2018...hope to not see this in 2019 anymore
•  » » 2 years ago, # ^ |   +12 After 20 minutes: 3 accepts, 3 submitsAfter 3 hours: 3 accepts, 4 submits
 » 2 years ago, # | ← Rev. 3 →   +6 Please make me expert :|UPD: I became! <3
 » 2 years ago, # |   +7 How to solve D?
 » 2 years ago, # | ← Rev. 3 →   0 Does D uses the fact that number of divisors are number of ways to select powers of its prime factorization?
•  » » 2 years ago, # ^ |   0 Well given that N is up to 10^15, you can check the divisors of N in O( sqrt(N) )
 » 2 years ago, # |   +57 Hello 2̶0̶1̶9̶ depression.
 » 2 years ago, # |   +88 People being unable to solve D (at any points during contest time) be like: Got at least one failed submission -> damned. Solved ABC too slow -> damned. Cannot get proper hacks (mostly on B) -> damned. And I got the first and third case. Won't really blame (for a master, this performance of mine was way disappointing), but still, my point still stands. This contest is too unbalanced.I know, most Div.1+Div.2 combined recently look quite similar that way, but still, this one took the gap to the highest magnitude. Like, a single mistake is a suicidal sign.
•  » » 2 years ago, # ^ |   0 I got them all. C statement was not clear and wasted a lot of submissions on it.
•  » » 2 years ago, # ^ |   0 It may include misinterpreting the problem.
•  » » » 2 years ago, # ^ |   +4 Well, that would be the worst of any start of a year.
•  » » » » 2 years ago, # ^ |   0 I did that too (╥_╥)
 » 2 years ago, # |   0 In E is just greedy O(n logn sqrt(n)) passing?
•  » » 2 years ago, # ^ | ← Rev. 3 →   +33 If by greedy you mean remove the longest monotonic subsequence, then I got WA with this approach. It is known to achieve , but I can only construct cases in which I need , so there is something missing.
•  » » » 2 years ago, # ^ |   0 I found that N = k2 + k + 1 needs f(N) ≥ k + 1 and that f(6) = 3, so this is obviously not the exact bound, but it's very close to the other bound from Erdos-Szekeres.
•  » » 2 years ago, # ^ |   0 Solution is either greedily pick largest subsequence or split the whole sequence into the minimum amount of increasing or decreasing sequences.
 » 2 years ago, # |   +77 me.
•  » » 2 years ago, # ^ |   0 After A, B and C.For me, Hacking phase begin!!
 » 2 years ago, # |   0 problem D , what maximum number of divisors n can have ? and if less than 1e3 can we use dp ?
•  » » 2 years ago, # ^ |   +1 Maximum number of divisors of a 15-digit number is 26880: https://oeis.org/A066150
•  » » 2 years ago, # ^ |   +17 86642131736160025880 divisors
•  » » 2 years ago, # ^ |   +7 it is around 27k for 866421317361600
 » 2 years ago, # |   +42 How to solve F?
 » 2 years ago, # |   +20 ok fellas, how do we solve D?
•  » » 2 years ago, # ^ |   +50 There's a straightforeward dp solution. Compute all dp[i][j] = expected value if starting value is i and you have j turns. (i are all potential divisors of n).However this is too slow. You can speed it up, by realizing that this function is multiplicative. Therefore you compute dp[p^e][k] for each prime factor p of n and multiply the results.
•  » » » 2 years ago, # ^ |   0 How to find prime factors of n? I mean n is big and I couldn't find out whether n is prime or n is pq for some p and q being prime numbers.
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   +11 n isn't that big. In my case I simply computed all primes <= 4*10^7 using a sieve (which runs in <0.1 sec), and tried dividing n with all primes. But I also expect that a simple for loop until sqrt(n) will also be fast enough.
•  » » » » » 2 years ago, # ^ |   0 :(. I thought maybe 4 * 10^7 does not fit. Thanks.
•  » » » 2 years ago, # ^ |   +13 Can you elaborate a bit on proofs of this function being multiplicative? I don't really getting it mathematically.
•  » » » » 2 years ago, # ^ | ← Rev. 3 →   +23 Expected value of product of two independent random variables A and B is the product of their expected values.Proof for discrete A, B:(Here a and b are values that A and B can get.) P(A = a, B = b) = P(A = a)P(B = b) from definition of independence.At every step the power of every prime changes independently, since if our current number is y = x * pa, then the number of divisors of y where the power of p is a given value <= a is always just the number of divisors of x. Since all these probabilities are equal, they do not depend from x.Let A_{p,k} be a random variable indicating the value of the power of p after k steps. Our answer is since as we just saw Ap, k's are all independent
•  » » » » » 2 years ago, # ^ |   +1 sigh I'm just bad to not being able to draft this out.Thanks for the help, it's crystal clear to me! ;)
•  » » » » » 9 months ago, # ^ | ← Rev. 2 →   0 This is beautiful! Thanks!!!! This was a completely new fact to learn.
•  » » » » 2 years ago, # ^ | ← Rev. 7 →   +46 You can do a induction over k.For n = a·b and , and D(x) being the number of divisors of x.We have: Because of the induction hypothesis we know that dp(d1·d2, k - 1) = dp(d1, k - 1)·dp(d2, k - 1).Therefore:  = dp(a, k)·dp(b, k)
•  » » » » » 2 years ago, # ^ |   +3 This is exactly what I was searching for. Thank you so much!
•  » » » » » 2 years ago, # ^ |   +8 You mean: "dp(d1·d2, k - 1) = dp(d1, k-1)·dp(d2, k-1)." in the line after: "Because of the induction hypothesis we know that", correct?
•  » » » » » » 2 years ago, # ^ |   0 Yes
•  » » » » 2 years ago, # ^ |   +5 It's also possible to prove it by noticing that performing one step on n is equivalent to calculate s / c where s is the sum of divisors and c is the number of divisors. These functions are known to be multiplicative. From there, you can use induction.
 » 2 years ago, # |   +14 What's the intended complexity of E/G?I have O(Nsqrt(N)log(N)) in E (I hope it passes with some pruning) and a heavy O(NKlogK) in G (most probably it's too slow).
•  » » 2 years ago, # ^ |   0 I'm really curious about E. What's the threshold for f()?
•  » » » 2 years ago, # ^ |   +85 f(n) = 1 for [1, 2], 2 for [3, 5], [6, 9], [10, 14], [15, 20],  and so on.How to decompose a seqeunce of, for example, length [55, 65], into 10 parts? If the length of LIS is at least 11, remove it and repeat the process. Otherwise let dp[i] be the length of the LIS that ends at position i. Since there are at most 10 distinct values of dp[i] in this case we can decompose it into 10 parts (If we only look at elements with dp[i] = c for some constant c, this is decreasing.)
•  » » » » 2 years ago, # ^ |   +44 Yup. And we can consider the permutations of the following form: 1, 3, 2, 6, 5, 4, 10, 9, 8, 7(concatenated decreasing sequences of lengths 1, 2, ..., k). It's possible to prove that this permutation needs k subsequences in any partition.
•  » » 2 years ago, # ^ |   +10 We have in E. We came up with plenty of LIS implementations and even the slowest ones fit in a second or so.G can be solved in O(NK).
•  » » » 2 years ago, # ^ |   +10 So what was the intended solution? Because greedily picking the longest sequence seems to be O(N1.5logN) but gives WA.
•  » » » 2 years ago, # ^ |   0 Apparently my LIS implementation is exceptionally slow then.
 » 2 years ago, # |   +1 How to solve D? I could see that the expected value was a multiplicative function, but values for prime powers were not having a nice form either.
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 The expected value of f(n, k) is the product of f(aipi, k), where ai is a prime factor of n and pi is the maximum value such that aipi is the factor of n.
•  » » » 2 years ago, # ^ |   0 Yes, that is same as saying f is multiplicative. But how to compute f(a_i^p_i,k)?
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   0 Consider the naive DP approach to the original question. Denote dp[i][j] as the expected value when i replacements are done and the current value be j.Then for all t that is a factor of j, and n is the number of factors of j.The base case is dp[k][t] = t.Just use the same approach for each set of prime products, and of course you are not to use the values as indices.
•  » » 2 years ago, # ^ |   +3 You can just DP the values for prime powers
•  » » » 2 years ago, # ^ |   0 You mean using the recurrence, (a+2)f(p^(a+1),k) — (a+1)*f(p^a,k) = f(p^(a+1),k-1)? Wouldn't that be too slow?
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   +6 EDIT: fix one-off in indexingLet DP[i][j] = f(pi, j). We can init DP[i][0] = pi. Then, For all j from 1 to k,Calculating the values is trivial in O(nk) by precalculating the mod. inverses, and looping i up, keeping track of the sum.Our answer for this prime is just DP[n][k].
•  » » » » » 2 years ago, # ^ |   +10 I think you mean DP[s][j-1] on the right. It is the same as I have written. (i+2)*dp[i+1][j] — (i+1)*dp[i][j] = dp[i+1][j-1], if we keep track of the sum in your formula.
•  » » » 2 years ago, # ^ |   +10 Ok I see it may not be slow, since n has atmost log(n) prime factors, this will be done in less than log(n)*k*O(1) iterations
 » 2 years ago, # |   +7 Problem D, if n = 6 and k = 2 then why does 1 has 9 ways? I could just figure out 4 ways: 6 6 1 6 1 1 6 3 1 6 2 1
•  » » 2 years ago, # ^ |   +11 Probability for all of them is different!
•  » » 2 years ago, # ^ | ← Rev. 2 →   +4 You are not taking in account the probabilities. 6 6 1 — 1/4 * 1/4 = 1/166 1 1 — 1/4 * 1 = 1/46 3 1 — 1/4 * 1/2 = 1/86 2 1 — 1/4 * 1/2 = 1/8Sum = 9/16
•  » » » 2 years ago, # ^ |   +4 Oh, i forgot about the probality. Thank you
•  » » 2 years ago, # ^ |   0 For n=6 and k=2, 1 has only 4 ways.
 » 2 years ago, # | ← Rev. 3 →   -8 The system testing that's still pending but running at the same time and gives failed systest on A for everyone seems broken.UPD: Now it gives AC, but the rest is still wrong.UPD2: Now it's ok, but it said "system testing, standings frozen" for a while.
 » 2 years ago, # |   +1 Could someone please explain/provide a hint for solving D.
•  » » 2 years ago, # ^ |   0 Great Hint: In this problem E(XY) = E(X)E(Y),  gcd(X, Y) = 1.
•  » » 2 years ago, # ^ |   0 Not sure if this will get AC because I didn't manage to get it working in time but here goes: get divisors of n by looping from 1 to sqrt(n) (O(n^1/3) can be used for number of divisors) O(10^8) build directed graph with divisors as vertices and edges going from a number to its divisors O(10^10) use DP to calculate probabilities O(10^4*10^10)??
 » 2 years ago, # |   +21 never expected that bitset.count() is so fast. is it supposed to be O(N/128) or its constant is low like everything else in stl?
•  » » 2 years ago, # ^ |   0 I thought it's supposed to be O(1)
•  » » » 2 years ago, # ^ |   -7 In GCC it's O(N) (proof).
•  » » » » 2 years ago, # ^ | ← Rev. 3 →   0 Depends on flags. With -Ofast -march=native, it's O(1): godboltBitset .count()'s "complexity" then of course is n / 64 * O(__builtin_popcount()) = O(n / 64) (probably even faster due to vectorization)
•  » » » » 2 years ago, # ^ |   +18 I am not care about contribution, but it's anyway annoying to get downvotes for the correct answer for non-trivial question. Dear green's and lower, do you understand that with such behavior you demotivate people to give answers for questions and to share their experience? Imagine that once your question can be ignored because of that and you will be left alone with your problems.
 » 2 years ago, # |   0 What was wrong with the solutions to G that failed on test #4?
 » 2 years ago, # |   +51
 » 2 years ago, # |   0 Was it possible to do D without using the prime decomposition of N ? With a DP over its divisors
•  » » 2 years ago, # ^ |   +3 But when you know divisors, you know the prime decomposition too.
•  » » » 2 years ago, # ^ |   0 I meant without the optimisation involving the prime decomposition but I just saw its impossible I'm still wondering why the fonction is multiplicative
 » 2 years ago, # |   +12 Cool C and F. Awesome intro-statement for Um_nik problem.B bad for beginners, E with bad limits — it's terrible that many people come up with and thought it would be too slow (or: limits wouldn't be so tight then). G is quite standard, and H is tedious to implement.7/10, the contest could be better, but it was fine.
•  » » 2 years ago, # ^ |   +14 why is B bad for beginners?
•  » » » 2 years ago, # ^ |   -7 Implementation, zero thinking. And then there is a jump to much harder to solve problem C.It's very hard to choose good easy problems. I try to avoid bitmasks (or similar) for example, because some people might not know them. More or less, I remember times when I started programming and I try to invent such problems that are solvable by thinking for such a kid. In my easy problems, one of the best ones was: Given a graph with N, M <= 2000, count triangles (triples of pairwise connected vertices).
•  » » » » 2 years ago, # ^ |   0 Are you saying that it's too straightforward? Or that you need some knowledge to solve it?In my programming contest experience, iterating over subsets of a set (for example, using recursion or building the subsets iteratively) was one of the first things necessary for me to learn.
•  » » » » 2 years ago, # ^ |   0 Explicit bitmask is not required though: one can do the knapsack DP.
•  » » » » » 2 years ago, # ^ |   +8 Or O(2^n) recursion
•  » » 2 years ago, # ^ |   +31 How do you solve F? I figured bitsets would easily do queries 1,2,4 but spent over an hour unsuccessfully trying to work out a bitset solution that works with query 3.
•  » » » 2 years ago, # ^ |   +76 I stored bitset "is the number of elements divisible by x odd". The third operation is then just bitwise and.
•  » » » 2 years ago, # ^ |   +10 Yeah, bitsets work.Set bit i of set j to 1, if there is an odd amount of elements in the set divisible by i. Then join is xor, multiplication is and.
•  » » 2 years ago, # ^ |   +36 I think E is very cool (Though I agree that constraints should be lowered. I see no bad polynomial solutions).Is G really standard? For me O(NK2) or KlogK with FFT was quite standard, but then got stuck for like an hour to improve it (and still I have no idea).I don't like H neither, sorry.
•  » » » 2 years ago, # ^ |   +10 For G, I think you can improve the NK2 to NK + N / K * K2 by simply computing a subtree dp only up to the subtree size.
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 Well, in E there are some heuristics which use randomization. After guessing the function you can erase random LIS or LDS and if you've ended with too many sequences — repeat. I wanted to cut it.
•  » » » 2 years ago, # ^ |   +3 For G, you can get AC with O(NK2) solution. Example: 47935104.Polynomials multiplication is good for SIMD optimizations. And compiler can do all the work for you, if your code would be simple enough :)Check https://godbolt.org/z/2r_bdG for nice comparison of source and assembly codes. You may notice, that lines 95 and 90 (most nested part of source code) are assembled into operations with 256-bit registers (ymmD).
•  » » » » 2 years ago, # ^ |   +3 Yeah, but I don't like it when knowing how to write a fast solution to a contest problem, or knowing that some solution is fast, depends on knowledge of hardware features like SIMD or cache. It can even break problems where the author doesn't realise that some bruteforce can be very fast.
•  » » 2 years ago, # ^ |   -28 E in ? Radewoosh, go fuck yourself with such limitations.I would spend less time on this problem if I would code it right after coming up with solution.
•  » » » 2 years ago, # ^ |   +89 Hahaha, I really agree with you on expected complexity, however I think it would be great if he followed the footsteps of your iconic comment https://codeforces.com/blog/entry/49932?#comment-339270 and replied "Also, I've consciously chosen TL to fail people like Um_nik" or ""I would spend less time on this problem if I would code it right after coming up with solution." — that's exactly why you didn't get it accepted" :D
•  » » » » 2 years ago, # ^ |   +4 Goddamn, did you remember that comment for like 2 years? holy sheet.
•  » » » » » 2 years ago, # ^ |   +18 You would be surprised how my mind is capacious when it comes to anything related to competitive programming. We just really liked this comment so it stuck in our minds — probably many of you remember gags like sorry_dreamoon or notorious coincidence even though they were long ago as well.
 » 2 years ago, # | ← Rev. 2 →   -72 Dear CF, is it very cold there?Why are you freezing up?
 » 2 years ago, # |   0 How do you solve C? I tried my solution many times but it kept failing on test case 4.
•  » » 2 years ago, # ^ |   0 have u handled strings like )((( ?
 » 2 years ago, # |   0 what is hack for problem B?
•  » » 2 years ago, # ^ |   0 For example 6 179 179 179 179 2 6
•  » » 2 years ago, # ^ | ← Rev. 2 →   +9 I hacked with 4 170 160 150 120and with 5 170 160 150 140 100The answer to both should be YES.
•  » » » 2 years ago, # ^ |   0 how can we reach 0 in first test case?
•  » » » » 2 years ago, # ^ |   0 170 + 160 + 150 — 120 = 360 = 0
 » 2 years ago, # |   0 MikeMirzayanov During this contest I was unable to hack in Qutebrowser (version 1.1.1 based on Chromium 56.0.2924.122) and in Firefox (version 64.0). I was able to view the code, but when clicking Hack the input field for the hack didn't load and I only saw a spinning wheel. Only with my third browser, Chromium (version 71.0.3578.80), it worked.
 » 2 years ago, # |   +119 I'm sorry if this is not the right place to do it, but during the contest there was a participant in my room who obfuscated his code (as you can see here: 47912509). I couldn't find any report button so here I am. Is there anything that can be done? Thanks in advance!
 » 2 years ago, # | ← Rev. 2 →   0 In problem C, what's the answer for the case: 4(())(())The pairs 1 — 2 and 3 — 4 form the same bracket sequence (()). So the answer is 1 or 2?
•  » » 2 years ago, # ^ |   0 1 — 2 does not form a bracket sequence.
•  » » » 2 years ago, # ^ |   0 I fixed, sorry
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 If second string is ")" answer is 1. If second string is "))" answer is 2. You don't care if some pairs form the same bracket sequence.
•  » » » 2 years ago, # ^ |   +1 "The task is to connect some of them into ordered pairs so that each bracket sequence occurs in at most one pair"Reading this i think that each bracket (form by a pair) has to be unique. In this way the problem became significantly harde.
•  » » » » 2 years ago, # ^ |   +3 When it says "each bracket sequence occurs in at most one pair" does not mean that the result should appear once. Means that you can pick every element and add it to one unique pair and not to multiples.
•  » » 2 years ago, # ^ |   +3 Ans:2 we need the highest number of pairs of correct sequence. No need for finding unique sequence of the pairs.
 » 2 years ago, # | ← Rev. 6 →   0 Problem D :dp[n][k] = (1/x)*dp[divisor_1][k-1]             + (1/x)*dp[divisor_2][k-1]             + ..... + (1/x)*dp[divisor_x][k-1]. Here x = number of divisor of n.dp[n][k] will be like this for example : dp[4][1] = {1*(1/4) , 2*(1/4) , 4*(1/4)}. and so on. PS : Here one optimization is instead of taking divisor as dp state we can take divisor count as first dp state as only number of divisor matters for expectation.For example 4 will have 3 divisor and so does 9.dp[4][1] = {1*(1/3), 2*(1/3), 4*(1/3)}dp[9][1] = {1*(1/3), 3*(1/3), 9*(1/3)}We only need to count dp[3][k] -> here 3 is count of the divisor and not number it self.
 » 2 years ago, # | ← Rev. 2 →   0 for F its my solution of F 47939459 get MLE, but any other AC solution's memory (bitset <7001> bs[1e5+1]) just like my solution, whats wrong with my solution?
•  » » 2 years ago, # ^ |   +3 I assume you mean problem F (not G).Your int gc[7001][7001]; takes ~186.97 MiB, and bitset <7001> bs[100001]` takes ~83.54 MiB (these figures are not exact). Summing up, they take ~270.52 MiB. Sorry to hear that.
•  » » » 2 years ago, # ^ |   0 Tnx
 » 2 years ago, # |   0 20 minutes delay on a problem --> 1000 positions in the standings. Gotta love this difficulty distribution.
 » 2 years ago, # |   +34 When you solve A,B,C and your C get runtime because your vector size is 1e5, but need 5e5
•  » » 2 years ago, # ^ |   +3 Exactly.
 » 2 years ago, # |   0 Wow, Editorial has been set before the contest. Thanks!!
 » 2 years ago, # |   +3 Can someone help me with the Problem C? my submission1 failed, I changed unordered_map to map, and instead of for(auto x: m), I used an iterator to loop, The solution is accepted. I couldn't figure out what was the issue I had?Submission1Submission2
•  » » 2 years ago, # ^ |   0 int b = m[-1*x.first]; This one potentially changes the map (if key -1*x.first wasn't in the map). Which breaks iteration over it (if it's unordered_map).Spend 2 hours debugging same issue :(
•  » » » 2 years ago, # ^ |   0 Thanks, I created a blog for this before checking your reply, btw it (unordered map) was passing with clang++17 diagnostics. Do you have any idea why is it so?
•  » » » » 2 years ago, # ^ |   0 Well, I don't think clang++17 diagnostics (or any automatic tool) can catch all possible bugs in the code.
 » 2 years ago, # | ← Rev. 3 →