Skip to content

Latest commit

 

History

History
2205 lines (1346 loc) · 162 KB

File metadata and controls

2205 lines (1346 loc) · 162 KB

Complete Competitive Programming Guide

A complete "Competitive Programming" guide with topics' name, categroy, links, blogs, books and video tutorials. This is my easy compilation of "Competitive Programming" resources


Maintainer


This repository is maintained by rng70 (Al Arafat Tanin) · GitHub


Table of Content



Contest Archives


Name Links
Codeforces Blog: 55247 · Topics
Blog: 48102 · Topics
Blog: 572282 · Resources
A2OJ Problem Category
Problem Ladder
CodeChef Getting Started
List of Topics
Number Theory
Best Resources
PEG Wiki Main Page · WCIPEG
CSAcademy Contest-Archive Archieve  CSAcademy
HAlexV Resources
Blogs
Awesome CP Awesome  CP · GitHub
PS Community Topics Collection Southseo's Blog
NOI.PH: a Filipino website with good resources Topics List · NoI.ph
GeeksForGeeks Top 10 Algorithms and Data Structures for Competitive Programming - GeeksforGeeks
Number Theory for Competitive Programming - GeeksforGeeks

Contest Sites (Practice)


Here is some cool online judge lists. You will not only be able to solve problems but also you will find a lot of tutorials, articles and other materials.

    • It also hosts the TopCoder data science tutorials, a list of tutorials written by respected Topcoder members.

Problem Archives


These are some online judges with large problem archives, that you can use to practice topics as you learn when you are not doing contests.

    • The DMOJ is a modern contest platform and archive of programming problems. It’s also entirely open source. So you can make you local pc as online judge.

    • Do you love interactive problem? Then it is really appropriate for you.


Visual Tools


  1. This is a app by CSAcademy. This tools will help to visualize hard graph problems and to make graph to solve properly.

  2. This is a tools by CSAcademy. This tools that can help you solve problems that are hard to visualize properly.

  3. This is a website perfect for people trying to get an intuitive feel for algorithms. It features animations for most common data structures and algorithms.

  4. This is another website to visualize algorithms, data strucutres and the operations we can do on those data structures.

  5. This is a French site and very good to practice some algorithms.


Topics


  1. SPLEN
  2. Centroid Decomposition
  3. CLIP Zul If you know Russian well then it is a good place for you to learn.

Number Theory



Geometry and Computational Geometry



Graph Theory


  • Representation and BFS and DFS
    • Lexicographical BFS
  • Dijkstra and Variation
  • Bellman-Ford Algorithm and it’s variation
  • Eularian Paths
    • Hierhozer’s Algorithm
  • Floyd Warshall and it’s variation
  • Johnson’s Algorithm
  • Shortest path and k-th shortest path
    • SPFA

    • Yen’s Algorithm

    • Seidel's algorithm, unweighted APSP

    • 0-1 BFS

    • Johnson algorithm

  • Minimum Spanning Tree
  • Topological Sorting
    • using DFS

    • Khan’s Algorithm

  • Strongly Connected Components
    • Kosaraju’s Algorithm
  • Articulation Point
  • Euler path (Construction and optimization)
  • Maximum Flow
    • Ford Fulkerson

    • Dinic

  • Maximum Independent set
  • Maximum flow minimum cost
  • Largest Clique
  • IDA* Search (Iterative deepening and Iterative deepening A*)
    • Advanced topics
  • Stable Marriage Problem
  • Stoer Wagner Algorithm
    • Finding Minimum Cut
  • Planar Graph Detection
  • Havel-Hakimi Algorithm
    • Construct a graph given degree of nodes
  • Erdos & Galli Theorem
  • DAG and Grid
  • Modular decomposition
  • Numbers
    • Euler

    • Catalan

    • Stirling

      • First Kind

      • Second Kind

  • Level ancestors and Ladder Algorithm
  • Flow
  • Constraint satisfaction problem
  • Kirchhoff's Matrix Tree Theorem
  • Rotating Calipers
  • Dominator tree
    • Lengauer-Tarjan Algorithm
  • Kempe’s Graph-coloring Algorithm
    • Chaitin's algorithm

    • Kempe’s Algorithm

  • Hall's marriage theorem
  • Hungarian algorithm
  • Blossom Algorithm
  • Search for bridges online
  • Hopcroft–Karp algorithm
  • Perfect order elimination
  • Maximum matching
    • Edmonds-Blossom algorithm
  • Global min-cut
  • [Tutorial] Matroid intersection in simple words

Game Theory


Used to solve problems involving mathematical modelling of conflict and cooperation among rational players.

  • Theory

    • Stanford - PDF on Combinatorial Games.
    • Wikipedia - Introduction to Nim Games.
    • Book - Composite Mathematical Games.
    • Book - Game Theory By Thomas S. Ferguson.
    • Wikipedia - Sprague Grundy Theorem.
    • Topcoder - Introduction to Algorithmic Games.
  • Nim

  • Grundy Number and DP Formulation

  • Alpha Beta Pruning Minimax


Group Theory


  • Schreier–Sims algorithm

Greedy


Greedy problems involve solving a problem statement considering the most greedy, i.e. most optimal solution at the given time without taking into consideration the future effects of it.

  • Theory

  • Task Scheduling

  • Chordal graph

  • Maximum sum subarray

    \left\beginaligned \text1D array in  \rightarrow \mathcalON\  \text2D array in  \rightarrow\mathcalON^3  \endaligned  \right\ \qquad \Longrightarrow \qquad \text  Kadane's Algorithm

  • Maximum rectangle \mathcalON^2


Dynamic Programming


Used to solve questions which can be broken down into smaller sub problems. It involves the technique of saving the result of a problem for future reference.

Everything About Dynamic Programming

Best DP resource

DP-ever resource

Topcoder - Dynamic Programming from Novice to Advanced.

Codechef - Tutorial on Dynamic Programming.

Quora - Getting started with Dynamic Programming (Quora Discussion).


String Algorithms



Bitwise


You can read my collection of some bit trick for [here](./.random notes/.Bit Trick.md)


Miscellaneous


  • Meet-in-the-Middle Approach

  • Konig’s Theorem

  • Matrix Tree Theorem

  • Counting-out Game

    \left.\begin{aligned} \text{Using queue in  }\rightarrow \mathcal{O}(N^2)\  \text{Using recursion in  }\rightarrow\mathcal{O}(N)  \end{aligned}  \right} \qquad \Longrightarrow \qquad \text{Josephus Permutation}

  • Hashing

  • Huffman Coding

  • Backtracking with pruning

  • Finding K-th number from a sequence of unsorted numbers in \mathcal{O}(log N)

  • Matrix exponentiation

  • Zeller's Congruence

  • Transforming Hexagonal grid, Triangular grid to 3-D coordinate system

  • Knight tours

  • Simulated annealing and Hill climbing

  • 15 Puzzle

    • A* and Meet-in-the-Middle
  • 2-SAT Problem


Some Useful Library


  • Segment Tree Library with Lazy
  • ModInt Library
  • FFT Library
  • Geometry Library

Adhoc


  • Interactive problems
  • Constructive algorithm

Blogs and Sites



Data Structure and Algorithm


Dictionary of Algorithms and Data Structures

All you need

Again-One


Data Structure


Lists of Data Structure

Data Structures - A guide to high level data structures by PrinceOfPersia


Algorithms


List of Algorithms

FXT: a library of algorithms


STL



Challenges


  1. Google-Foobar
  2. Coding-Interview-Question-Patterns
  3. Tech-Interview
  4. An awesome beginner’s list for competitive programming
  5. Dhaka regional Analysis
  6. ICPC-2019 Analysis
  7. __int128

বাংলায় প্রোগ্রামিং রিসোর্সসমূহ


বাংলায় সহজবোধ্য প্রোগ্রামিং টিউটরিয়াল, রেফারেন্স এবং অন্যান্য প্রয়োজনীয় লিংকের তালিকা

বাংলা ভাষায় লেখা প্রোগ্রামিং এর সবচেয়ে বড় রিসোর্স কালেকশন


যাদের ব্লগ থেকে লেখা সংগ্রহ করা হয়েছে


ব্লগের তালিকা (লেখকের নামের ক্রমানুসারে):


এলগোরিদম


ব্যাসিক

ডাটা স্ট্রাকচার

ম্যাথ ও নাম্বার থিওরী

গ্রাফ থিওরী

ডাইনামিক প্রোগ্রামিং

সর্টিং

সার্চিং

গ্রীডি মেথড

রিকার্শন, ব্যাকট্র্যাকিং

স্ট্রিং এলগোরিদম

জিওমেট্রী

গেম থিওরী

অন্যান্য


ও-ও-পি (OOP) এবং ডিজাইন প্রিন্সিপালস



ডিজাইন প্যাটার্ণ


ডিজাইন প্যাটার্ণ কি

ফ্যাক্টরী ডিজাইন প্যাটার্ণ

সিঙ্গেলটন ডিজাইন প্যাটার্ণ

স্ট্রাটেজি ডিজাইন প্যাটার্ণ

ডেকোরেটর ডিজাইন প্যাটার্ণ

প্রোটোটাইপ ডিজাইন প্যাটার্ণ

এডাপ্টার ডিজাইন প্যাটার্ণ

ইটারেটর ডিজাইন প্যাটার্ণ

চেইন অফ রেসপন্সিবিলিটি ডিজাইন প্যাটার্ণ

অবজারভার ডিজাইন প্যাটার্ণ

কম্পোজিট ডিজাইন প্যাটার্ণ

মেমেন্টো ডিজাইন প্যাটার্ণ

এমভিসি (MVC) ডিজাইন প্যাটার্ণ

ব্রীজ ডিজাইন প্যাটার্ণ

মিডিয়েটর ডিজাইন প্যাটার্ণ

ভিজিটর ডিজাইন প্যাটার্ণ

স্টেট ডিজাইন প্যাটার্ণ

টেমপ্লেট মেথড ডিজাইন প্যাটার্ণ

কমান্ড ডিজাইন প্যাটার্ণ

ফ্যাসাড ডিজাইন প্যাটার্ণ

ফ্লাইওয়েট ডিজাইন প্যাটার্ণ

নাল অবজেক্ট ডিজাইন প্যাটার্ণ

বিল্ডার ডিজাইন প্যাটার্ণ


সফটওয়্যার আর্কিটেকচার



ভার্সন কন্ট্রোল সিস্টেম (GIT)



সফটওয়্যার টেস্টিং



ডাটাবেজ সিস্টেম



আর্টিফিশিয়াল ইন্টিলিজেন্স, মেশিন লার্নিং



অন্যান্য


এপিআই (এপ্লিকেশন প্রোগ্রামিং ইন্টারফেস)

স্কেলিং এন্ড পারফর্মেন্স অপটিমাইজেশন

ক্রিপ্টোগ্রাফি

অন্যান্য


প্রোগ্রামিং ল্যাঙ্গুয়েজ টিউটোরিয়াল সিরিজ


পাইথন (Python)

জাভা (Java)

সি (C)

সি প্লাস প্লাস (C++)

জাভাস্ক্রিপ্ট (Javascript)

পিএইচপি (PHP)

গো-ল্যাং (golang)

ক্লোজার (Clojure)

স্ক্যালা (Scala)


বই



অনুপ্রেরণা এবং ক্যারিয়ার এডভাইজ