peltorator's blog

By peltorator, 5 months ago, In English

UPD: schedule, list of guests, and questions form for guests added.

UPD2: link to the stream: https://youtu.be/WZKOdorb1Dg

I know that lots of you were saying that Codeforces should stay out of politics when there were lots of blog posts supporting Ukraine a couple of weeks ago. Well, I respect your opinion, but I can't agree. If you see a binary search tutorial on the "Top" page, do you complain about it if you're not interested in binary search, or do you just ignore it? And at the end of the day, it's not really about politics, but about people's lives.

Having said that, I'd like to invite you to join my 8-hour long live stream on YouTube against the Russian invasion of Ukraine next Sunday (27th of March) from 10 AM till 6 PM Ukrainian time (be careful, 27th of March is a daylight saving start in Ukraine and a lot of other countries, but it may not be the case for your country, so check your timezone using this link).

Сurrent plan is (all time periods are in Ukrainian timezone; if you want to ask questions, go here):

10:00-10:30 — Intro, tricky interesting problems for chat

10:30-11:00 — Interview with Matt tehqin Fontaine (author of Algorithms Live! youtube channel)

11:00-11:30 — Solving problems blindfolded

11:30-12:00 — Interview with Nikita nskybytskyi Skybytskyi (author of Nikita Skybytskyi youtube channel)

12:00-13:00 — Lecture: Everything I know about lambda optimisation (aliens trick)

13:00-13:30 — Interview with Alex Um_nik Danilyuk (ICPC 2020 champion team member, author of umnik_team youtube channel)

13:30-14:30 — Solving problems blindfolded

14:30-15:00 — Interview with Kamil Errichto Debowski (author of Errichto and Errichto2 youtube channels)

15:00-15:20 — Lunch break

15:20-16:00 — Cool little algorithms nobody talks about

16:00-16:30 — Interview with Anton antontrygubO_o Trygub

16:30-16:45 — Talking to chat

16:45-17:15 — Interview with Jay Geothermal Leeds (author of Jay Leeds (Geothermal) youtube channel)

17:15-17:45 — Interview with Ildar 300iq Gainullin (IOI 2019 2nd place)

17:45-18:00 — Outro

And during this stream, I'd like viewers to donate money to Ukraine. Here I'd like to get some help from you. Please, leave some organizations that help Ukraine to which we could donate money in the comments. Also, I'd like to have a counter on the stream that says how much money was donated by the viewers, but I don't understand how it is possible if they will not be donating it to me. If you know how to do it, also suggest your ideas. Of course, it's possible to donate the money to me, and then at the end of the stream I could send them to charity organizations, but first of all, you should 100% trust me in this case, and second of all, I'm a Russian citizen, so it's really hard for me to have any kind of PayPal, etc at the moment to collect money :)

If you are my friend or anyone who would like to be a guest on this stream, please DM me on Codeforces or Telegram. Don't be shy! If you have any ideas on what I should do during this stream, also write them in the comments.

Hope I'll see you in a week! NO WAR!

Read more »

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

By peltorator, 8 months ago, In English

I really like good blog posts. And that's the main reason I like Codeforces. But as we all know, it's hard to find good blog posts here. So let's help each other and share our favorite posts, which were uploaded to Codeforces in the last year! I will share my top 10, and I encourage you to share some of your favorites in the comments.

10. Heuristic algorithm for Hamiltonian path in directed graphs by slime

An absolutely incredible algorithm which kinda sometimes solves the Hamiltonian path problem on some random and special kind of graphs.

9. I compiled a list of almost all useful blogs ever published on Codeforces by parveen1981

This blog has a purpose that's similar to the purpose of the blog you're reading right now. A great source of interesting blog posts!

8. Fast modular multiplication by orz

Some really interesting algorithms that help multiply 64-bit numbers modulo without int128.

7. Competitive Programming Hall of Fame — cphof.org by Ra16bit

A new awesome resource, that collects all the different achievements of CP-legends.

6. The Ultimate Topic List and (The Ultimate) Code Library by YouKn0wWho

These are two different posts, but I would like to combine them. This is a really nice collection of materials and implementations of tons of different algorithms and data structures needed for competitive programming.

5. My opinion on how to practice competitive programming by Radewoosh

Some really interesting thoughts from Radewoosh and a really long and engaging discussion in the comments.

4. C++20 Is Released by MikeMirzayanov

The main treasure of this blog post is the comments! So many interesting tricks and tips for C++20.

3. [Tutorial] GCC Optimization Pragmas by nor

I never used pragmas because I didn't understand what they're doing. Finally, there is a resource where I can close this gap in my education :)

2. Lambda optimization certificate by never_giveup

A really interesting discussion about an algorithm which is around for 5 years but still isn't really understood by the public. I learned a lot from this blog post and after that started researching a lot of things about lambda optimization (a.k.a. Lagrange optimization a.k.a. aliens trick) on my own and figured out that I didn't really understand a thing about it before.

1. [Tutorial] Li Chao Tree Extended by rama_pang

In my opinion, it is the best blog post and the best new data structure of the year. It's absolutely incredible and simple at the same time.

I hope you learned something new today. I'm looking forward to reading your favorite blogs. Merry Christmas and Happy New Year.

Read more »

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

By peltorator, 10 months ago, In English

Hi!

I wanted to make a new fun screencast. In this video, I'm solving Codeforces Round #747 (div. 2) but there are two main differences from a regular screencast:

  1. It's a highlight video which means that it's not a 2-hour long video of me thinking about problems but just some fun, interesting, exciting moments.

  2. It's something I called a "Challenge Screencast" which means that there is a challenge I need to complete during the contest. This time the challenge was to not use any loops in the code. So no for loops, no while loops... At all!

https://youtu.be/imGdtb_lB_U

I hope you'll enjoy it! I'll be happy to hear any comments and suggestions for the future challenge screencasts!

Read more »

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

By peltorator, 14 months ago, In English

As some of you asked me, I'd like to share a video in which I'm talking about my competitive programming setup (especially codeforces). I'm talking about my hardware, google chrome extensions for codeforces, vim setup + snippets, c++ template, and much more.

If you're interested in something specific, you may want to use timestamps in the description. All the links to everything I'm talking about in this video are in the video description.

Link to the video

Read more »

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

By peltorator, 15 months ago, In English

When you use C++ and the input is really big you can't just use cin and cout. You need to speed up it with

ios::sync_with_stdio(0);
cin.tie(0);

Someone argues that the second line is unnecessary but it's not true. if the input and output alternate then adding the second line makes I/O more than twice faster. But then... Someone argues that we also need to use cout.tie(0).

I personally never use this and I don't know any case where it can help. So my question for today is the following: "Is there any case where we actually need cout.tie? Or is it completely useless?"

Read more »

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

By peltorator, 15 months ago, translation, In English

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

Read more »

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

By peltorator, 16 months ago, In English

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.

Read more »

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

By peltorator, 16 months ago, In English

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?

Read more »

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

By peltorator, 17 months ago, translation, In English

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?

Read more »

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

By peltorator, 17 months ago, translation, In English

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.

Read more »

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

By peltorator, 17 months ago, translation, In English

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

Read more »

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

By peltorator, history, 18 months ago, translation, In English

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!

Read more »

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

By peltorator, 18 months ago, translation, In English

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!

Read more »

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

By peltorator, 4 years ago, In English

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.

Read more »

Tags bug
 
 
 
 
  • Vote: I like it
  • +47
  • Vote: I do not like it

By peltorator, 4 years ago, In English

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.

Read more »

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