algorithm_py

Algorithm template for online contests, available on

• Codeforces(pypy 3.9.10)
• Atcoder(Python 3.8.2 | pypy 3.6.9)

basic usage

• basic
• input and output
• math and cmath
• itertools
• collections
• regular expressions

algorithm template

• data structure

  • Segment Tree
  • Lazy Segment Tree (Monoid)
  • ZKW Segment Tree
  • Fenwick Tree
  • Sparse Table
  • Union Find
  • Encoded Dict
  • Sorted List
  • Sorted Blocks

• math and number theory

  • Quick Power
  • Binomial
  • Modulo Integral
    • Note: this's not faster than python big number with proper modulo operations
  • Prime Table
  • Exgcd and Chinese remainder theorem

• graph

  • BFS
  • Colorize bipartite graph
  • Topo sort
  • Shortest path
    • Floyd $O(n^3)$
    • Single source
      • $O(n)$ on DAG
      • Dijkstra
      • Spfa
  • Minimal spinning tree
    • Prim
    • Kruskal
  • MaxFlow
    • Dinic

• string

  • 1d Hash
  • KMP
  • Manacher
  • Longest Palindromic Prefix
  • Binary Trie(Min XOR)
  • Trie

• geometry

  • Point (E^d)
    • quaternion
    • rotate
    • matrix (row major)
    • polar_cmp
    • find_points_in_aabb
  • Segment
    • intersection
    • point on segment
    • projection of point
    • distance to point / segment
  • Plane
    • projection of point / segment
  • Matrix
    • from translate
    • from rotate
    • from scale
  • Triangle
    • normal
    • area
    • bounding box
    • centriod
    • incircle (内心)
    • circumcircle (外心)
    • point in triangle
    • uniform sample in triangle(three kinds of algorithm)
  • Polygon
    • is convex or not
    • signed area / area
    • centriod (area based)
    • triangulation by earcut algorithm
    • point in polygon
  • Convex Hull
    • 2d quick convex hull from point cloud
  • Delaunay Trianglation
    • Fortune algorithm (o(n log n))
  • other

• bit tricks

  • BitSet

• list tricks

errors and other notes

known pypy errors

• pypy notes

sqrt precision error

s = int(1e18)-2

x = math.floor(math.sqrt(s))
while (x+1) * (x+1) <= s: x += 1
while x * x > s: x -= 1

Time complexity of python operations

list

O(1)

• Append
• pop last
• get item
• set item
• get length

O(k)

• get slice
• extend(k)

O(n)

• copy
• insert
• pop(id)
• x in list
• del item
• iteration
• min, max, sum

O(n log n)

• sort

collections.deque

O(1)

• append
• appendleft
• pop
• popleft

O(k)

• extend
• extendleft
• rotate

O(n)

• copy
• remove

set

O(1)

• x in s

O(len(s))

• s-t
• s^t

O(len(t))

• s.difference_update(t)
• s.symmetric_difference_update(t)

O(min(len(s), len(t)))

• s&t

O(len(s)+len(t))

• s|t

dict

O(1)

• k in d
• get item
• set item
• del item

O(n)

• copy
• iteration

heapq

O(logn)

• heappush
• heappop
• heappushpop
• heapreplace

O(nlogk)

• merge

O(n)

• heapify

O(n+klog(n))

• nsmallest
• nlargest

bisect

O(logn)

• bisect
• bisect_left
• bisect_right

O(n)

• insort
• insort_left
• insort_right

References

• TimeComplexity - Python Wiki
• heapq — Heap queue algorithm — Python 3.10.6 documentation
• Python's heapq module
• bisect — Array bisection algorithm — Python 3.10.6 documentation

complexity analysis

Big O

Big O notation is used to give an upper bound on the asymptotic growth

• O(1): constant
• O(log n): logarithmic
• O(n): linear
• O(n log n): log-linear
• O(n^k): polynomial, where k is a constant
• O(c^n): exponential, where c is a constant

tricks

mock interactive problem

diff with brute force methods

python gen.py > data.in && \ # generate random data
    python brute.py > brute.out && \ # brute force output
    python e.py > e.out && \ # algorithm output
    diff e.out brute.out # diff