Python3 implementation of competitive programming library inspired by spaghetti-source/algorithm.

日本語のREADME

• These are my Python3 implementations of snippets and algorithms, which are written for studying/understanding algorithms.

• These codes are published in public domain. You can use the codes for any purpose without any warranty.

• Data Structure

  • A dequeue that can perform random accesses with O(1)
  • Alternatives to ordered set (set) in C++
  • BIT (Binary Indexed Tree, Fenwick Tree) and inversion number
  • Doubly Linked List
  • Manage two-dimensional lists as one-dimensional lists
  • Range Add Query (RAQ) and Range Sum Query (RSQ)
  • Segment tree
  • Self-balancing binary search tree using pivot values (ordered set in C++)
  • Sorted multiset
  • Sorted set
  • Sum of top kth (the smallest / the largest)
  • The K-th greatest value among the first i terms of P (i = K, K + 1, ..., n)
  • Trie Tree

• DP

  • LCS (Longest Common Subsequence)
  • LIS (Longest Increasing Subsequence)
  • Template of TSP (Traveling Salesman Problem)

• Geometry

  • Calc area of triangle
  • Calc line passing through points
  • is_colinear
  • Is on circle / Is intersected

• Graph

  • Bellman Ford
  • BFS (Breadth-First Search) template
  • Cycle detection and reconstruct of directed and undirected graphs (first one only)
  • DFS (Depth-First Search) template
  • Dijkstra
  • Is bipartite
  • Lowest Common Ancestor
  • Rooted Tree
  • SCC (Strongly Connected Component)
  • Topological Sorting
  • Tree Distance
  • Union Find Tree (1D and 2D)
  • Union Find Tree (weighted)
  • Warshall Floyd

• Math

  • Binary search
  • Calculate rotation / reversal of coordinates using matrices
  • Combination
  • Compress coordinate
  • Digit
  • Direct product
  • Extended Euclidean algorithm
  • Factorization
  • Generate divisors
  • Interger carry
  • Least Common Multiple (LCM)
  • List of indices whose bit is 1
  • Matrix rotation
  • N-ary number
  • Pascal's triangle (binomial coefficients, nCr)
  • Permutation (nPr with mod)
  • Prime
  • Sort using key
  • Ternary search

• String

  • Add offset to alphabet
  • Get offset
  • Popcount
  • Rolling Hash
  • Run Length Encoding / Decoding
  • To titlecase
  • Z algorithm

• Technique

  • Cumulative Sum 2D
  • Doubling (template)
  • Find the index before and after a specific value and the same value for an array, counting the numbers in an interval
  • Two-pointer Techinique (template)
  • Count dot(.) cells up, down, left and right in grid
  • Wrapper of bisect

• Python 3.11.0+
• pip

• pytest
• GitHub Actions

1. Install this repository by the following method.
2. Search for snippets and algorithms as needed.

Paste the following commands at a Terminal prompt.

git clone https://github.com/KATO-Hiro/Somen-Soupy

Readme Driven Development; RDD^archive.org

Software licenses for competitive programming library

spaghetti-source/algorithm

Starting with the Python workflow template

@KATO-Hiro

CC0