Aksenov239's blog

By Aksenov239, 3 weeks ago, translation, In English

Hello Codeforces!

My name is Vitaly Aksenov and I present you the new lesson in English EDU section as a part of "ITMO Academy: pilot course". I will talk about Disjoint Sets Union (DSU).

A little bit about myself, I cannot brag about being red (International Grandmaster), however, I was twice and each time afterwards there was a revolution of colours on Codeforces. :-) Right now I am the Researcher in ITMO University in parallel and distributed computing (link). Also, I am in Jury Committee of several olympiads such as NERC, Bioinformatics Contest, Russian Code Cup and etc.

This is my first time to write a lecture so do not judge harshly. I hope you will like it!

I want to thank pashka for video editing, and thanks to pashka, MikeMirzayanov and niyaznigmatul for sharing the problems.

Go to EDU →

More about EDU section you can read in this post.

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

»
3 weeks ago, # |
  Vote: I like it -50 Vote: I do not like it

In the image in the blog, it looks like your face was photoshopped on to someone else xD.

Great video though! I have always found DSU to be one thing that was super cool and easy to understand. Needed a great video to recommend to others.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it -35 Vote: I do not like it

    Why does this comment has so much negative votes ?

»
3 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

You can brag about it. Most of our Professors don't even know what Codeforces is.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +55 Vote: I do not like it

    In my opinion, they don't need to. (Competitive Programming is a mind sport, and not a measure of competency of Computer Science professors.)

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      What if the Professors teach you DSA? I think they should know atleast implementation of basic topics and their modifications which they don't, atleast in my college/country. Just imagine if a grandmaster(on CF) teaches us DSA in college.

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it +7 Vote: I do not like it

        Unrelated but I saw my friend's DSA teacher buying a course on DSA from a private coaching institute where he himself teaches the course on DSA. Just imagine the irony that you would be teaching your teacher in the evening on the subject she teaches you in the morning xD

»
3 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it

I ve always wanted to join cp but couldn't find time for the huuuuge research one should do to get some simple techniques from the internet jungle. But now with these great lessons, I didn't just improve my algorithmic skills but also my self-confidence for further effort is toooo daaamn high! big thanks for everyone working on these series. I hope one day I can be helpful for the community too.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    this kind of comment is probably also what motivates the authors of these lessons :) so that's pretty amazing

»
3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Please give subtitles in English Aksenov239

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Unfortunately, they are not available. It is timeconsuming to make them. I think we will try to do something about that.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      I think you can upload the video on YouTube and make it private. Google automatically generates subtitles for the videos in 1-2 days. Then you may download the video and upload it here. I don't know if it is allowed or not, but it can be used as a hack. Reference: Link

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the video.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

The video is great. Thanks a lot, Aksenov239 and ITMO!

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

watting for db :)

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

As far as I understand, Node.js supports WebAssembly. C++ code can be compiled to WebAssembly with Emscripten. While WebAssembly is noticeably slower than native C++, Node.js has a 3x time limit multiplier here. Does this mean I can compile my C++ submissions (that use the correct algorithm, but are implemented inefficiently and get TLE) to Javascript to increase their "performance"?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

If you want more people to watch your instructional videos, you can try to increase your rating. On codeforces. People can't quickly know your other abilities, the only thing that can quickly know is your rating. If you have a higher rating. I believe there will be more people watching your video.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks Aksenov239 for sharing this.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks ..This is very helpful...

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice explanation

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the video.

»
2 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

Please check here for an in-depth explanation https://cp-algorithms.com/data_structures/disjoint_set_union.html

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Aksenov239, Can we have the expected time complexities in the practice problems?

For example, in this problem my naive $$$O(m^2)$$$ solution runs in 124ms which is well under the TL.

But I think there would be faster approaches with better time complexities. Reasearching whether my solution is optimal is so hard and with sorting solutions by runtime disabled its even harder.

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

    No worries, for that problem $$$O(m^2)$$$ is good enough and is the expected complexity. :-)

»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

A great feature that can be added is to make these videos downloadable, so we can download these and watch it without buffering on high quality anytime, anywhere.