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:

• Double data type
• Integer data type Passed Codeforce

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