SHARE
TWEET

Rafid

a guest Nov 21st, 2019 111 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. \documentclass[twoside]{book}
  2. \usepackage[utf8]{inputenc}
  3. \usepackage{geometry}
  4. \geometry{a4paper, bottom=1in, right=1in, left=1.5in, top=1in}
  5. \usepackage{url}
  6. \usepackage{minted}
  7. \usepackage{amsmath}
  8. \usepackage[toc,page]{appendix}
  9.  
  10. \setminted{linenos, tabsize=4, breaklines, frame=lines, framesep=2mm}
  11. \usemintedstyle{perldoc}
  12. % \usemintedstyle{bw}
  13.  
  14. % errors
  15. \DeclareUnicodeCharacter{2264}{ }
  16. \DeclareUnicodeCharacter{2200}{ }
  17.  
  18. \title{{\Huge{T E M P L A T E S}}}
  19. \author{\Large{R A F I D}}
  20. \date{} % Nov 13, 2019
  21.  
  22. \begin{document}
  23.  
  24. \maketitle
  25.  
  26. \tableofcontents
  27. % \pagebreak
  28.  
  29.  
  30. \begin{chapter}{Data Structures}
  31.     \section{Binary Indexed Tree}
  32.     Faster than Segment Tree. Useful if query $Q(l, r) \equiv Q(1, r) \setminus Q(1, l-1)$.
  33.     \inputminted{cpp}{src/ds/binary-indexed-tree-bit.cc}
  34.    
  35.     \section{Centroid Decomposition}
  36.     For a given tree, reconstructs the tree such that height is at most $O(\log n)$. Also, consider any two arbitrary vertices $A$ and $B$ and the path between them (in the original tree) can be broken down into $A-C$ and $C-B$ where $C$ is LCA of $A$ and $B$ in the centroid tree.
  37.     \inputminted{cpp}{src/ds/centroid-decomposition.cc}
  38.    
  39.     \section{Heavy Light Decomposition}
  40.     Decomposes a tree to a set of paths. A path $u-v$ uses at most $\log N$ paths. Useful for path updates, subtree update and path query.
  41.     \inputminted{cpp}{src/ds/heavy-light-decomposition-hld.cc}
  42.    
  43.     \section{Lowest Common Ancestor}
  44.     \inputminted{cpp}{src/ds/lca-sparse-table.cc}
  45.    
  46.     \section{Mo's algorithm}
  47.    Useful for answering offline range queries in $O((N+Q)\sqrt{N})$.
  48.    \inputminted{cpp}{src/ds/mo.cc}
  49.    
  50.    \section{Segment Tree}
  51.    
  52.    \subsection{Lazy Propagation}
  53.    \inputminted{cpp}{src/ds/segment-tree-lazy.cc}
  54.    
  55.    \subsection{Point Update Range Query}
  56.    \inputminted{cpp}{src/ds/segment-tree-purq.cc}
  57.    
  58.    \section{Trie}
  59.    \inputminted{cpp}{src/ds/trie.cc}
  60. \end{chapter}
  61.  
  62. \begin{chapter}{Dynamic Programming}
  63.    \section{Convex Hull Trick}
  64.    For a given set of lines $y = m_i x + c_i$, maintains the lower (or upper) hull.
  65.    
  66.    \subsection{Dynamic (General)}
  67.    Finds the minimum (or maximum) $y$ for a query $x$ in $O(\log N)$ time.
  68.    \inputminted{cpp}{src/dp/convex-hull-trick-dynamic.cc}
  69.    
  70.    \subsection{Special Case}
  71.    For lines with non-increasing slope, a bunch of sorted queries can be answered in constant time on the fly.
  72.    \begin{equation*}
  73.        dp(i) = \min\limits_{j<i} \{dp(j) + b(j) \cdot a(i)\}
  74.    \end{equation*}
  75.    Condition: $b(j) \geq b(j+1)$ and $a(i) \leq a(i+1)$ \\
  76.    Complexity: $O(n)$ \\
  77.    \begin{equation*}
  78.        dp(i, j) = \min\limits_{k<j} \{dp(i-1, k) + b(k) \cdot a(j)\}
  79.    \end{equation*}
  80.    Condition: $b(k) \geq b(k+1)$ and $a(j) \leq a(j+1)$ \\
  81.    Complexity: $O(kn)$
  82.    
  83.    \inputminted{cpp}{src/dp/convex-hull-trick-special.cc}
  84.    
  85.    \section{Divide \& Conquer Optimization}
  86.    \begin{equation*}
  87.        dp(i, j) = \min \limits_{k \leq j} \{ dp(i-1, k) + C(, j) \}
  88.    \end{equation*}
  89.    Let $opt(i,j)$ be the value of k that minimizes the above expression. If $opt(i, j) \leq opt(i, j+1)$, we can optimize to $O(nm \log n)$ from $O(nm^2)$ where $1 \leq i \leq n$ and $1 \leq j \leq m$.
  90.    \inputminted{cpp}{src/dp/divide-conquer-dp.cc}
  91.    
  92.    \section{Subset over Sum (SOS DP)}
  93.    \inputminted{cpp}{src/dp/sos-dp.cc}
  94. \end{chapter}
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top