Skip to content

Latest commit

 

History

History
115 lines (98 loc) · 6.75 KB

specialist-plan.md

File metadata and controls

115 lines (98 loc) · 6.75 KB
Raw

Specialist Plan

Duration: XX acm days

Pracitce Style: topics + medium problems on basic topics in pupil plan or previously discussed topics in the current plan.

Content

  • Data Structures

    • Disjoint-sets union
    • Segment Trees
    • Fenwick Trees
    • Sparse Table

  • Problem-solving Paradigms

    • Dynamic Programming
    • State-Space Search
    • Meet-in-the-Middle

  • Graphs

    • All-Pairs Shortest Path
    • Bellman-Ford
    • Max Flow
    • Bipartite Graphs
    • DAGs
    • Trees
    • Eulerian Graph

  • Mathematics

    • Number Theory
    • Combinatorics
      • Pigeonhole Principle
      • Fibonacci Numbers
      • Binomial Coefficient
      • Catalan Numbers
      • Inclusion-Exclusion Principle

  • Geometry

    • 2D shapes
      • Circles
      • Triangles
      • Quadrilaterals
    • Polygons
    • Line Sweep

  • String Processing

    • String Matching Algorithms
    • Suffix trie

Timeline

Day Category Topic General Problems
1 - 4 Solving Techniques Dynamic Programming gpset-1, gpset-2, gpset-3, gpset-4
5 Data Structures Disjoint-Sets Union gpset-5
6 Data Structures Sparse Table gpset-6
7 Data Structures Modified Stacks/Queues -
7 Data Structures SQRT Decomposition gpset-7

[Old Plan]

Day Topic Resources Problems on Topic Extra Problems
4 [DS] Disjoint-sets Union CP 2.4.2, Maximal UVa [10583, 12460, 11474, 1197, 10608]
5 [DS] Sparse Table CP 9.33 UVa [11235, 12674] CF [38B, 667A], UVa [12192, 11515, 11824]
6 [Graphs] Floyd-Warshall CP 4.4.5 UVa [10525, 11047, 10171, 925, 439] CF 817C, UVa [10369, 10364, 11456, 10397]
7 [Graphs] Bellman-Ford CP 4.4.4 UVa [558, 10449, 10557, 11721] CF [58C, 331A2], UVa [10318, 551, 12583]
8 [Math] Number Theory CP 5.5.1-5 UVa [91, 10200, 332, 10717, 568] CF [425A, 205D, 59E], UVa [127, 11472]
9 [Math] Number Theory CP 5.5.6-9 CF 476C, UVa [516, 10061, 10820, 10212, 12043 10090] CF [8C, 67D, 28B, 75B, 721D]
10 [SP] State-Space Search CP 8.2.3 CF 520B, UVa [12101, 652, 321, 12135] CF 25D, UVa [11491, 10309, 10874, 11258]
11 [SP] Meet-in-the-Middle CP 8.2.4 TODO UVa 521
12 [DS] Segment Trees CP 2.4.3 TODO CF 665D, UVa 10174
13 [DS] Segment Trees Maximal TODO UVa 11226
14 [DS] Fenwick Trees CP 2.4.4, TC tutorial TODO UVa 10673
15 [Graphs] Eulerian Graph CP 4.7.3 TODO UVa 408
16 [Graphs] DAGs CP 4.7.1 TODO UVa 11029
17 [Graphs] DAGs CP 4.7.1 TODO UVa 543
18 [Geometry] Polygons CP 7.3 UVa 10170 UVa 539
19 [Geometry] Polygons CP 7.3 TODO UVa [125, 133]
20 [Geometry] Polygons CP 7.3 TODO CF 79B
21 [Strings] String Matching: Prefix Function Maximal, CP 6.4.2 TODO CF 664A
22 [Graphs] String Matching: Z-Algorithm Maximal, Slides TODO CF 300C, UVa 334
23 [Graphs] Trees: Basic Algos CP 4.7.2 TODO UVa 10139
24 [Graphs] Trees: Euler walk & LCA TC tutorial TODO UVa 10633
25 [Graphs] DSU on trees CF blog TODO UVa 10006
26 [Graphs] Trees: DP on trees N/A TODO UVa 10871
27 [Geometry] Line Sweep TC tutorial TODO UVa 11267
28 [Strings] Suffix Trie CP 6.6.1-3 TODO UVa 967
29 [Math] Combinatorics check topics sheet TODO UVa [11894, 11730, 10047]
30 [Graphs] Bipartite Graphs CP 4.7.4 TODO CF 681C
31 [Graphs] Bipartite Graphs CP 4.7.4 TODO CF 475D
32 [Math] Combinatorics: Inc-Exc Principle check topics sheet TODO UVa 10307
33 [Graphs] Max Flow CP 4.6 TODO CF 3D, UVa 10738
34 [Graphs] Max Flow CP 4.6 TODO UVa [10608, 10622]
35 [Geometry] Circles CP 7.2.3 TODO UVa [1243, 11415]
36 [Geometry] Triangles CP 7.2.4 TODO UVa [1040, 10680]
37 [Geometry] Quadrilaterals CP 7.2.5 TODO CF [547B]

Notes

  • To find the problems:

    • For CF problems, if problem is 71A, then it's link will be "http://codeforces.com/problemset/problem/71/A".
    • For UVa problems, just google "UVA [problem id]" and you will get links for the problem. Make sure that the same id appears in the problem page written before the problem name.
    • For extra problems about the mentioned topics, check CP or problems sheet.

  • Resources:

  • Solutions and hints:

    • For CF problems, you can see other accepted submissions.
    • For UVa problems, check this repo or google it.

  • Practice and Contribution

    • If you are following this plan and want to contribute to it, send an access request to this google sheet. You will get a column with your name at which you can add links to your solutions, information about time taken to finish the tasks and your own comments on the problems.