ko_osaga's blog

Yosupo Judge Stream: Implementing Subquadratic Directed MST
By ko_osaga, history, 4 years ago, In English

Hi! Tomorrow at 21:00 KST I will stream solving judge.yosupo.jp. In the stream, I will try to implement Edmond's Directed MST algorithm with this lecture note.

I will solve the following problems in the stream. Recommendations are welcome, preferably ones that's not just "Find Directed MST".

Spoiler

Since this is not a regular data structure stream, I will keep it short. The stream will last about 3 hours.

This event isn't that well-prepared like others, please don't expect too much :)

Thanks!

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ko_osaga (previous revision, new revision, compare).

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

Joyful Party

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

    I remember this problem! That's actually the most interesting problem with arborescence that I've ever seen.

    The subquadratic algorithm for arborescence is very trivial, so it is sad that problems with it are not so common.

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

This was fun, any plans for another stream?

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

    Thanks for enjoying! Not soon, because I have a lot of stuffs to do until the year-end. I will try my best to do the Data structure stream for New Year Prime Contest :)

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

Unfortunately, it wasn't trivial for me unlike 300iq, so it took 4 hours to finish.

Thank you for watching!

→ Reply