A chain is defined as the sequence of integers $$$1 \rightarrow 2 \rightarrow 3 \rightarrow \dots \rightarrow k$$$.

Given 2 arrays $$$A$$$ and $$$B$$$

• Does the array has a subsequence whose values form a chain. If so, what is the maximum length of such a chain.
• Notice that the maximal chain is not unique. Define min-lex maximal chain subsequence as the subsequence which is lexicographically smaller than any other maximal chain subsequence.
• Find the the min-lex maximal chain of A and B
• Are the indices of min-lex maximal chain of $$$A[L \dots R]$$$ and $$$B[L \dots R]$$$ same?
• How many subarrays such that min-lex maximal chain of A and B are same?
• Find the length of maximal chain of $$$A[L \dots R]$$$

I created a video on the ideas used in this problem

You are given a string. In one operation, you can delete a contiguous substring of identical characters by paying some cost. What is the minimum cost to delete the entire string when:

• Cost is 1 regardless of the substring length.
• Cost is equal to the length of the substring.
• Cost is equal to $$$len^2$$$.

I created a video discussing the ideas used in this problem.

Given an array, you can select 2 adjacent elements, and either increase both of them by 1, or decrease both of them by 1. Can you sort the array after doing the operation any number of times?

I created a video discussing the ideas used in this problem

I'm experimenting with a new series on my youtube channel where I try to brainstorm a 1300 rated problem. Let me know if you would like to see more videos of this kind.

Here's the problem description of the first episode : You are given an array, and you have to place $$$k$$$ integers from this array to a box. If at any point the sum of elements in the box becomes even, you discard the entire box. What is the maximum box sum you can gain?

You can attempt the problem on Codeforces. If you are not able to solve it, you can watch the video.

Given a rooted tree with weighted edges, you start at the root at time $$$T$$$ and move down along the children. When you are at a node $$$u$$$, and the current time is $$$m$$$, you move to the child with index $$$m \% d$$$ where $$$d$$$ is the number of children of $$$u$$$. You would take time $$$w$$$ to reach that child, where $$$w$$$ is the edge weight between them.

Given several queries, determine which leaf vertex would you arrive at for a given $$$T$$$?

I created a video discussing the ideas used in this problem

Given an array,

• Find out the number of inversions.
• Find out the number of inversions across all $$$n!$$$ permutation of the elements.
• Find out the expected value of the number of inversion if I permute elements randomly.

Then, define 2 arrays $$$A$$$ and $$$B$$$. This time, $$$A$$$ is fixed, and you have to permute $$$B$$$. After permuting and fixing $$$B$$$, define $$$C[i] = A[i] \cdot B[i]$$$

• Count the number of inversions in array $$$C$$$ across all permutations of $$$B$$$.
• If I permute $$$B$$$ randomly, what is the expected number of inversions that I'll find in the array $$$C$$$?

I created a video discussing how to solve these problems, starting from bruteforce and then optimizing it to $$$O(N^4)$$$ to $$$O(N^3 \cdot Log(N))$$$ to finally $$$O(N^2 \cdot Log(N))$$$.

This problem appeared at the fourth position in today's Div2 Round.

Consider the famous Leetcode problem, House Robber, where you're a burglar trying to rob $$$n$$$ houses while ensuring that no adjacent houses are robbed. What is the maximum amount that you can rob?

Now, you're given several queries, and each query, you need to answer this problem if only the houses in the segment $$$[L \dots R]$$$ existed.

I created a video discussing the techniques used in this problem.

Given an array, you can select any subarray of length 3, say $$$[a, b, c]$$$. Then, if $$$a + c \gt b$$$, you can delete this triplet, and replace it with $$$(a + c - b)$$$.

Can you achieve an array of length 1 by doing these operations optimally? Then, solve a harder version: How many subarrays can be trimmed to length 1 after doing these operations?

I created a video talking about the ideas and intuition used in this problem

Count the number of substrings with exactly $$$k$$$ distinct characters. I created a video on this classic 2 Pointer problem

Given an array, you can reverse any subarray if the minima and maxima of the subarray have different pairities. Can you sort the array after any number of operations?

I created a video discussing the ideas used in this problem

In an unrooted tree, for a given pair $$$(u, v)$$$, delete all edges on the path from $$$u$$$ to $$$v$$$. Find out the max size of the connected components that are created after this deletion. Call this $$$S$$$.

For each $$$S$$$ in $$$[1, N]$$$, determine how many pairs achieve this $$$S$$$.

I created a video discussing how to solve this problem in $$$O(N^3)$$$ and then optimize it to $$$O(N^2)$$$ by rerooting the tree. Practice Problem

Disclaimer : The intended solution of the linked problem is $$$O(N \cdot Log(N))$$$, but solving it even in $$$O(N^2)$$$ is a good exercise.

Given an undirected graph, define the cost of a path as the MEX of all the edge weights on the path. Define $$$dist(u, v)$$$ as minimum possible cost across all paths from $$$u$$$ to $$$v$$$. Practice Problem

• Compute all pairwise distances.
• Given a subset of vertices, find the minimum cost to make them connected. Adding an edge $$$(u, v)$$$ costs $$$dist(u, v)$$$.

I created a video talking about how to solve these in $$$O(N^2 \cdot E)$$$ followed by an optimization for $$$O(N \cdot E)$$$.

Given an array, split into the maximum number of blocks such that each block has equal median.

I created a video discussing the ideas used to solve this problem

Given a string, you have to delete all characters which differ from atleast one of its neighbors (the deletion of all eligible character happen at once).

Find the number of rounds after which deletion is not possible.

I create a video discussing the ideas used in this problem

Given $$$n$$$ and $$$k$$$, Maximize $$$(a_1 + a_2 + \dots + a_k)$$$ such that $$$a_1 \oplus a_2 \oplus \dots \oplus a_k = n$$$ and $$$0 \leq a_i \leq n$$$.

I created a video discussing the concept of Tight in Bit manipulation and how to apply it to this problem

Partition an array into $$$\geq K$$$ blocks, where each each block has $$$\geq L$$$ elements. Across all such partitions, find the maximum value of the $$$K^{th}$$$ smallest block sum.

I created a video discussing the ideas used to solve this problem. Practice Problem

Given an array, you are allowed to select a subarray of size at least $$$k$$$ and delete the $$$k^{th}$$$ smallest element. Can you make the array a palindrome after doing the operation any number of times? Practice Problem

I created a video talking about the ideas used in this problem.

I created a video on an interesting problem involving maps, 2 pointer and combinatorics, based on E. Monotonic Renumeration

How many subarrays can be rearranged to form a permutation? I created a video on this classic Codeforces problem F. The Number of Subpermutations

Video Link https://youtu.be/FI__C9WjtvE

I created a video on how to optimize Dynamic Programming problems by using 2 pointers, set, stack, binary search and segment tree. This is based on problem D. Blocking Elements

Video Link: https://youtu.be/f-_1lJo3H_M

Given an array, split it into $$$k$$$ disjoint consecutive blocks such that the value of $$$\sum a[i] \cdot blockIndex[i]$$$ is maximized.

I created a video discussing why the greedy strategy for this problem is not obvious. Here is the practice problem

https://youtu.be/y_lk5x4ZRNI

I created a video on Greedy algorithms, Combinatorics and Euclid's Divison Lemma. It discusses problem D. Christmas Tree Decoration

Video Link https://youtu.be/b43Bf1syIe4

Given a permutation, compute the unique MEX across all subarrays. Then, reverse the problem, given a binary string where a $$$1$$$ at index $$$i$$$ means that a subarray with MEX $$$i$$$ exists (and $$$0$$$ means it doesn't), compute the number of permutations that satisfy these constraints.

I created a video discussing the ideas to solve both the problem in $$$O(N)$$$. Practice Problem

Video https://youtu.be/78N9JfaQ72g

I created a video discussing DP on Trees, Expected Value and Greedy strategies to solve E. Coloring a Red Black Tree from last Codeforces Div2 round.

Video Link: https://youtu.be/EAODhN-zthA

Given an array, compute the prefix maxima array and remove all the duplicates. How many subsequences of the original array can you create such that the prefix maxima of the subsequence is equal to the prefix maxima of the original array (after removing the duplicates from both)?

I created a video to solve this problem in $$$O(N \cdot Log(N))$$$.

https://youtu.be/3VQtW8lnEvQ

Practice Problem