Programming Notes

@programmingNotes

Public team

Community (0)
No community contribution yet

Joined on Jun 19, 2021

  • Motivation Given a list of elements, we want to calculate cumulative total based on an associative binary operation. Moreover, efficient modification is desired. Naive Concept Using an array arr to store each element in the original list.
     Like  Bookmark
  • Motivation Design a data structure that stores a partition of a set. With the operations of union, find, etc. Naive Way-A: Update the Set Each Element Belongs to Find: $O(1)$ Make Union: $O(N)$
     Like  Bookmark
  • Range Minimum (Maximum) Query class SegmentTree { public: SegmentTree(size_t size) : N(size), arr(size << 2, 0), tag(size << 2, 0) {} int query(int left, int right) { return query(1, 1, N, left, right); } void modify(int left, int right, int val) {
     Like  Bookmark
  • --- tags: Data Structure title: BigInteger ---
     Like  Bookmark
  • Programming Notes Data Structure BigInteger Fenwick Tree Disjoint Sets Segment Tree
     Like  Bookmark
  • Dinic's Algorithm Sample Code struct Dinic { Dinic(size_t N, int s, int t) : N(N), s(s), t(t), adj(N) {} struct Edge { int to; int cap; int rev;
     Like  Bookmark
  • Sample Code vector<vector<int>> adj(n); vector<bool> vis(n); vector<int> times(n, -1), low(n, -1); int count = 0; int ans = 0; function<void(int, int)> dfs = [&](int u, int p) { vis[u] = true;
     Like  Bookmark
  • Prim's Algorithm Sample Code Kruskal's Algorithm $\text{Input: } G=(V,E)\text{ and a weight function }w:V\times V\rightarrow\mathbb{R}$ $\text{Output: } T=(V,F) \text{ where }F\subseteq E\text{ and }T\text{ is a spanning tree of }G.$ $1F\leftarrow\varnothing$ $2\textbf{for each }e={u,v}\text{ in }E \text{ ordered by }w(u,v)\text{ do}$ $3~~~~~~~~\textbf{if }\text{there is no cycle in }H=(V,F\cup e)\text{ do}$ $4F\leftarrow F\cup e$
     Like  Bookmark
  • Special case: 2-Dimensional space Graham's Scan First choose a trivial point $p_0$ that it must be in convex hull (leftmost and lowest). sort all the other points in polar angle order, getting ${p_1, \dots,p_n}$. let $s={p_0,p_1}={s_2,s_1}$(reversed order). let $i=2$. while $i<n$ do the following: If $|s|<2$ or $\angle p_is_1s_2$ is convex, then let $s=s\cup{p_i}$, and $i=i+1$. If not, $s=s\setminus{s_1}$.
     Like  Bookmark
  • --- tags: Geometry title: Closest Pair ---
     Like  Bookmark
  • --- tags: Graph Theory title: Lowest Common Ancestor ---
     Like  Bookmark
  • --- tags: Dynamic Programming title: Weighted Perfect Matching ---
     Like  Bookmark
  • --- tags: Dynamic Programming title: Longest Common Subsequence ---
     Like  Bookmark
  • --- tags: Dynamic Programming title: Longest Increasing Subsequence ---
     Like  Bookmark
  • Failure Function vector<int> failure_function(const string& s) { vector<int> failure(s.length(), -1); int p = -1; for (int i = 1; s[i]; ++i) { while (p != -1 && s[p + 1] != s[i]) p = failure[p]; if (s[p + 1] == s[i]) ++p;
     Like  Bookmark
  • Fractional Knapsack Problem Input: A sequence of weights and another of values, the capacity of knapsack. Output: Maximum value. (You can cut item into pieces.) Greedy Sorted by $\dfrac{\text{value}}{\text{weight}}$ of each item, always choose the biggest one in that moment. Since every unit of space in the knapsack contains the most valued item,
     Like  Bookmark
  • Problem Input: number of cites, number of roads, a sequence of roads Output: Minimum cost of travelling through all the cities. Naive: Exhaustive Search All permutation of cities. Time complexity: $O(n!)$, where $n$ is the number of cities.
     Like  Bookmark
  • --- tags: Useful Headers title: (unknown) ---
     Like  Bookmark
  • Problem Description Given a DAG (directed acyclic graph), find out a sequence ${a_1,\dots,a_n}$ such that if $i<j$, you need to go through $a_i$ before you go to $a_j$. Kahn's Algorithm vector<vector<int>> adj; vector<int> topological_sort() { int n = adj.size();
     Like  Bookmark
  • Kosaraju's Algorithm Notion: Strongly connected components will also be strongly connected in transposed graph. vector<vector<int>> adj, radj; vector<int> timeStamp, scc; vector<bool> vis; void dfs(int u) { vis[u] = true;
     Like  Bookmark