Hi!

In the new video, we’re going to talk about the amazing data structure called Segment Tree Beats, which allows us to support a huge number of operations that a regular segment tree can’t handle. We will learn how to take numbers on a segment modulo some number, apply the min= and max= operations, add += to them, and also find GCD on a segment with these operations. And all the proofs are gonna be super simple, so don’t be scared, it will be easy! In the next video, we will cover even more awesome queries, so stay tuned.

Link to the video

You can check out my previous videos on my channel

Contest on Segment Tree Beats (and others) is here

Also, there's the Russian version of this video if you speak Russian here

Original article in English

Original article in Chinese

Implementations of algorithms from this video:

%= on a segment, = in a point, sum on a segment

Ji Driver Segment Tree (min= on a segment, sum on a segment)

min= on a segment, max= on a segment, += on a segment, = on a segment, sum on a segment, minimum on a segment, maximum on a segment

Everything from the previous implementation but also GCD on a segment of algorithms from this video:

%= on a segment, = in a point, sum on a segment

Ji Driver Segment Tree (min= on a segment, sum on a segment)

min= on a segment, max= on a segment, += on a segment, = on a segment, sum on a segment, minimum on a segment, maximum on a segment

Everything from the previous realisation but also GCD on a segment

There's a really weird situation with the last Educational Codeforces Round 107. risujiroh is top 1 but his solution for problem G is $$$\mathcal{O}(n^2)$$$. A bunch of people tried to hack him but all these tests work like 4.6 seconds and TL is 5 seconds.

So here goes my challenge. I'm really interested in how to hack it so the first person who will hack risujiroh's solution in the next 24 hours (until April 14th 2021 19:15 UTC) will get $50 from me if you'll share your test generator with me.

Good luck if you're interested!

UPD. I'm sad to announce that nobody accomplished it. I wasn't expecting this scenario so I decided to donate $50 to charity. I chose this. It's a Russian organization that helps people to overcome domestic violence problems.

Hey! I decided to record myself while solving rounds. It's my first attempt and an experiment for my channel. Check out my Educational Round 107 screencast.

Leave a comment if you have anything to say. Did you find it helpful? Is it just a waste of time? Or maybe I should improve something? I've already noticed that in the future I should be aware of the fact that I've got my camera in the right bottom corner so I shouldn't draw there. Maybe you noticed anything else?

When I was in high school I once learned about wavelet tree and I was really impressed. But over time when I learned more tricks I started thinking: is there any essential need in it? Because it seems like merge-sort tree with fractional cascading solves all the same problems and its time complexity is $$$O(\log n)$$$ which is better than $$$O(\log C)$$$.

So, am I right or not? Does anyone know any cases where it's helpful to use wavelet tree?

Hi!

Here goes another video! And now it's in English! This topic is experimental for my channel. I'm talking about everything you need to know about the MEX to solve problems involving this operation. I hope you find this video helpful.

Link to the video

In the future, I'm going to translate my other videos into English. So stay tuned!

You can check out my previous videos on my channel

Contest on mex (and others) is here

Also, there's the Russian version of this video if you speak Russian here

P.S. I'm definitely not fluent in English but I hope you'll understand everything. I see some problems in my English but I'd appreciate it if you said what you found weird in my speech or text.

Hi!

I continue to make videos on algorithms. This time the topic is more basic. In this video, I talk about prefix sums and how they can help you to find sum on segments. You can also learn from this video how to easily generalize prefix sums for 2D, 3D, 4D, etc. cases. In addition, we'll also talk about a simple concept named difference array, which can easily help in some sorts of situations where it seems like you need some complex data structures. And in the end, we'll learn how to add constants, arithmetic progressions, and even quadratic functions to a segment of an array.

Link to the video

The video is in Russian but English subtitles are available. I'd be glad if you watch the video and leave a comment below with your impressions, thoughts, and ideas for future videos. You may also want to text me on telegram if you didn't understand something or you have any questions. I'll be glad to answer!

I'm sorry you need to watch it with subtitles but I'm gonna make an English channel soon. So stay tuned!

If you didn't see it already, I also have a video on disjoint sparse table: here.

Codeforces group with a contest

My realizations:

1D prefix sums

1D prefix sums with structures

2 methods for finding 2D prefix sums: one, two

1D difference array

1D difference array with structures

I've never been good at solving problems about permutations. I find it really hard to illustrate and solve in mind (or on paper) even small examples. Of course, I know that it's a good idea to split a permutation into a set of cycles, but it doesn't really help! I think you understand what I'm talking about. You have these elements that are not in their original positions and you want them to be in the right places. But when you start to make swaps, you should always draw a new picture for every swap to track what's going on.

Yesterday's global round featured this problem about permutations. And it wasn't that hard, but I spent a lot of time trying to figure out what's going on. And this case is even harder because you don't only have a permutation, but also its elements are being flipped every time.

So I'd like to ask you how do you represent permutations and work with them while solving problems?

I personally found out a pretty nice way to do it yesterday. I cut cards out of paper and swapped them with my hands.

You can see that there are two cycles: 123 and 4567. And I could manually swap them and flip while swapping.

It really helped me, but it was still kinda confusing. I needed to perform the same operations several times to figure out what's going on.

I'll be glad if you share your own methods!

Hi!

I made a video on the disjoint sparse table. It's a generalization of a sparse table that expands the possibilities of its application.

Link to the video

The video is in Russian but English subtitles are available. I'd be glad if you watch the video and leave a comment below with your impressions, thoughts, and ideas for future videos. You may also want to text me on telegram if you didn't understand something or you have any questions. I'll be glad to answer!

I'm gonna make more videos in the future. Both on basic algorithms such as prefix sums, binary search, sorting, etc., and also some advanced topics such as heavy-light decomposition, link-cut tree, lambda optimization, FFT, and so on. If you're interested, consider subscribing to my channel!

My disjoint sparse table realizations:

Easy one

Easy to use with templates

Without extending to the power of two

Codeforces group with contest

Good luck!

I think that rating(all) tab on codeforces doesn't work. There is no difference between "rating" and "rating (all)" tabs. But for example there is ershov.stanislav who should be in the top on "rating (all)" tab.

A few days ago 300iq wrote in the blog that he'll dye his hair pink for a week if he doesn't become a legendary grandmaster before the new year. But he has already become a legendary grandmaster((( Actually we have one more chance! If we get 300 iq likes under this post 300iq WILL dye his hair pink! Let's do it together.