Radewoosh's blog

Hello 2019
By Radewoosh, history, 6 years ago, In English

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.
  • mnbvmar for indescribably helpful discussions about problems.
  • 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!

  1. V--o_o--V
  2. ecnerwala
  3. tourist
  4. lych_cys
  5. Petr

And to the first-to-solvers!

UPD7: Editorial

  • Vote: I like it
  • +1910
  • Vote: I do not like it

Comments Comments (335)
| Write comment?
»
6 years ago, # |
  Vote: I like it +550 Vote: I do not like it

You accidentally uploaded the ediotiral, but i am honest and don't look there

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +453 Vote: I do not like it

    Well, thanks for that, but you shouldn't worry so much :P

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -12 Vote: I do not like it

    you changed your handle from numb. So many quora links are gonna be dead now

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I have seen a new name in my friend list and wondering about who is this guy... Finally I understood...

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +17 Vote: I do not like it

      If you change your handle the links refered to the lastwill redirect to the new profile page

      → Reply
»
6 years ago, # |
  Vote: I like it +22 Vote: I do not like it

Nice editorial tho.

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

I can neither confirm nor deny that editorial without Radewoosh's approval

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it -225 Vote: I do not like it

lol

→ Reply
»
6 years ago, # |
  Vote: I like it +44 Vote: I do not like it

That editorial, haha, so funny!

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it +70 Vote: I do not like it

this.handle+" 2019!";

→ Reply
»
6 years ago, # |
  Vote: I like it +239 Vote: I do not like it

Thanks for fast editorial.

→ Reply
»
6 years ago, # |
  Vote: I like it +90 Vote: I do not like it

I really hope noone is enjoying the New Year as much as you.

→ Reply
»
6 years ago, # |
  Vote: I like it +228 Vote: I do not like it

Can you please reupload the editorial? It is not available in my country and now I feel at disadvantage.

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it -24 Vote: I do not like it

One of the best editorials ever seen. Nice one.. Haha:P

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it -10 Vote: I do not like it

Why aren't you blue anymore? Also, what is the blog gonna look like when you upload the real editorial?

→ Reply
»
6 years ago, # |
  Vote: I like it +10 Vote: I do not like it

too excited about the first contest in this year and as well as a contest by Radewoosh.

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Awesome editorial! :P

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it -27 Vote: I do not like it

-

→ Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

By the way, why isn't the Rating of the problems in Goodbye 2018 shown yet?

→ Reply
»
6 years ago, # |
  Vote: I like it +24 Vote: I do not like it

could you explain in more detail div2a? including official solutions also helps.

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Nice editorial :P

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it -30 Vote: I do not like it

LOL HAHABA SHIT JOKE=))))

→ Reply
»
6 years ago, # |
  Vote: I like it +184 Vote: I do not like it

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::::;;,,
→ Reply
»
6 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Your editorial sucks! The video isn't available in my country!

→ Reply
»
6 years ago, # |
  Vote: I like it +173 Vote: I do not like it

memerickcf

→ Reply
»
6 years ago, # |
  Vote: I like it +63 Vote: I do not like it

clicked on the Editorial

Really Radewoosh? Thanks for being the first one doing that to me in 2019 :D

→ Reply
»
6 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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 :)

→ Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Looking forward to it, hopefully I will finally become green again :P

→ Reply
»
6 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Not gonna lie, I thought I badly missed the contest..

Until I swiped left my mobile screen..

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I've been looking forward to a round prepared by a single expert, but, however..

→ Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

wulalalala is it rated?

→ Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

what is the rating of the contest ?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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.

    → Reply
»
6 years ago, # |
  Vote: I like it +46 Vote: I do not like it

Fastest editorial in my codeforces history. Thanks Radewoosh

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Well-written editorial ^^ but I think you forgot to link the statements that go with it :\

→ Reply
»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Hello

→ Reply
»
6 years ago, # |
  Vote: I like it +12 Vote: I do not like it

I've already read so many editorials that I know this gXcQ by heart.

→ Reply
»
6 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Fastest editorial ever!!! Also that's one of my favorite songs to cheer me up too.

→ Reply
»
6 years ago, # |
  Vote: I like it +28 Vote: I do not like it

Is it just me, or does Radewoosh look really similar to Rick? o.O
Radewoosh vs Rick

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Never gonna give you uuuup! I like this editorial :)

→ Reply
»
6 years ago, # |
  Vote: I like it +20 Vote: I do not like it

How to solve D ?

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Exceptional Editorial :P

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Wow, early editorial. When are you gonna update the ratings?!.

→ Reply
»
6 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Goodbye 2017;Hello 2018.:D

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm gonna listen to this editorial everyday

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the video editorial , really educational !

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Just hope, everyone has high ratings with this new year. Tough competition though :P

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

OMG, Radewoosh contribution +200. That`s so much!

→ Reply
»
6 years ago, # |
  Vote: I like it +45 Vote: I do not like it

Fuck U Radewoosh.My New Year Resolution was not to Open Youtube(Personal Reason).And Bcoz of u it is broken now.

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

this will get me out of master :^D

→ Reply
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Everyone says that he hopes to be green, gray and other color. I hope to become Double Legendary Grandmaster SuperJava

→ Reply
»
6 years ago, # |
  Vote: I like it -21 Vote: I do not like it

Is it rated??

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

ArepitaDePernil will never tell a lie and hurt you!!

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope to reach green this contest :)

→ Reply
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

it would be cool if pressing the downvote button would also redirect u to smth funny

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Lets see if this post gets more upvotes than Hello 2018. Radewoosh you are my favorite.

→ Reply
»
6 years ago, # |
← Rev. 5   Vote: I like it +6 Vote: I do not like it

I think that the set of people will be: tourist Petr Radewoosh Um_nik rng_58 OO0OOO00O0OOO0O0…O PikMike Vovuh

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

UPD3 challenge: tourist, Radewoosh, OO0OOO00O0OOO0O00OOO0OO, Um_nik, V--o_o--V, LHiC, Petr, encerwala

→ Reply
»
6 years ago, # |
  Vote: I like it -24 Vote: I do not like it

UPD2: I'll be on the Discord channel after the contest, so you will be able to ask me about the problems
I can't enter the server ((

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +302 Vote: I do not like it

Egor it was very tricky from you to hide on 158th place in overall standings with these 11 wins of yours :P

Petr tourist Radewoosh jqdai0815 Um_nik rng_58 V--o_o--V Egor — be aware that Radewoosh invites you to take part in this contest :)

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +65 Vote: I do not like it

    And we have a winner!

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    Seems cool, he's just after tourist and Petr, not sure about OO0OOO00O0OOO0O00OOO0OO, but all in all, 11 is too much!!!

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    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.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Radewoosh invites himself to take part in his own contest? :thinking:

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +36 Vote: I do not like it

    includes unofficial participation

    gimme some of the left over contribution

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +81 Vote: I do not like it

    Anyone wants to create Codeforces version of this?

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      Something like this?

      Link

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Thank you, looks nice :)

        Maybe we shouldn't mix d1/combined matches and d2/d3/unrated matches?

        → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +86 Vote: I do not like it

    Only reason I failed last several rounds is to deceive everyone in anticipation of this

    → Reply
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I just want to tag dreamoon_love_AA sorry_dreamoon :P.

→ Reply
»
6 years ago, # |
  Vote: I like it +15 Vote: I do not like it

In UPD 3 , I think they are (in sorted order from number of contests winning)

1 — tourist

2 — Petr

3 — OO0OOO00O0OOO0O00OOO0OO

4 — rng_58

5 — Egor

6 — Um_nik

7 — V--o_o--V

8 — Radewoosh

9 — YuukaKazami

and since you said that you invite first 8 to take part in contest...so I think that maybe you mean 9th which is YuukaKazami

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +52 Vote: I do not like it

    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.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I cant understand the editorial, anybody can explain with more details? :D

→ Reply
»
6 years ago, # |
  Vote: I like it +42 Vote: I do not like it

It sure will be the best 2019 contest so far.

→ Reply
»
6 years ago, # |
  Vote: I like it +40 Vote: I do not like it

Change the start time to 20:19 ! :D

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Taking part in a contest begins at 22:35(UTC+8) is usual for me now, but if it lasts for 3 hours...

    → Reply
»
6 years ago, # |
  Vote: I like it +14 Vote: I do not like it

I hope there won't be solutions in the problems.

→ Reply
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Even Problems In an Odd Year will Make My Day !!!

→ Reply
»
6 years ago, # |
  Vote: I like it +2 Vote: I do not like it

One of the Best Editorial ever.

Thanks for the Motivation.

Another Editorial if you wanna take a look.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

finally.. someone generous. Three hours !

→ Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Really enjoyed this editorial.

→ Reply
»
6 years ago, # |
  Vote: I like it +13 Vote: I do not like it

If you can't see the editorial, you can try this. It's the same video.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The 8 people will not includes OO0OOO00O0OOO0O00OOO0OO because it's too hard to write.

QAQ

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Outrageous editorial!

→ Reply
»
6 years ago, # |
  Vote: I like it -68 Vote: I do not like it

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!

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +17 Vote: I do not like it

      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?

      → Reply
»
6 years ago, # |
  Vote: I like it +22 Vote: I do not like it

PM 11:30 to AM 02:30 in my country 8ㅅ8

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +78 Vote: I do not like it

Adjusted drain, please. Nobody wants their C-D to be worth more than G-H.

@ MikeMirzayanov, cdkrot, KAN

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +44 Vote: I do not like it

    Pls pls pls!!! It lasts 3 hours (not 2.5), so it is even more important!

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    it is adjusted

    → Reply
»
6 years ago, # |
  Vote: I like it +15 Vote: I do not like it

I Have a Farsi exam tomorrow, I know Im going to fail but F*** that, I waited a year for this.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Very exclusive tutorial.Following the tutorial most of the contestant including me become legendary grandmaster without participating any contest :D

→ Reply
»
6 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Never gonna give you up =))

→ Reply
»
6 years ago, # |
  Vote: I like it +88 Vote: I do not like it

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +43 Vote: I do not like it

Score distribution? Updated Now

→ Reply
»
6 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Good luck to all! Wish you to see lot of "Happy New Year!" verdict!

→ Reply
»
6 years ago, # |
← Rev. 4   Vote: I like it +1 Vote: I do not like it

Before start, delayed by 10 mins :|

→ Reply
»
6 years ago, # |
  Vote: I like it +17 Vote: I do not like it

why delay 10 min ?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

    Finally my time travel machine worked, I moved everyone 10 minutes in the past

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

10 minutes delay means now I will skip the last 30 minutes of the round, not a good thing :(

→ Reply
»
6 years ago, # |
  Vote: I like it +22 Vote: I do not like it

PING : 600000ms

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I'm confused because the contest was suddenly delayed a few seconds before the start of the competition.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

JEBAITED XD

→ Reply
»
6 years ago, # |
  Vote: I like it -6 Vote: I do not like it

Is it another DDOS attack???

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    Maybe expecting more participation, I guess.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What an Anti-Climax (Delayed by 10 mins)

→ Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

There should be a notification when a contest is delayed. We press OK and suddenly get shocked to see delay :/

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it +34 Vote: I do not like it

Radewoosh, You want to crack the 12K record?

→ Reply
»
6 years ago, # |
  Vote: I like it -13 Vote: I do not like it

UDP5 : 10 min delay.

→ Reply
»
6 years ago, # |
  Vote: I like it +38 Vote: I do not like it

Trying to get 12k registrants and beat Goodbye 2018 with that delay? haha

→ Reply
»
6 years ago, # |
  Vote: I like it +9 Vote: I do not like it

I think the delay was for beating the record for the most registered people in a contest.

→ Reply
»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

About +600 participants. Good luck :)

→ Reply
»
6 years ago, # |
  Vote: I like it +16 Vote: I do not like it

It's great idea from you to put a link to your song in the blog, nice advertisement man

→ Reply
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Starting new year with 10 minutes delayed contest, it gonna be legen wait for it dary year.

→ Reply
»
6 years ago, # |
  Vote: I like it +46 Vote: I do not like it

Task C

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +118 Vote: I do not like it 
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
→ Reply
»
6 years ago, # |
  Vote: I like it -30 Vote: I do not like it

What is TC4 of Prob C?

→ Reply
»
6 years ago, # |
  Vote: I like it +129 Vote: I do not like it

Radewoosh unbalanced contest

→ Reply
»
6 years ago, # |
  Vote: I like it +97 Vote: I do not like it

Why does E have only 1 correct submission? Overkill or wrong official solution?

→ Reply
»
6 years ago, # |
  Vote: I like it +185 Vote: I do not like it

For Div-2 Coders, it was a 1/2 hour contest.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

very funny statements

→ Reply
»
6 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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

    → Reply
»
6 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it -80 Vote: I do not like it

[DELETED]

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +23 Vote: I do not like it

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 (-_-)

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The strange thing that my rank keeps increasing if that i didn’t solve a problem after the first 40 min

→ Reply
»
6 years ago, # |
  Vote: I like it +215 Vote: I do not like it


Yeahhh!!!

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

    without taking part in the contest how did you solve A, B, C?

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i dont know how many times i saw this in 2018...

    hope to not see this in 2019 anymore

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    After 20 minutes: 3 accepts, 3 submits

    After 3 hours: 3 accepts, 4 submits

    → Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it +6 Vote: I do not like it

Please make me expert :|
UPD: I became! <3

→ Reply
»
6 years ago, # |
  Vote: I like it +7 Vote: I do not like it

How to solve D?

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Does D uses the fact that number of divisors are number of ways to select powers of its prime factorization?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Well given that N is up to 10^15, you can check the divisors of N in O( sqrt(N) )

    → Reply
»
6 years ago, # |
  Vote: I like it +57 Vote: I do not like it

Hello 2̶0̶1̶9̶ depression.

→ Reply
»
6 years ago, # |
  Vote: I like it +88 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I got them all. C statement was not clear and wasted a lot of submissions on it.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It may include misinterpreting the problem.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      Well, that would be the worst of any start of a year.

      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In E is just greedy O(n logn sqrt(n)) passing?

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 3   Vote: I like it +33 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Solution is either greedily pick largest subsequence or split the whole sequence into the minimum amount of increasing or decreasing sequences.

    → Reply
»
6 years ago, # |
  Vote: I like it +77 Vote: I do not like it

2o50s2

me.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

problem D , what maximum number of divisors n can have ? and if less than 1e3 can we use dp ?

→ Reply
»
6 years ago, # |
  Vote: I like it +42 Vote: I do not like it

How to solve F?

→ Reply
»
6 years ago, # |
  Vote: I like it +20 Vote: I do not like it

ok fellas, how do we solve D?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +50 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 2   Vote: I like it +11 Vote: I do not like it

        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.

        → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      Can you elaborate a bit on proofs of this function being multiplicative? I don't really getting it mathematically.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 3   Vote: I like it +23 Vote: I do not like it

        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

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          sigh I'm just bad to not being able to draft this out.
          Thanks for the help, it's crystal clear to me! ;)

          → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          This is beautiful! Thanks!!!! This was a completely new fact to learn.

          → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 7   Vote: I like it +46 Vote: I do not like it

        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)
        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          This is exactly what I was searching for. Thank you so much!

          → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          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?

          → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        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.

        → Reply
»
6 years ago, # |
  Vote: I like it +14 Vote: I do not like it

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).

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I'm really curious about E. What's the threshold for f()?

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +85 Vote: I do not like it

      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.)

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +44 Vote: I do not like it

        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.

        → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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).

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      So what was the intended solution? Because greedily picking the longest sequence seems to be O(N1.5logN) but gives WA.

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Apparently my LIS implementation is exceptionally slow then.

      → Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, that is same as saying f is multiplicative. But how to compute f(a_i^p_i,k)?

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    You can just DP the values for prime powers

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 2   Vote: I like it +6 Vote: I do not like it

        EDIT: fix one-off in indexing

        Let 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].

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it +10 Vote: I do not like it

          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.

          → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      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

      → Reply
»
6 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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
→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Probability for all of them is different!

    → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +4 Vote: I do not like it

    You are not taking in account the probabilities.

    6 6 1 — 1/4 * 1/4 = 1/16
    6 1 1 — 1/4 * 1 = 1/4
    6 3 1 — 1/4 * 1/2 = 1/8
    6 2 1 — 1/4 * 1/2 = 1/8
    Sum = 9/16

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      Oh, i forgot about the probality. Thank you

      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For n=6 and k=2, 1 has only 4 ways.

    → Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it -8 Vote: I do not like it

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.

→ Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Could someone please explain/provide a hint for solving D.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Great Hint: In this problem E(XY) = E(X)E(Y),  gcd(X, Y) = 1.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Not sure if this will get AC because I didn't manage to get it working in time but here goes:

    1. 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)

    2. build directed graph with divisors as vertices and edges going from a number to its divisors O(10^10)

    3. use DP to calculate probabilities O(10^4*10^10)??

    → Reply
»
6 years ago, # |
  Vote: I like it +21 Vote: I do not like it

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?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I thought it's supposed to be O(1)

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it -7 Vote: I do not like it

      In GCC it's O(N) (proof).

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        Depends on flags. With -Ofast -march=native, it's O(1): godbolt

        Bitset .count()'s "complexity" then of course is n / 64 * O(__builtin_popcount()) = O(n / 64) (probably even faster due to vectorization)

        → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +18 Vote: I do not like it

        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.

        → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What was wrong with the solutions to G that failed on test #4?

→ Reply
»
6 years ago, # |
  Vote: I like it +51 Vote: I do not like it

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Was it possible to do D without using the prime decomposition of N ? With a DP over its divisors

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    But when you know divisors, you know the prime decomposition too.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I meant without the optimisation involving the prime decomposition but I just saw its impossible I'm still wondering why the fonction is multiplicative

      → Reply
»
6 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    why is B bad for beginners?

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it -7 Vote: I do not like it

      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).

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Explicit bitmask is not required though: one can do the knapsack DP.

        → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +76 Vote: I do not like it

      I stored bitset "is the number of elements divisible by x odd". The third operation is then just bitwise and.

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      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.

      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +36 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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).

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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.

        → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -28 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +89 Vote: I do not like it

      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.me/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

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        Goddamn, did you remember that comment for like 2 years? holy sheet.

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it +18 Vote: I do not like it

          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.

          → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How do you solve C? I tried my solution many times but it kept failing on test case 4.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

what is hack for problem B?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For example 6 179 179 179 179 2 6

    → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +9 Vote: I do not like it

    I hacked with

    4
170 160 150 120

    and with

    5
170 160 150 140 100

    The answer to both should be YES.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      how can we reach 0 in first test case?

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        170 + 160 + 150 — 120 = 360 = 0

        → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
6 years ago, # |
  Vote: I like it +119 Vote: I do not like it

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!

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    1 — 2 does not form a bracket sequence.

    → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      "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.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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.

        → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Ans:2 we need the highest number of pairs of correct sequence. No need for finding unique sequence of the pairs.

    → Reply
»
6 years ago, # |
← Rev. 6   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

20 minutes delay on a problem --> 1000 positions in the standings. Gotta love this difficulty distribution.

→ Reply
»
6 years ago, # |
  Vote: I like it +34 Vote: I do not like it

When you solve A,B,C and your C get runtime because your vector size is 1e5, but need 5e5

→ Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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?

Submission1

Submission2

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 :(

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Well, I don't think clang++17 diagnostics (or any automatic tool) can catch all possible bugs in the code.

        → Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it +130 Vote: I do not like it

My screencast will be available here: https://youtu.be/UxtEMlc0sHM , including getting problem H correct 30 seconds after the end of the contest (just checked in upsolving), which would be just enough for the first place :) Oh well.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    quality is 360 , couldn't see anything .. blurred . increase the quality to 480 or 720 Petr

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Wait for the video to render...

      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

So why THe function Expectation of D is Multiplicative ?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    E(XY)=E(X)E(Y) if X, Y are independent random variables.

    → Reply
»
6 years ago, # |
  Vote: I like it +19 Vote: I do not like it

What happened to CF-Predictor?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Probably too many F5's.

    Apparently it runs in a free heroku instance, so it might have reached its maximum traffic allowance or something like that.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah I too thought of the same, thanks :)

      → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it -7 Vote: I do not like it

That was a nice contest but i love that editorial.

→ Reply
»
6 years ago, # |
  Vote: I like it +32 Vote: I do not like it

and where is real editorials ?)

→ Reply
»
6 years ago, # |
  Vote: I like it -136 Vote: I do not like it

Probably the worst combined round in Codeforces history, imbalanced and not interesting problems, didnt expect it from Radewoosh

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +32 Vote: I do not like it

    At least problems E and F had really nice solutions, G and H looks interesting. Maybe balance wasn't the best, but it's really hard to balance contest correctly and it happens in 80% of contests.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Sorry, but I can't find "hack it!" button on anyone's solution. What it might be? Tried already in Chrome and Edge.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve c?

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    There are 3 cases. The first one is when both of sequences are valid. They are valid, if stack is empty in the end(read about correct bracket sequence). To solve other two cases we have to calculate count of needed brackets in our invalid sequence. For example: (()( to "close" it we need two brackets like ")". Lets define it as need_right. It was the second case. The last one is need_left, i.e. count of brackets needed to "close" for example, this guy )(), need only one from left. It is easy to notice, it's impossible to make our sequence correct, if there is a sequence, that needs brackets from both sides, like )(. So, just push these values into two vectors, sort them and get your answer.

    → Reply
»
6 years ago, # |
  Vote: I like it +49 Vote: I do not like it

real editorial would be nice

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Plot twist: that is the real editorial.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How to solve problems A-H: Never Give [the problem] Up

      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

problem F: bitset pleeeease

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

LOL

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi. Can someone explain problem B? Is it well-known algorithm that everyone used?

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 5   Vote: I like it +5 Vote: I do not like it

    notice that n <= 15 if n = 15 you will have 2^15 combinations which is small. You can thus try all combinations (at each step, you can either rotate clockwise(add to the current angle) or counterclockwise(subtract from the current angle)). This is very similar to subset sum problem but here you don't have to use DP because n is small. That screams recursion.

    Recursive solution: https://pastebin.com/k6AwE2ur .

    It could be also solved without recursion like this: iterate over all 2^n combinations like this:

    for(int mask = 0 ; mask < 2 ^ n ; mask++){

}

    For each mask, iterate over all elements in the array. The current mask describes the state. For example if mask's binary notation is 10111 means that try this combination: *rotate clockwise the 1st,3rd,4th, and 5th elements(clockwise) (positions with 1s). *rotate the second angle counterclockwise (positions with 0). At each state, compute the final angle(adding when bit is 1 subtracting when 0) and check if final angle % 360 = 0.

    iterative solution: https://pastebin.com/F9y9vM75

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D, how 15/8(mod 10^9+7) = 875000008 can anyone explain to me how to calculate this? thanks

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    According to Euler's theorem if p is prime and n is not a multiple of p then n^(p-1) = 1 [p] Thus n^-1=n^(p-2) and here 10^9+7 is a prime number

    → Reply
»
6 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Can we now have the actual editorial please?

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +23 Vote: I do not like it

Where did my rating go?
Radewoosh?

→ Reply
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

What happend

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve B.i am new at programming.please help

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Just think in trying all versions (if you turn wheel by a[i] to the right (ans+a[i]) or to the left (ans-a[i]) ). Then check if any of final answers is divisible by 360 (because then it is on 0). Complexity is O(2^n) and on worst case n=15, so it passes time limit.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anyone here have successfully solved problem C??? I'm just a kiddo and I am new to coding please help meee I just can't have the faintest notio of it. T.T thanks if u can help

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can divide all the brackets sequence into 4 cases

    1. Perfect sequence
    2. Sequence that lack X leading '(' but no excess '('
    3. Sequence that has Y excess '(' but does not lack any leading '('
    4. Sequence that lack both Z opening '(' and ZZ following ')'

    For case 4 it's obvious that you can not make a 'pair' out of it because it needs at least 2 more sequence to complete it.

    For case 1 it must match with another case 1 sequence (Perfect+Perfect)

    For case 2 and 3 we just need to match the sequences that X = Y

    How to find the answer I'll left as exercise :p

    PS. Just a reminder(I think you know this already). To find the case you cannot just take number of '(' — number of ')'. For example, ')(' is not case 1 , but a case 4 because it lack 1 opening and have 1 excess. '(()' is case 3 with Y=1. '())' is case 2 with X=1.

    → Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

[DELETED]

→ Reply
»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

D/E is very cool. Thank you!

→ Reply
»
6 years ago, # |
  Vote: I like it +24 Vote: I do not like it

Suddenly screencast

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

After some searching on codeforces, I found who are Gennady, Petr, Makoto, Egor, Alex, Vladislav and Mateusz. But who on earth is Yuhao on problem C?

→ Reply
»
6 years ago, # |
  Vote: I like it +13 Vote: I do not like it

A round with two editorials emmm

→ Reply
»
6 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Please remove the UPD1 editorial now as the contest is already over and so is the fun of the click-bait. Now it just creates confusion.

→ Reply
»
6 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Why are there two editorials and first one directs me to some singing guy?

→ Reply
»
6 years ago, # |
  Vote: I like it -11 Vote: I do not like it

I got WR in problem C with this code using unordered_map 47928656 but I got AC After the contest using map in the same code 47970451 . what the different between them ?? Radewoosh MikeMirzayanov...

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +27 Vote: I do not like it

    I'm not really sure about it, but it seems that modifying the unordered map while iterating it is a bad idea and can lead to the undefined behavior.

    Why? Here: mp[it.first] = mp[it.first*-1] = 0; you can accidentally insert new keys to the hashmap (which can happen e.g. when key 5 exists in the map, but -5 does not). This can lead to the rehashing of the hashmap (the hashmap rebuilds from scratch if the number of elements in it is too large compared to its current capacity). Yet, the range loop in fact takes an iterator to the hashmap and advances it over and over again. Now the hashmap can be somewhere else in memory, and you're trying to iterate over the hashmap (which might be already gone...)

    Same story can happen with vectors: https://ideone.com/ds4Rkp. (WTF, why are there zeroes in the output?)

    → Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I wrote a tutorial of problem G. https://codeforces.me/blog/entry/64367

→ Reply