Skip to content

Latest commit

 

History

History
185 lines (157 loc) · 7.76 KB

README.md

File metadata and controls

185 lines (157 loc) · 7.76 KB
Raw

Competitive Programming Data Structures and Algorithms

About

Contains a library of premade templates for common data structures and algorithms found in competitive programming

Data Structures

Segment Tree

  • About Segment Trees

    • Use for queries over ranges of data
      • Operations on said ranges must be associative

  • Functionality

    • Builds from arr O(N)
    • Updates individual values O(logN)
    • Queries on associative range O(logN)
    • Prints debug elements O(N)
    • Does not currently support lazy propagation

  • segment_tree.cpp

    • Declare with c++ template
      • e.g. SegTree<long long> seg_tree(size, default, associativeFunction);
    • Debug print requires declared template type supports << insertion operator
      • Stream io with << is slower than stdio.h in C++ so be careful with using this everywhere

  • segment_tree.py

    • Note that this class has not been optimized for maximized efficiency
      • All that can be promised is operations in accordance with the previously defined runtime complexities

Sparse Table

  • About Sparse Tables
    • Similar to Segment Trees in that you can efficiently compute queries over associative ranges
    • Difference with segment tree is that it is cannot handle dynamic updates
    • Recommended that if presented with the choice go instead with the segment tree as is is more flexible
      • only turn to this if you are struggling with the segment tree
  • Functionality
    • Currently it is implemented to solve the range minimum query problem
    • Constructs itself in O(NlogN)
    • Each query is O(1) -> this is the advantage of sparse tables: if you have alot of queries over a static range
  • sparse_table.py
    • Do not ask me how it works, I copied it from Halim
      • It works, thats all that needs to matter

Suffix Array

  • About Suffix Arrays
    • By sorting the suffixes of a string a lot of powerful computation can be done
      • These often involve using some sort of binary search query on the data
    • A suffix array is efficiently stored as an array of integers representing the order of the suffixes by their indices
    • Alongside the suffix array is the longest common prefix (LCP) array
      • This array contains between suffixes adjacent to each other in the suffix array the length of their common prefix
      • What is important about such is the following:
        • For any list of sorted strings, the LCP between any two strings is the minimum value in between their indices in the LCP array
        • Thus any range minimum query (RMQ) structure can be used to calculate the longest common prefix between any two suffixes in log(N) time
  • Functionality
    • Constructs the suffix array (O(NlogN)) and LCP array (O(N))
    • The corresponding suffix array and LCP array are easily accessible for computation
    • TODO: will add a basic segment tree for LCP queries (may want to change to Sparse Query Data Table)
  • suffix_array.cpp
    • Be sure to read the commonts at the top of the namespace
    • order of construction must be followed precisely
    • an example declaration follows:
std::cin >> SuffixArray::str;
SuffixArray::str += '$';		// Having a trailing character is necessary for the sort to perform properly
SuffixArray::size = SuffixArray::str.length();
SuffixArray::buildSA();
SuffixArray::buildLCP();
SuffixArray::printSA();
SuffixArray::printLCP();
  • suffix_array.py
    • Everything is done through the SuffixArray class interface
    • You must append special characters like '$' yourself
    • A suffix array and a rank array are created in the constructor
    • calling longestCommonPrefixArray() constructs and returns the LCP array

reTrieval Tree

  • About reTrieval Trees
    • A reTrieval tree (Trie) - or prefix tree - is a tree structure for efficiently matching strings in a set
  • Functionality
    • Builds the Trie in O(NW) where N is the number of strings and W is the length of each string
    • IMPORTANT: Can only handle strings of the 26 lowercase characters
      • This may have to be manually changed depending on the problem
    • Can compute whether a particular word exists in the Trie in O(W)
    • Can perfom efficient longest common prefix queries in O(log(W))
  • trie.cpp
    • Specific details of Trie implementation are intentially hidden
    • If you would like direct access on the Trie there is an accessor method for such
    • IMPORTANT: if you plan on using LCP(), you must first call buildLCA()
    • Memory management is guaranteed to be handled for you so long as you do not use direct access to the internal TrieNode structure

Union Find

Matrix

  • Supports basic operations such as multiplication, addition, transpose
  • TODO: Work in conjunction with Floyd Warshalls

MathVector

  • implement dot product, cross product, angle between vectors, sum of vectors, to polar coords, etc

Red Black Tree for Python Plebs

Priority Queue for Simultaneous OOP simps and Python Plebs

  • About Priority Queues
    • using a heap, can access the maximal (or minimal) element in a set in O(logN)
  • Functionality
    • Essentially a wrapper for Python's heapq library
    • implements basic push, pop, peek operations
    • Allows construction with a key() function which is used for comparison (similar to sorted())

Fenwick Tree (BIT)

Algorithms

TODO - Make some algorhythms

Common Mathematical Operations

  • Most c++ math functions are in math_functions.cpp with exception of euler's totient function
  • it recommended not to copy the entire namespace but rather just the functions you will need

Modulo

  • This is included for C++ because C++ does not handle negative modulo very well
    • -11%5 should result in 4 however C++ evaluates this as -1
      • our implementation correctly evaluates modulo(-11,5) as 4

Power Over Modulo

  • Finds (b^k)%mod in log(k) time.
  • Not implemented in python because math.pow() already has this functionality
  • cannot currently handle negative base currently

Divide Over Modulo

  • Finds (a/b) % mod
  • This only works for when mod is a prime number

GCD - Greatest Common Divisor

  • Efficiently returns the greatest common divisor between two integers

LCM - Least Common Multiple

  • Efficiently returns the least common multiple between two integers

Euler's Totient Function

  • Note that this is implemented in totient.cpp
  • Counts the number of integers between 1 and N that are relatively prime (coprime) with N
    • a and b are coprime if gcd(a,b) == 1

Convex Hull

Tarjans DFS

  • Tarjans algorithm, or DFS Low Link, is a versatile algorithm that can solve problems such as Strongly Connected Components (SCC) and Articulation Points/Bridges
  • tarjan_scc.cpp
    • As the name indicates, this implementation solves the Strongly Connected Components problem
    • searches for a "low-link" or, in other words, a connection to node already searched in the dfs
      • the presence of a low-link indicates the existence of a strongly connected component along that path

Max Flow

Max Flow Min Cost

Dijkstras

Bellman-Ford

  • Single Source Shortest Path for Negative Weighted Graphs
    • Dijkstras will fail on a negative weighted graph
    • Bellman-Ford handles negative weights properly
  • bellman_ford.cpp
    • At the top of the file are some typedefs and constants that should be set by the user according to the problem
    • The bellmanFord() function returns a vector (typedef'd to Costs)
      • the ith index of this vector is the cost of the shortest path from the source to the ith node
      • if the value is INFINITY that means the node is unreachable
      • if the value is NEG_INFINITY that means there exists a negative cycle on the shortest path so the cost is indeterminate

Floyd-Warshalls

KMP

Aho-Corasick

Longest Increasing Subsequence

  • Given an array of data returns the elements of the longest increasing subsequence
  • lis_nlogn.cpp
    • Solves the problem in NlogN
      • compared to the easier to understand N^2 DP solution