Hey everyone,

The premiere of my interview with Kavi, the first Iranian LGM, is set for Friday at 17:00 GMT.

We can all gather and watch it together in this link. The chatbox is also open there and we can react to the video while watching it.

The video is a mix of inspirational, informative, and funny content. We put a lot of effort into making it, I hope you all enjoy it.

Watch the trailer here.

For live discussions, sharing thoughts on contests, and more, join our Discord server.

Don't forget to hit the 'Notify me' button to ensure you don't miss the premiere!

This interview has manual English subtitles and you can also auto-translate to your own language and watch it with subtitles in your own language.

I'm curious to hear from you: Who should be my next interviewee? Drop your suggestions below.

UPD: Because of some issues, the link is changed now.

Hey guys,

I have prepared a video discussing LCS and added it to my YouTube DP playlist.

The Longest Common Substring (LCS) is the length of the longest string shared between two given strings. It's like finding the common set of characters that appear in the same order in both strings.

A subsequence is a sequence of characters that appears in the same order as they do in the original string but not necessarily consecutively. In contrast, a substring is a contiguous sequence of characters within a string.

You can watch the video here.

Here is a code for LCS:

int lcs(string X, string Y) {
    int m = X.length();
    int n = Y.length();

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (X[i - 1] == Y[j - 1])
                dp[i][j] = 1 + dp[i - 1][j - 1];
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }

    return dp[m][n];
}

Link of the DP playlist:

https://www.youtube.com/playlist?list=PLzDmwrrgE-UVKGwxoYao36BVTvBozwLoG

Feel free to join our Discord channel to further discuss these topics and chat with the CP legends I will interview.

https://discord.gg/fYj9xMam7f

As always, please let me know your feedback and suggestions.

Hey everyone,

I received some feedback that some of my audience are not comfortable with English. Also, the auto-generated subtitles on YouTube, especially for mathematical equations, were not accurate.

To solve this issue, I've added manual subtitles to the videos. YouTube allows translation of these subtitles into other languages, and it seems to work well when the subtitles are accurate. I personally tested it with my native language (Persian), and it was understandable.

Let me know if this resolves the issue. If not, perhaps we can use the help of volunteers to add manual subtitles in other languages.

This is an example of using this feature with the Japanese language.

Hey guys,

As some people asked me in the comment section of the previous videos, I have prepared a video discussing how to approach DP problems.

In this video, I discuss the way that I teach my students to think about DP problems. It consists of 4 steps:

1. Definition
2. Base Case
3. Update
4. Final Answer

I will apply this method to solve two problems—Chocolate Bar from Codeforces and Independent Set from Atcoder.

I've added this video to the DP playlist that I've prepared, which currently includes 'Recursion', 'DP & Memoization', and this video:

https://www.youtube.com/playlist?list=PLzDmwrrgE-UVKGwxoYao36BVTvBozwLoG

Feel free to join our Discord channel to further discuss these topics and chat with the CP legends I will interview.

https://discord.gg/fYj9xMam7f

Let me know whether this approach works for you and whether you like these kinds of videos. As always, I appreciate all your feedback—positive or negative.

In this video, I discuss Dynamic Programming and Memoization. You can watch the video here.

You can also read the blog in text in this blog.

Memoization

Memoization is a performance optimization technique that stores previously computed results to avoid redundant calculations when solving problems. By caching these outcomes, it enhances efficiency and speeds up computations, especially in scenarios involving repetitive calculations or recursive algorithms. This approach optimizes runtime by utilizing stored values instead of recalculating them.

Example

#include <iostream>
using namespace std;

int memo[100]; // Array to store computed Fibonacci numbers

// Function to calculate Fibonacci using Memoization
int fibonacciMemo(int n) {
    if (n <= 1) {
        return n;
    }
    if (memo[n] != -1) {
        return memo[n]; // If the value is already calculated, return it
    }
    // If the value is not calculated, compute and store it in the array
    return memo[n] = fibonacciMemo(n - 1) + fibonacciMemo(n - 2);
}

int main() {
    int n = 10; // Desired Fibonacci number
    fill(memo, memo + 100, -1); // Initializing memo array with -1 (uncomputed)
    cout << "The " << n << "th Fibonacci number is: " << fibonacciMemo(n) << endl;
    return 0;
}

In this code, the memo array stores calculated Fibonacci numbers, reducing redundant calculations and enhancing performance.

Dynamic Programming

Dynamic Programming is a problem-solving method used to solve complex problems by breaking them down into simpler subproblems. It works by solving these smaller subproblems just once and storing their solutions for future use, avoiding redundant computations. This approach typically involves solving problems in a bottom-up manner, starting from simpler cases and building up to the more complex ones. Dynamic Programming optimizes efficiency by reusing calculated results, drastically reducing the overall computational load. It's commonly used for optimization problems and often involves iterating through smaller instances to solve larger ones.

Example

#include <iostream>
using namespace std;

int fib[100]; // Array to store computed Fibonacci numbers

// Function to pre-process (calculate) Fibonacci numbers using Dynamic Programming
void pre_process(int n) {
    fib[0] = 0;
    fib[1] = 1;
    for (int i = 2; i <= n; i++) {
        fib[i] = fib[i - 1] + fib[i - 2]; // Calculating Fibonacci numbers iteratively
    }
}

// Function to get Fibonacci number using Dynamic Programming
int fibonacciDP(int n) {
    return fib[n]; // Returning the pre-computed Fibonacci number
}

int main() {
    int n = 10; // Desired Fibonacci number
    pre_process(n); // Pre-calculate Fibonacci numbers up to 'n'
    cout << "The " << n << "th Fibonacci number is: " << fibonacciDP(n) << endl;
    return 0;
}

In this example, the fib array is pre-calculated using an iterative approach, enabling quick access to Fibonacci numbers for problem-solving.

Next video

In my upcoming video, I'll dive into problem-solving using DP techniques. I show exactly how to approach DP problems. I am going to do this based on the comments I received from you.

Support?

If you found this content helpful, your support means a lot. Your simple acts of liking the video and subscribing to the channel bring me so much motivation. Your support truly helps in boosting my work and encourages me to keep creating more valuable content.

Sharing your thoughts, questions, or feedback through comments not only helps me improve but also increases the visibility of this content within the Codeforces community. Let's keep the conversation lively and engaging for everyone!

Thank you for being a part of this!

Join the Discord server here to discuss these topics further, share problems, and discuss with legends I interview with.

Hey everyone,

I'm creating a series of educational [Posts + Videos] dedicated to beginners. The goal of this series is to provide free access for people around the globe to learn competitive programming by themselves.

The first topic that I am going to cover is recursion. The next topic will be dynamic programming and memoization, which I will publish next week. But you need to watch this video first in order to comprehend that one. (That video has references in this video).

If you like my work, I request you to support me so that my work can help more people. You can support by sharing the videos, liking the videos, and subscribing to the channel (which leads to more people watching the content).

You can watch the video here.

Recursion

Recursion is a way to solve a problem by solving smaller instances of the same problem. To understand what I am talking about, let's take a look at a few examples.

Factorial

Factorial is a mathematical operation denoted by an exclamation mark (!). It's applied to a non-negative integer and represents the product of all positive integers less than or equal to that number. For example, the factorial of 5 (written as 5!) is calculated as 5 × 4 × 3 × 2 × 1, which equals 120. In general, n factorial (n!) is the product of all positive integers up to n. The factorial function has applications in various mathematical calculations, permutations, and combinations.

Now, assume that we want to calculate n!. Based on the definition of n!, we can figure out that n! = n * (n — 1)!. So, if I solve this problem for n — 1, I can simply multiply it by n and have the answer for n. This is how we can solve a problem by solving a smaller instance of the same problem.

Fibonacci Sequence

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, typically starting with 0 and 1. So, the sequence begins 0, 1, 1, 2, 3, 5, 8, 13, 21, and so on. Mathematically, it's expressed as f(n) = f(n-1) + f(n-2), with f(0) = 0 and f(1) = 1 as the starting values. This sequence appears in various natural phenomena and is known for its mathematical properties and connections to patterns in nature.

Now, if we want to calculate f(n), we can solve the problem for n-1 and n-2 and then simply add these two values. By doing this, we get f(n).

There is only one issue with solving this problem by recursion. We might have a lot of duplication of calculations here. This will lead to inefficiency in our solution. In the next video, I will talk about how we can make our solution more efficient, using dynamic programming and memoization.

Hey Codeforces,

I've prepared an animation explaining the pigeonhole principle. This video can help kids and newcomers become familiar with fundamental math and computer science. I also explain it in text in this Codeforces blog.

Pigeonhole Principle

The pigeonhole principle states that if n pigeons are in m holes and n > m, then at least one hole has more than one pigeon.

How's that Useful?

The pigeonhole principle is a way of thinking to solve problems. It's an approach to problems by modeling some objects as pigeons and some objects as pigeonholes. Then, by applying the pigeonhole principle, we can solve the problem.

I have solved two exemplary problems using the pigeonhole principle in the video.

Also, this problem from Codeforces can be solved by applying the pigeonhole principle:

Kuroni and Impossible Calculation

I'd love to hear your feedback about how I can be more helpful and make better videos.

Here is the link to the video: https://www.youtube.com/watch?v=J3VrsRGKZO4

Thank you,

Shayan

You can view the original codeforces blog here.

Centroid

If you have ever read about graph theory or participated in a Codeforces contest, you've likely heard about trees. In this tutorial, I'll be talking about centroid, an important vertex that helps you to solve many problems.

To comprehend what centroid is, you need to first be familiar with trees, and also know a little bit about divide and conquer.

The following tutorial is accompanied by the following two videos I prepared to explain centroid:

Centroid #1 | Full Explanation and Implementation

Centroid #2 | Bonus and Interesting facts

Some sample problems

Centroid #1 0:41

The following problems can be solved using centroid:

Ciel the Commander (I solve this problem for you in my first video)

Distance in Tree (Can also be solved without centroid, but it is a good training for implementing centroid)

Xenia and Tree

Kirito in Memeland (Also needs segment tree)

Close Vertices (Also needs segment tree)

Feel free to suggest additional problems.

Definition

Centroid #1 1:44

A centroid is a vertex that, if you remove it from the tree, all connected components afterward have at most n/2 vertices.

You might have these questions now:

1. Why should such a vertex exist?
2. How can we find it?
3. How this vertex can help us solve problems?

Proof of existence and the algorithm to find it

Centroid #1 3:19

We address both questions simultaneously. In other words, we prove the existence of a centroid by discovering it. Once found, its existence is validated.

We root the tree arbitrarily (let's say at vertex 1) and determine the subtree size for each vertex.

Initially, we start from vertex 1. In each step, if the current vertex has a child with a subtree size exceeding n/2, we move to that vertex. Eventually, we will stop moving. We argue that the vertex we are in is our centroid. (Detailed proof in the video)

How centroid helps us

If you are familiar with divide and conquer, "n/2" likely strikes a chord!

As the number of vertices is halved at each step, removing the centroid, selecting one of the resulting connected components, and repeating this process over and over again, each time reduces the tree's size by half. Hence, how many times we repeat our process? Yes, at most log(n). :) (each time, the number of vertices is halved, we start from n vertices, so we have at most lg(n) steps)

Solving a problem using centroid

Centroid #1 9:09

In the video, I solve 'Ciel and Commander'. Make sure to watch it to comprehend how centroid can aids to solve a problem.

How many centroids?

Centroid #2 00:45

In the video, I prove that there are two cases: 1. We have only one centroid. 2. We have two centroid, and there are adjacent.

Most of the time, the first case happens.

An alternative definition for centroid + Proof

Centroid #2 5:14

There is also another definition for centroid.

If we define S(v), as the sum of the distances of all the vertices in the tree from vertex v (unweighted distance), then vertex c is a centroid if and only if S(c) is minimal. I prove this in detail in the video.

The rest of the topic is covered in my second video about centroid.

The second proof

Centroid #2 13:15

Now that we know a vertex with the minimal value of S is a centroid, it's clear we have one because there's a vertex with a minimal S value. :)

In order to find the centroid, you can calculate the value S for all the vertices (using dynamic programming) and report the minimal one as your centroid.

The third proof (and the most incredible one)

Centroid #2 15:17

For each edge, see how many vertices are on each side of this edge. Direct the edge toward the side with more vertices (if equal, direct it randomly).

With n vertices and n-1 edges, there will be a vertex with zero outgoing edges. (Otherwise, we needed to have at least n edges) That vertex is a centroid. (Why?)

I hope this tutorial helps you. I'm trying to help everyone get familiar with algorithms and competitive programming easily. Your feedback is very important to me. Please share your comments and suggestions. If these tutorials aid, I will dedicate myself to releasing at least one every Friday. If you want to support this initiative, liking the videos and subscribing to the channel can be very helpful.

Thank you,

Shayan

Hi Codeforces,

I'm trying to find out how exactly can I help to provide educational materials for everyone to learn Algorithms and CP.

I posted another blog about a month ago about tutoring some people. I am really happy that I have a chance to help two incredible students prepare for IOI for free. (well, I have accepted some paid classes as well)

But, of course, I could not have a class with all the people who emailed me. Therefore, over the past month, I have been thinking about what can help them out. Some people wanted me to prepare some educational videos, some wanted me to hold some online sessions for everyone, and some wanted me to talk more about the teaching approaches I was talking about.

A little about me, I'm currently pursuing a PhD degree in theoretical computer science at the University of Maryland, United States. I've always been passionate about making people familiar with computer science. I had many classes with awesome students in underserved areas of my home country, all for free. Their success in the Olympiads was incredibly rewarding, and now, I'm looking to expand my reach.

I talked to one of my friends, and he told me that he could help me prepare some videos with high quality. (filming, editing, etc.)

I've put together some sample videos and want to share them with the Codeforces community to see if they're helpful. They're currently up on Youtube, accompanied by explanations in Codeforces blog posts.

One tutorial I've worked on covers the centroid, with two videos recorded on the topic. You can find them below.

Centroid #1 | Full Explanation and Implementation

Centroid #2 | Bonus and Interesting facts

Codeforces Blog

Additionally, I've created an animation explaining the pigeonhole principle. I believe that it is mostly going to help newcomers (and kids) understand fundamental math and computer science concepts. I will finalize and upload it in the following days.

Your feedback means a lot to me! I'm open to your thoughts and suggestions on what should come next.

I acknowledge there might be issues with these initial videos. Centroid is quite advanced, and I understand many may need simpler topics first. I plan to cover those too, possibly releasing an educational video every Friday.

Your reactions to these videos will guide my next steps. If you'd like to support this initiative, liking the videos and subscribing to the channels would be very helpful.

Thank you.

PS: Yes, I am Shayan. Hats off to the people who figured that out by themselves. :))

Hello everyone,

I am a competitive programming instructor with 8 years of experience, including as a team leader in the International Olympiad in Informatics (IOI). I have helped many IOI students achieve medals, many of them for free.

Through these years, I have developed a new approach to teaching CP that helps students develop a strong intuition for algorithmic thinking, beyond simply explaining algorithms.

I currently have some free time, so I am offering to teach a few students. I teach in simple English.

If you are a talented and passionate CP student with a financial need, I am happy to teach you for free. But in general, my rate is 50-70$/hour.

Please send an email to jenxls99@gmail.com or message me here if you are interested in learning more.

PS: Sorry for putting this message in Codeforces, I thought it was the best place to do so.