ak2006's blog

By ak2006, 2 months ago, In English

Hello everyone,

After concluding my DP playlist on YouTube where I discussed my solutions to 16 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: https://www.youtube.com/playlist?list=PLzVLIdIx9dQxwAN5mMkzdvK2B4rV8879j

Graph Theory Playlist: https://www.youtube.com/playlist?list=PLzVLIdIx9dQwzso2IwXCQq3aEicK02iKF

The problem list is as under:

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

Problem Link: https://codeforces.com/contest/580/problem/C

Video Editorial Link: https://www.youtube.com/watch?v=hXv0KBoFDBY

(I have also uploaded a tutorial on DFS on Tree in case you are new to the topic: https://www.youtube.com/watch?v=0vNXkdPserI)

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

Problem Link: https://codeforces.com/contest/1144/problem/F

Video Editorial Link: https://www.youtube.com/watch?v=_n-OeOJpnIY

(I have also uploaded a tutorial on Bipartite Graphs — 2 Coloring Strategy in case you are new to the topic: https://www.youtube.com/watch?v=JGjm8pV2_NM)

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

Problem Link: https://codeforces.com/contest/1093/problem/D

Video Editorial Link: https://www.youtube.com/watch?v=PFWp3-PuAK4

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

Problem Link: https://codeforces.com/contest/1328/problem/D

Video Editorial Link: https://www.youtube.com/watch?v=A0tAbJSbc5g

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

Problem Link: https://codeforces.com/contest/977/problem/E

Video Editorial Link: https://www.youtube.com/watch?v=-ZMi6jfKUuM

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

Problem Link: https://codeforces.com/contest/1454/problem/E

Video Editorial Link: https://www.youtube.com/watch?v=TTIjWRJ3TRw

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

Problem Link: https://codeforces.com/contest/1534/problem/D

Video Editorial Link: https://www.youtube.com/watch?v=K5N6KoyQBKE

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

Problem Link: https://codeforces.com/contest/1037/problem/D

Video Editorial Link: https://www.youtube.com/watch?v=d8SmH0GnFcs

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

Problem Link: https://codeforces.com/contest/796/problem/D

Video Editorial Link: https://www.youtube.com/watch?v=Ho_u5kMnM0Y

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

Problem Link: https://codeforces.com/contest/1213/problem/G

Video Editorial Link: https://www.youtube.com/watch?v=VkaBSwObYnw

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

Problem Link: https://codeforces.com/contest/25/problem/D

Video Editorial Link: https://www.youtube.com/watch?v=5nfm5__jjN8

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

Problem Link: https://codeforces.com/contest/766/problem/D

Video Editorial Link: Part 1: https://www.youtube.com/watch?v=ukZzBWZE-PE Part 2: https://www.youtube.com/watch?v=XziToDOWKLU

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

Problem Link: https://www.codechef.com/INOIPRAC/problems/AMONGUS2

Video Editorial Link: https://www.youtube.com/watch?v=eeWclQfnObU

Update: INOI 2021 Among Us added to the playlist.

I hope this helps some of you.

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

5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Seems like a really good list to practice some good graph problems.

5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

great channel