/competitve_programming_library

Primary LanguageC++MIT LicenseMIT

competitve_programming_library

Author: Nguyen Anh Tuan (gsdt) MIT License

Math

Modulo

Matrix

  • Supported: add, subtract, multiply, power
  • Operator () overloaded, ex: M(1,2) = 12

Geomatrix

Point

  • Get distance to another point

Circle

  • Create new circle from three points
  • Get center and radius

Gaussian Elimitation

There are two version:

Usage:

  • Contructor: input an matrix to solve.
  • solve(): Solve equation

FFT - multiplying two polynomials

Data structure

Fenwick Tree

  • add(pos, value): add some value to position pos.
  • set(pos, value): set a value to position pos.
  • sumToPosition(pos): get sum from first position to pos.
  • sumOfRage(start_pos, end_pos): get sum from start_pos to end_pos.
  • operator []: for get data, not for set data.
  • clear(): remove all data from tree.
  • size(): get number of element in tree.

Disjoin Set Union (updated: 09:22AM 18/05/2019)

  • unionSets(a, b): join two set has element a and b.
  • findSet(a): find root of set a.
  • isSameSet(a, b): test if set a and set b is same.
  • getSetSize(a): number of element in set a.

Sum-SegmentTree

  • SegmentTree(n): create segment tree to manage n element.
  • update(l, r, v): increasing value from l to r by value v.
  • query(l,r): query sum from l to r.

Graph

Adjacency List Graph

  • AdjacencyListGraph(n): create graph with n+1 vertex: from 0 to n.
  • addDirectedEdge(startVertex, endVertex, weight = 1): add an weighted directed edge.
  • addUndirectedEdge(firstVertex, secondVertex, weight = 1): add an weighted undirected edge.
  • showGraph(): show current graph.
  • shortest(startVertex, endVertext): using Dijkstra alogrithm find shortest path between to vertex. Return shorted path and direction. This implementation passed SPOJ