I made a video editorial discussing G. Vlad and Trouble at MIT from last Div 4 Round (CF Round 928). The video can act as a gentle introduction to Tree DP.

Youtube Link : https://youtu.be/xB2sZz7aa-M?si=z2eRU0dDai-jodmf

Here are 3 practice contests:

• Practice Contest 1
• Practice Contest 2
• Practice Contest 3

If you're a complete beginner, then you should only attempt these 3 problems : 1, 2 and 3

The editorial for ABC340G: Leaf Color from last Atcoder Beginner Contest mentions an interesting exercise/subproblem for the readers

Fix a color and find the answer in $$$O(N)$$$ with Tree DP. Although not easy, it is a good exercise for blue coders, so we recommend you to think about it.

So I created a blog post that discusses how to find

1. The number of induced subgraphs that are trees.
2. Number of connected induced subgraphs with degree $$$d$$$ for any $$$d$$$.
3. Number of connected induced subgraphs with degrees $$$0$$$, $$$1$$$ and $$$\geq 2$$$.
4. Number of connected induced subgraphs with monochromatic degree 1 vertices.
5. Followup problem to apply the concepts learned.

To help you solidify the concepts discussed, I've created 2 + 1 practice problems. You can access them here: https://codeforces.net/group/7Dn3ObOpau/contest/504547

https://cfstep.com/training/tutorials/trees/dp-on-induced-subgraphs-of-a-tree/

If you have an alternate solution for any of these problems, do let me know in the comments.

The problems are untested. If you see any issues, please let me know.

If you need any help or hints for the practice problem, you can ask on my Discord Server or on the Twitter thread. In case you are interested, you can also checkout my youtube channel

ABC339G: Smaller Sum from the last week's ABC had restrictions for online query and someone in the comment section was interested in knowing the alternate easier solution if the queries could be answered offline. So, I've written a short blog that talks about how to use sweep line to answer these 2 problems:

1. You are given an array and several queries. A query consists of a subarray and $$$x$$$. Print the sum of all elements from this subarray that are $$$\leq x$$$.
2. You are given a tree and some queries. In each query $$$(x, y, T)$$$ print YES if there is a path from $$$x$$$ to $$$y$$$ such that the maximum value on that path is $$$ \leq T$$$.

To help you solidify the concepts discussed, I've created 1 + 1 practice problems. You can access them https://codeforces.net/group/7Dn3ObOpau/contest/503852

https://cfstep.com/training/tutorials/general-techniques/answering-queries-offline-with-sweepline/

The problems are untested. If you see any issues, please let me know.

If you need any help or hints for the practice problem, you can ask on my Discord Server. In case you are interested, you can also checkout my youtube channel

Given an array, how do you efficiently find out the minimum xor pair. I've written a short blog discussing the idea behind it.

To help you solidify the concepts discussed, I've created 1 + 1 practice problems. You can access them here: https://codeforces.net/group/7Dn3ObOpau/contest/503551

https://cfstep.com/training/tutorials/bitwise-operations/xor-is-minimized-for-adjacent-sorted-elements/

The problems are untested. If you see any issues, please let me know.

If you need any help or hints for the practice problem, you can ask on my Discord Server. In case you are interested, you can also checkout my youtube channel

The editorial of ARC171C mentions that the sum of $$$\prod deg(u)!$$$ over all spanning subgraphs can be computed using DP but doesn't mention how. So I created a blog post that discusses how to compute:

1. Number of spanning subgraphs where root vertex has degree $$$d$$$.
2. Sum of $$$\prod deg(u)!$$$ over all spanning subgraphs
3. Sum of $$$\sum deg(u)$$$ over all spanning subgraphs

To help you solidify the concepts discussed, I've created 2 + 1 practice problems. You can access them here: https://codeforces.net/group/7Dn3ObOpau/contest/503270

https://cfstep.com/training/tutorials/trees/dp-on-spanning-subgraphs-of-a-tree/

The problems are untested. If you see any issues, please let me know.

I've written a short blog discussing the idea of extending Binary Strings with DP. It also discusses the solution to problem E: Counting Binary Strings from last Div 2 round.

To help you solidify the concepts discussed, I've created 5 + 1 practice problems. You can access them here: https://codeforces.net/group/7Dn3ObOpau/contest/498710

https://cfstep.com/training/tutorials/strings/extending-binary-strings/

The problems are untested. If you see any issues, please let me know.

I've written a short blog discussing the applications of Dijkstra's Algorithm (to find shortest path, second shortest path, monochromatic shortest paths, etc).

Target Audience : You've used Dijkstra's algorithm as a black box in the past. Or you have some understanding but not the complete picture of why the algorithm works.

To help you solidify the concepts discussed, I've created 1 + 3 practice problems.You can access them here: https://codeforces.net/group/7Dn3ObOpau/contest/497900

Can you write/prove Dijkstra’s algorithm without referring to external sources? What about BFS? If your answer to the first question is NO, and to the second question is YES, this tutorial is for you.

https://cfstep.com/training/tutorials/graphs/dijkstra-is-bfs-in-disguise/

I made a video editorial discussing ABC335F : Hop Sugoroku. The video talks about how to use Distributing DP and optimize it using the square root trick.

Youtube Link

Easy version of the problems and practice problems can be found in this contest : https://codeforces.net/group/7Dn3ObOpau/contest/496787

I've written a short blog discussing the applications of tracking time while performing DFS. It also discusses the (partial) solution to problem E: Happy Life in University from Good Bye 2023. To help you solidify the concepts discussed, I've created 4 + 1 practice problems.You can access them here: https://codeforces.net/group/7Dn3ObOpau/contest/496216

If you're familiar with DFS, but don't know what Euler Tour and Tree Flattening mean, this tutorial is for you.

https://cfstep.com/training/tutorials/trees/timer-on-trees/

I made a video editorial discussing ABC334F : Christmas Present 2. The video talks about how to use the sliding window technique to optimize DP transitions.

Youtube Link

I also created 1D version of the problem, with 3 versions so that you can submit your $$$O(N^3)$$$, $$$O(N^2)$$$ and $$$O(N * Log(N))$$$ solution and verify the correctness. You can access the group using this link https://codeforces.net/group/7Dn3ObOpau In the contests section, you'll see a contest by the name DP + Sliding Window.

The problems are untested, so if you spot any issues, please let me know.

I made a video editorial discussing Edu 160D — Array Collapse . The video talks about how to use monotonic stacks to perform DP transitions faster.

Youtube Link

I also created some basic problems to help you practice the stuff covered in the video. You can access the group using this link https://codeforces.net/group/7Dn3ObOpau In the contests section, you'll see a contest by the name Monotonic Stack + DP. If you want me to add even more basic problems, like finding the previous smaller element or next greater element, please let me know. The problems are untested, so if you spot any issues, please let me know.

I made a video editorial discussing ABC 333 F — Bomb Game 2 . The video covers a common technique used in Probability DP problems, and how to handle cycles between DP states.

Youtube Link

I would appreciate your feedback!