Dynamic Programming Playlist

Hello everyone,

I just started my YouTube channel — Adhish K - YouTube in which I have started posting videos related to competitive programming.

My first playlist is on Dynamic Programming — Dynamic Programming Series - YouTube
and I will be uploading solutions for 15 — 16 DP problems in the month of May (with videos coming every second day.)

This playlist is aimed at those who have a conceptual understanding of what DP is and want to raise their DP problem solving level so that they are able to solve medium level DP problems (of CF rating from 1700 to 2100).

Please have a look at my channel and consider subscribing if you like the content.

The problem list is as under:

  1. Flowers (Round 271 Div 2 D Rated 1700) — DP, Combinatorics, Prefix Sums

  2. Consecutive Subsequence (Round 479 Div 3 Rated 1700) — DP, Map Data Structure

  3. Sleeping Schedule (Round 627 Div 3 E Rated 1700) — Scheduling 2D DP

  4. Python Indentation (Round 455 Div 2 C Rated 1800) — DP, Prefix Sum Optimization

  5. Multiplicity (Round 523 Div 2 C Rated 1700) — DP, Number Theory, Memory Optimization

  6. Longest Regular Bracket Sequence (Beta Round 5 C Rated 1900) — DP, Stack Data Structure

  7. Bad Luck Island (Round 301 D Rated 1900) — DP, Probabilities

  8. Queries for Number of Palindromes (ACM-ICPC Elimination Round H Rated 1800) — DP, String Processing

  9. K-Periodic Garland (Round 642 Div 3 E Rated 1900) — DP, Prefix Sums

  10. Zuma (Round 336 Div 1 B Rated 1900) — 2D Range DP

About Me —
I am a high schooler who enjoys CP. I qualified for IOITC 2021 (in 9th grade); have a Codechef max rating of 1965 and a Codeforces max rating of 1748.

Edit:
Problem 10 added to the playlist: Codeforces Dynamic Programming 336 Div 1 B - Zuma (Rated 1900) - YouTube

3 Likes

Explanations are really smooth and intuitive. Thanks

1 Like

Getting TLE on test_case 35 . Submission #115009859 - Codeforces

1 Like

Use ordered map (i.e normal map) not unordered map because the hash function in unordered_map is undependable and is potentially O(n).
Map has O(logN) per query which means time is O(NlogN) which is fine for this problem.

Your AC code - Submission #115015155 - Codeforces

My original code which used unordered_map also gave TLE - Submission #103949800 - Codeforces

But it also gave AC on changing to normal map - Submission #103949899 - Codeforces

This is a common mistake and the key learning is to be wise in using map vs unordered_map
Hope this helps you solve the problem.

1 Like

I though undered_maps are always faster lol

I submitted again ( here ) , using some modifications in hash function as guided by this post . Faster than ever.