### ak2006's blog

By ak2006, history, 4 months ago,

Hello everyone

In the last Codeforces round, one possible solution to Div 2 Problem D / Div 1 Problem B (named "Integers have Friends") used sparse table data structure to handle range GCD queries. So I posted a new video tutorial explaining what a sparse table is and how we can use it to handle range GCD queries.

After watching that tutorial, you should be able to solve / up-solve (if you did the contest and didnt solve it in contest) the Codeforces problem.

I also made a video editorial for that problem: Link to the video editorial for Integers have Friends

Hope this helps some of you.

• +13

By ak2006, 5 months ago,

Hello everyone

After concluding my DP and Graph Theory playlist on YouTube, I just started a DP on Trees playlist where I plan to post my solutions to intermediate level DP on Trees problems from various sources every 2nd day during the month of July 2021.

Here are the links to my playlists:

DP Playlist (18 problems discussed)

Graph Theory playlist (12 problems discussed)

DP on Trees playlist (current)

I have uploaded 2 tutorials on DP on Trees in case you are new to the topic:

Tutorial Part 1

Tutorial Part 2

The problem list is as under:

1) Parsa's Humongous Tree (Round 722 Div 1 A Rated 1600)

2) Choosing Capital for Treeland (Round 135 Div 2 D Rated 1700)

3) CSES Tree Diameter

4) The Fair Nut and the Best Path (Round 526 Div 1 A Rated 1800)

5) Eternal Victory (Round 57 Div 2 D Rated 1800)

6) Distance in Tree (VK Cup 2012 D Rated 1800)

7) Bakry and Partitioning (Round 746 Div 2 C)

I hope this helps some of you.

• +25

By ak2006, 6 months ago,

Hello everyone,

After concluding my DP playlist on YouTube where I discussed my solutions to 18 intermediate level DP problems (rated 1600 to 2000), I just started a Graph Theory Problem Solving playlist where I plan to post my solutions to intermediate level graph theory problems every 2nd day during the month of June 2021.

DP Playlist

Graph Theory Playlist

Tutorial on DFS on Tree

The problem list is as under:

1) Kefa and Park (Round 321 Div 2 C Rated 1500) — DFS on a Tree

2) Graph Without Long Directed Paths (Round 550 Div 3 F Rated 1700) — Bipartite Graphs; 2-Coloring

Tutorial on Bipartite Graphs — 2 Coloring Strategy

3) Beautiful Graph (Education Round 56 Div 2 D Rated 1700) — Bipartite Graphs; 2-Coloring

4) Carousel (Round 629 Div 3 D Rated 1800) — DFS; Graph Coloring

5) Cyclic Components (Round 479 Div 3 E Rated 1500) — DFS; Cycles in Connected Components

6) Number of Simple Paths (Round 686 Div 3 E Rated 2000) — Cycles in a graph; Combinatorics

7) Lost Tree (Latoken Round 1 D Rated 1800) — Interactive; Tree as a Bipartite Graph

8) Valid BFS? (Manthan, Codefest 18 D Rated 1700 ) — BFS

9) Police Station (408 Div 2 D Rated 2100) — Multisource BFS; Edge Coloring

10) Path Queries (582 Div 3 G Rated 1800) — DSU

11) Roads not only in Berland (25 Div 2 D Rated 1900) — DSU

12) Mahmoud and a Dictionary (396 Div 2 D Rated 2000) — DSU

13) INOI 2021 Among Us — BFS, Bipartite Graph Colouring

14) Web Of Lies — Special Representation of Graphs (using Sets)

15) Mocha and Diana (Easy) — DSU; Connected Components

16) Book — DP; Topological Sorting of a Directed Graph

Update: 743 Div 2 Problem C / Div 1 Problem A added to the playlist

I hope this helps some of you.

• +64

By ak2006, 7 months ago,

Hello everyone,

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

My first playlist is on Dynamic Programming and I will be uploading solutions for 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 1600 to 2000).

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

I have also uploaded a general video on how to get better at Dynamic Programming which should be helpful for all skill levels: How to get better at Dynamic Programming

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) — Range DP

11) Clear the String (Educational Round 61 Div 2 F Rated 2000) — Range DP

12) Bottles (ACM ICPC NEERC J Rated 1900) — 3D DP; Greedy

13) The Least Round Way (Beta Round 2 B Rated 2000) — Grid DP

14) Yet Another Yet Another Task (Educational Round 88 Div 2 D Rated 2000) — DP; Kadane's Algorithm

15) Working Out (Round 245 Div 1 B Rated 1600) — Grid DP

16) Modulo Sum (Round 319 Div 2 B Rated 1900) — DP, Prefix Sums, Pigeonhole Principle

17) Fixed Points (Round 734 Div 3 E Rated 2000) — 2D DP

18) Moamen and Xor (Round 737 Div 2 C) — DP, Combinatorics, Bitmasks

19) Up the Strip (Round 740 Div 2 D1 + Hint for D2) — DP, Binary Indexed Tree

20) Book (Round 743 Div 2 C / Div 1 A) — DP, Topological sorting of a Directed Graph

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:

Added a general video on how to get better at DP