You are given an array consisting of $$$n$$$ positive integers. You are standing at the first index, and you want to reach the last index. You can make as many forward jumps as you want. If you jump from index $$$i$$$ to $$$j$$$ your profit is $$$(j - i) \cdot a[i]$$$. What is the maximum total sum of profits that you can achieve?

I created a blog on this topic discussing how the DP optimization for this problem is easier than you think or harder than you think.

https://cfstep.com/training/tutorials/dp/the-hardest-easy-dp-problem/

Problem E — Sensor Optimization Dilemma 2 from last Atcoder Beginner Contest had a new idea that people in the comments section claimed to be pretty well known. However, this was my first time encountering such an idea, and I figured it'd be the same for a lot of people, so I created a video editorial talking about this fractional greedy idea (with a twist).

https://youtu.be/Tha0WO2FVXE?si=cxuKQbIiaVaGIpt1

Credits to Igor_Parfenov for sharing his wonderful approach in the comments.

I created a video editorial talking about how to use Atcoder Library's Segment Tree to optimize CF2019D: Speedbreaker

https://youtu.be/GyBA_nK4qiw?si=E5qw4X4FLHO5j--_

The editorial of problem ABC370G: Divisible by 3 from last Atcoder Beginner Contest contains an interesting subproblem : How to count the number of arrays of length $$$L$$$ where product of all elements is $$$P$$$? The editorial mentions that this is a good exercise for Blue/Yellow coders, so I created a blog talking about this idea.

https://cfstep.com/training/tutorials/math/count-arrays-with-fixed-product/

To help you verify correctness, I also created a practice problem : https://mirror.codeforces.com/group/7Dn3ObOpau/contest/549784

The problems are untested, if you see any issues with the model solution, do let me know in the comments.

The problem of computing the length of the Longest Increasing Subsesquence is usually solved via DP, Binary Search or Segment Tree. I created a blog discussing a Trie based approach that can solve this problem with very few lines of code.

https://cfstep.com/training/tutorials/dp/lis-using-trie/

I created a Hybrid tutorial discussing Contribution Technique in the context of Problem E. Iris and the Tree from last Codeforces Round. The video just goes over key insights, if you want to dive deep, you should read the blog after watching the video.

Video Link : https://youtu.be/xWGFdf2pvh4?si=dm6GZ0BWPsFP0IU1

Blog Link : https://cfstep.com/training/tutorials/general-techniques/contribution-technique-on-trees/

I created video editorial for D. Iris and Game on the Tree from last Codeforces Round.

https://youtu.be/xDYXvn0NfA0?si=pe3Tzwb3z-CDWZoA

I also created a practice contest containing 3 Game Theory Problems (that I will keep updating in future). https://mirror.codeforces.com/group/7Dn3ObOpau/contest/546860

I created video editorial for D. Longest Max Min Subsequence from last Div 2 round, that discusses multiple approaches for this problem, involving data structures like set, map, vector, dequeue, segment tree, stack, and algorithms such as Binary Search, Greedy Algorithms, Next Greater Element, Exchange Argument.

Problems discussed :

1. Check if pattern exists as subsequence in text.
2. Finding lexicographically smallest subsequence with maximal length containing only unique elements.
3. CF2001D: Longest Max Min Subsequence

https://youtu.be/fiiGEH0nb-w?si=j_Q-Z8KGJgKMfrrh

I also created a practice contest that contains all problems mentioned in the video. Here is the link to the contest https://mirror.codeforces.com/group/7Dn3ObOpau/contest/545195

The problems are untested, if you see any issues, do let me know.

Problem E. Cosmic Rays from last Div1 + Div2 Round had an interesting application of stack. So, I created a video editorial to help you visualize stack problems using graph modelling.

https://youtu.be/l2LTxerp2KE?si=FQzjaNj1Y-QiMH1V

I also created a practice contest https://mirror.codeforces.com/group/7Dn3ObOpau/contest/542909

The last problem from today's Codechef starter dealt with diameter of weighted trees. So I created a video discussing the general ideas behind computing diameter of weighted/unweighted tree, and the farthest node from each node (using ideas from this amazing blog by TheScrasse )

https://youtu.be/UhhIFuHhllE?si=mpzEwZwm9py7OgFT

3 Practice Problems :

1. CSES : Tree Diameter
2. CSES : Tree Distances 1
3. Codeforces : Three Paths on a Tree

I created a video discussing how to compute the XOR of all numbers in the range $$$[L, R]$$$ in $$$O(1)$$$. It also talks about how to compute the number of set bits at position $$$p$$$ in the range $$$[L, R]$$$ (people usually get confused with off-by-one errors in these problems, Not anymore!).

Although not directly related, XORs and modulo 4 appeared in the last Codeforces Round. This trick is not known by many, so I decided to create a video.

https://youtu.be/v8G2gjQ_gp8?si=rG60v07Bn4mTL-dw

If you want to apply this info to an actual problem, here's a practice contest https://mirror.codeforces.com/group/7Dn3ObOpau/contest/539212

I created a video discussing strategies to upsolve and read editorials for Codeforces problems. It also talks about how to use Atcoder Library like STL, in context of problem G: Penacony from last Div 3 Round.

https://youtu.be/iMjd2QI6NEs?si=Xr9g2Mz_HTwLBLQ8

I also curated some practice problems. Here's the contest link : https://mirror.codeforces.com/group/7Dn3ObOpau/contest/538988

I created a video editorial for Problem D : Cases from last Codeforces Round 961 (Div 2)

https://youtu.be/LgxHoy3Aguk?si=XcacblYTS5nIHMf0

I also created a practice contest with easy version of the problem. You can find it here https://mirror.codeforces.com/group/7Dn3ObOpau/contest/538630

I created a video that talks about how to efficiently and easily compute the next smaller element, second next smaller element and so on, using a set instead of stack. It also talks about a non trivial contribution technique that recently appeared as part of problem E: Range Minimum Sum from Codeforces Round 958.

Here is the video link https://youtu.be/MRlaULKT9V4?si=PfpyqPIJns0OMRqb

I also curated some practice problems and created easy version of problem E. You can find the contest here https://mirror.codeforces.com/group/7Dn3ObOpau/contest/537569

The problems are untested, if you see any issues, do let me know.

I made a video editorial discussing the intuition behind problem D: The Omnipotent Monster Killer from last Codeforces Round 958. It also talks about a neat trick to analyze the time complexity of Tree DP problems. I also created a practice contest for you to assess your cubic and quadratic solutions.

https://youtu.be/exUm24JN2-A?si=uQsyu0tz571kwinW

Here is the link to the contest https://mirror.codeforces.com/group/7Dn3ObOpau/contest/536755

Here are the slides, blog, code, similar problems and other resources used in the video https://cfstep.com/codeforces/contests/contest-1988/problem-d/

If you need any help, or if you notice anything wrong with the easy version of the problems, do let me know in the comment section.

TL;DR : I created a practice contest that contains 6 problems that use the same underlying DP idea.

https://mirror.codeforces.com/group/7Dn3ObOpau/contest/532384

I will publish the blog soon. Till then, feel free to discuss your approach in the comment section.

DP on distinct subsequences is one of the easiest DP to implement, but also the hardest DP to come up with. It is like an optical illusion, where at the start, you’d think that it’s impossible for such a simple code to work, but once you finally understand how the algorithm works, you’d think that the problem was a cakewalk.

To truly appreciate the beauty of the solution, it’s important that, before reading the blog, you spend a significant amount of time attempting all the 7 problems that I’ve created.

P.S : The problems are untested, if you see any issues, do let me know.

The last Educational round contained an interesting problem D on Balanced parenthesis, which becomes almost trivial if someone has read this 8 year old comment by tenshi_kanade that talks about a much easier problem

Count the number of substrings that are balanced parenthesis.

I created a blog that talks about this idea in a bit more detail and also discusses how to modify the solution of this problem to make it work for the Edu problem. I also created practice problems on it so that you can submit your $$$O(n^2)$$$ and $$$O(n)$$$ approach. This is the contest link https://mirror.codeforces.com/group/7Dn3ObOpau/contest/527306

https://cfstep.com/training/tutorials/general-techniques/balanced-parenthesis-on-segments/

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

I created a blog that talks about 3 quirks of maps/multisets.

1. Accessing non existent elements in maps keyed on characters may lead to WA.
2. Accessing non existent elements in maps keyed on integers may lead to TLE.
3. Using the fancy count operator in multisets may lead to TLE.

There's no new/unique insights, I just documented my personal experience with these quirks, along with the problems link where I first encountered this issue. It might be helpful to beginners in competitive programming.

https://cfstep.com/training/tutorials/general-techniques/quirks-of-non-existent-map-elements/

The editorial of D. Colored Balls mentions that the first part of the problem is a standard puzzle, so it doesn't go into too much details. However, what's standard to old timers is new learning opportunities for newcomers. At least, to me, it was not at all obvious why the given formula works, until I encountered a good visual proof for the same.

I created a video talking about the strategy to solve the puzzle, with proof.

https://youtu.be/3TbkZ1A489o?si=V6Qq5CoXdbAfPi6U

Problem Link

Target Audience : If you are not able to come up with the $$$O(n^2)$$$ algorithm in 5 minutes, and the $$$O(n)$$$ algorithm in additional 5 minutes, this tutorial is for you. If you are a beginner to Dynamic Programming on Prefix, this 1D DP problem is a good starting point for you to learn the technique. This tutorial assumes that you already have some experience with 1D DP.

I came across a simple yet elegant problem, which might be trivial to some but a good learning experience for others. So I created a blog that talks about how to optimize DP transitions by switching from Pull DP to Push DP.

You can submit your $$$O(n^2)$$$ and $$$O(n)$$$ solution here : https://mirror.codeforces.com/group/7Dn3ObOpau/contest/517981

https://cfstep.com/training/tutorials/dp/push-dp-vs-pull-dp/

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

If you have more practice problems on this concept, please share them in the comments below and I'll add them to the practice contest.

I created video editorial for H. The Most Reckless Defense from last Div 3 Round (CF Round 938). It talks about Bitmask DP, exponentials, and how to approach problems with long description.

Youtube Link : https://youtu.be/bBTW58NEoJ4?si=zItmAtlyEGBiNMG_

Here's a practice contest on bitmask and bitmask DP

• Practice Contest 1

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

To improve, just upsolving problems is not enough. You also need to ask yourself at what point you diverged from the intended solution, or what you could've done differently to arrive at the intended solution.

I made a video editorial discussing my train of thoughts involved for solving D. Learning to Paint from last CodeTON Round. The video talks about how you can spot patterns in problems and use them to your advantage for future problems.

Youtube Link : https://youtu.be/EGp72-5MV8U?si=1l9kq1SFQ_qhFRro

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

I made a video editorial discussing D. Birthday Gift from last Div 2 Round (CF Round 936). The video talks about how the concept of submasks can be helpful outside of subset counting problems.

Youtube Link : https://youtu.be/qZobx4EOVm0?si=LsPPCv4mi2szw-PR

Here's a practice contest on bitwise operations:

• Practice Contest 1

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

Given an array of positive integers, for each element, you can choose to multiply it by $$$-1$$$. Find the maximum number of negative elements at the end, such that the prefix sum of the final array contains strictly positive integers only.

I created a short blog that talks about how the obviously incorrect greedy strategy for some problems can actually be fine-tuned to be correct, by going back and altering our choices.

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

https://cfstep.com/training/tutorials/general-techniques/time-travel-in-greedy-algorithms/

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

If you have more practice problems on this concept, please share them in the comments below and I'll add them to the practice contest.

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

I made a video editorial for CF1923E : Count Paths discussing the DP solution that acts as the foundation of the small to large trick.

Youtube Link : https://youtu.be/D454rHDUb6E?si=FtfBwoKG3_p-8m7f

I also created practice contest with easy problems:

• Practice Contest