ak2006's blog

By ak2006, history, 4 months ago, In English

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.

Link to the tutorial

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.

Read more »

 
 
 
 
  • Vote: I like it
  • +13
  • Vote: I do not like it

By ak2006, 5 months ago, In English

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)

Problem Link

Video Editorial Link

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

Problem Link

Video Editorial Link

3) CSES Tree Diameter

Problem Link

Video Editorial Link

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

Problem Link

Video Editorial Link

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

Problem Link

Video Editorial Link

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

Problem Link

Video Editorial Link

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

Problem Link

Video Editorial Link

I hope this helps some of you.

Read more »

 
 
 
 
  • Vote: I like it
  • +25
  • Vote: I do not like it

By ak2006, 6 months ago, In English

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

Problem Link

Video Editorial Link

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

Problem Link

Video Editorial Link

Tutorial on Bipartite Graphs — 2 Coloring Strategy

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

Problem Link

Video Editorial Link

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

Problem Link

Video Editorial Link

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

Problem Link

Video Editorial Link

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

Problem Link

Video Editorial Link

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

Problem Link

Video Editorial Link

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

Problem Link

Video Editorial Link

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

Problem Link

Video Editorial Link

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

Problem Link

Video Editorial Link

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

Problem Link

Video Editorial Link

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

Problem Link

Video Editorial Link Part 1 Video Editorial Link Part 2

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

Problem Link

Video Editorial Link

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

Problem Link

Video Editorial Link

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

Problem Link

Video Editorial Link

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

Problem Link

Video Editorial Link

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

I hope this helps some of you.

Read more »

 
 
 
 
  • Vote: I like it
  • +64
  • Vote: I do not like it

By ak2006, 7 months ago, In English

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

Problem Link

Video Editorial Link

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

Problem Link

Video Editorial Link

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

Problem Link

Video Editorial Link

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

Problem Link

Video Editorial Link

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

Problem Link

Video Editorial Link

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

Problem Link

Video Editorial Link

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

Problem Link

Video Editorial Link

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

Problem Link

Video Editorial Link

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

Problem Link

Video Editorial Link

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

Problem Link

Video Editorial Link

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

Problem Link

Video Editorial Link

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

Problem Link

Video Editorial Link

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

Problem Link

Video Editorial Link

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

Problem Link

Video Editorial Link

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

Problem Link

Video Editorial Link

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

Problem Link

Video Editorial Link

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

Problem Link

Video Editorial Link

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

Problem Link

Video Editorial Link

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

Problem Link

Video Editorial Link

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

Problem Link

Video Editorial Link

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

Read more »

 
 
 
 
  • Vote: I like it
  • +47
  • Vote: I do not like it