nthu-cp/nthu-cpp

前人種樹，後人持久化🌴

nthu-cpp's Issues

Add Monotone optimization(四邊形優化)

Outline

• Definition of concave/convex totally monotone
• 1D/1D concave/convex monotone
  • 1D/1D common form
  • Transform the problem into a two-dimensional array extremum query
  • using monotonicity to speed up dp calculation
  • Implement & application
• Monge condition
  • Theory and equivalent form
  • Proof Monge condition implies monotonic split point
• Knuth Optimization - 2D/1D convex monotone (四邊形優化)
  • 2D/1D common form
  • monotonic split point speed up calculation
  • Time complextiy
  • Implement & application
• Transfer point monotonic (轉移點單調)
  • main processing form
  • ARC067 D

References

https://tioj.ck.tp.edu.tw/uploads/attachment/11/54/7.pdf
https://slides.com/kevin_zhang/deck-8c1c8e/
http://www.chino.taipei/code-2016-0402Algorithm-DP優化之四邊形不等式優化/
http://pisces.ck.tp.edu.tw/~peng/index.php?action=showfile&file=f4c79992d9e0b5ee4aa9fd7db9115c673b2cf6150
http://momo-funnycodes.blogspot.com/2012/06/tioj-1449-extreme.html
https://cp-algorithms.com/dynamic_programming/knuth-optimization.html
https://oi-wiki.org/dp/opt/quadrangle/
https://core.ac.uk/download/pdf/82676028.pdf

Add chapter Greedy

Based on: https://drive.google.com/file/d/1cks-b5ELqYp2el-V8-WfJxZbb2An8AQ-/view?usp=sharing

Add Centroid Decomposition

Introduction to Centroid Decomposition

Centroids

• What is a centroid
• How to find centroids
• Application

Centroid Tree

• What is a centroid tree
• How to build a centroid tree
• Property

Problems

• Codeforces Xenia and Tree
• Codeforces Ciel the Commander
• CSES Fixed-Length Paths I
• CSES Fixed-Length Paths II
• Codeforces Close Vertices
• CS academy Black-White-Tree

References

• USACO Guide, Centroid Decomposition
• oi wiki, 樹分治
• Codeforces, Centroid Decomposition on a tree(Beginner)

Add Game Theory

Outline

• Winning and losing states' definition and properties
• Introduction of Nim Game and Grundy numbers
• Solution and Proof of Correctness of basic Nim game
• Sprague-Grundy Theorem
• Some extensions of Nim game

Exercises

• https://cses.fi/problemset/task/1729
• https://cses.fi/problemset/task/1730
• https://cses.fi/problemset/task/1098
• https://cses.fi/problemset/task/1099
• https://atcoder.jp/contests/abc297/tasks/abc297_g
• https://atcoder.jp/contests/abc255/tasks/abc255_g
• https://codeforces.com/contest/1738/problem/C
• https://codeforces.com/contest/1823/problem/E

References

• https://codeforces.com/blog/entry/66040
• https://cp-algorithms.com/game_theory/sprague-grundy-nim.html
• https://cp-algorithms.com/game_theory/games_on_graphs.html
• https://oi-wiki.org/math/game-theory/impartial-game/
• https://usaco.guide/adv/game-theory?lang=cpp
• https://www.topcoder.com/thrive/articles/Algorithm%20Games

Todo list for release

• foreword
• Introduction to CP an NTHU CP Team
• How to Practice
• Calendar
• Update Contest information
• Update contribution note
• Update useful resources
• doc for clerical work if you want to host an event or apply for reimbursement
• C++ programming tips
• Give each topic an intro.md
• Update GitHub repo information
• Google analytic of the website

Add Flow

Outlines

• Introduction to Network Flow and definition of some terms
• State and prove The Max-flow Min-cut Theorem
• Ford-Fulkerson's algorithm
  • Introduction to Augmenting path
  • A common wrong method of finding max-flow
  • Detail process of the algorithm
  • Time complexity and the correctness of the algorithm
  • Template code
• Edmonds-Karp's algorithm
  • The flaw of Ford-Fulkerson's algorithm and the method of optimization
  • Detail process of the algorithm
  • Time complexity and the correctness of the algorithm
  • Template code
• Solving some related problems

References

• https://web.ntnu.edu.tw/~algo/Flow.html
• https://oi-wiki.org/graph/flow/

Add chapter Sparse Table

• Introduction of sparse table
• RMQ
• Some problems

Add chapter Graph

• Graph Definition
• Graph Storage
• Graph Traversal
• Tree Definition
• Binary Tree Traversal

Add Fast Fourier Transform (FFT)

Introduction to Fast Fourier Transform (FFT)

Mathematical Background

• The principal nth root of unity
• Representing polynomials
  • Coefficient representation
  • Point-value representation
• Vandermonde matrix and its properties

DFT && Inverse DFT

• Introduction
• Calculation (by Vandermonde matrix)

FFT algorithm

• Find DFT
• Divide and conquer
• Find Inverse DFT

Exercises

• Easy
  • SPOJ Polynomial Multiplication [3]
• Medium
  • SPOJ Maximum Self-Matching [4]
  • SPOJ Ada and Nucleobase [5]
  • Codeforces Yet Another String Matching Problem [6]
  • Codeforces Lightsabers (hard) [7]
  • Codeforces Running Competition [8]
  • Codeforces Dasha and cyclic table [9]
  • Kattis A+B Problem [10]
  • Kattis K-Inversions [11]

References

• [1] Introduction to Algorithms Fourth Edition p. 877 ~ p. 893
• [2] CP Algorithm, Fast Fourier transform https://cp-algorithms.com/algebra/fft.html
• [3] https://www.spoj.com/problems/POLYMUL/
• [4] https://www.spoj.com/problems/MAXMATCH/
• [5] https://www.spoj.com/problems/ADAMATCH/
• [6] https://codeforces.com/problemset/problem/954/I
• [7] https://codeforces.com/problemset/problem/958/F3
• [8] https://codeforces.com/contest/1398/problem/G
• [9] https://codeforces.com/contest/754/problem/E
• [10] https://open.kattis.com/problems/aplusb
• [11] https://open.kattis.com/problems/kinversions

Add Inversion Pair

Outline

• Definition & mathematical meanings
• Upper bound of # inversions & lower bound of comparison-based sorting
• Efficient approaches to count inversions
  • Merge sort
  • Data structures that support single update and range query like BIT (a.k.a. Fenwick tree)
  • Data structures that support $k^\text{th}$ query
• Problems related to inversions
• Dynamic inversions
• Other pairwise problems

Problems

• UVa 10810 Ultra-QuickSort
• UVa 11858 Frosh Week
• 2021 ICPC Asia TOPC C. A Sorting Problem
• 2022 ICPC Asia Taoyuan Regional C. Distance Calculator (No OJ)
• AtCoder Beginner Contest 190 F - Shift and Inversions
• SPOJ SWAPS - Counting inversions
  And so forth...

Reference

• Fenwick Tree - Algorithms for Competitive Programming
• 树状数组 - OI Wiki
• 归并排序 - OI Wik
• 置换和排列 - OI Wiki
• 划分树 - OI Wiki

In fact, there are few online resources that is mainly focused on inversions :(

Add Aliens Optimization

Aliens Optimization

• Introduction to Aliens Optimization
  • Preface: DP Optimizations & Techniques
  • Backgrounds: WQS binary search & IOI 2016 Aliens
  • Overview: Properties of the related problem
• Analysis of the technique (Based on a problem)
  • Comparison of Greedy and DP approches
  • Transform into a concave function & binary search
  • Proof and Analysis
  • Implementation & Conclusion
• Problem
  • https://codeforces.com/problemset/gymProblem/102059/M
  • https://tioj.ck.tp.edu.tw/problems/2039
  • https://www.luogu.com.cn/problem/P2619
  • https://codeforces.com/problemset/problem/1279/F
  • https://ioinformatics.org/files/ioi2016problem6.pdf

Reference

• https://soi.ch/wiki/alien-optimization/
• https://pufanyi.github.io/%E7%94%9F%E6%88%90%E6%A0%91%E5%85%A5%E9%97%A8/Train2012-sol-wqs.pdf
• https://tioj.ck.tp.edu.tw/uploads/attachment/5/51/10.pdf
• https://hackmd.io/@wiwiho/cp-note/%2F%40wiwiho%2FCPN-aliens
• https://medium.com/@bluezebragames/dynamic-programming-optimization-the-aliens-trick-9138176287cf
• https://prutekoi.github.io/post/xue-xi-bi-ji-wqs-er-fen-tu-you-hua/
• https://blog.csdn.net/emm_titan/article/details/124035796
• https://www.cnblogs.com/CreeperLKF/p/9045491.html
• IOICamp 2022 handout

Add chapter Mo's Algorithm

Outline

• introcdution
• 帶修改莫隊
• 回滾莫隊
• 在線莫隊

References

Rearrange arithmetic function

• convolution is not yet mentioned before or in sqrt decomposition

Add Suffix Array

Introduction to Suffix Array

Implementation

• 倍增法
• SA-IS

Problems

Reference

• https://cp-algorithms.com/string/suffix-array.html
• https://oi-wiki.org/string/sa/

Add KMP

Outline:

• Introduction to KMP algortithm
  • Prefix function
  • Time complextiy
  • Search for a substring in a string
• Applications
  • Counting the number of occurrences of each prefix
  • The number of different substring in a string
  • Remove all occurrences of string t in string s using KMP Algorithm
  • Automaton of KMP

Problems:

https://codeforces.com/problemset/problem/535/D
https://codeforces.com/problemset/problem/471/D
https://codeforces.com/contest/432/problem/D

Reference:

https://cp-algorithms.com/string/prefix-function.html
https://oi-wiki.org/string/kmp/
https://www.geeksforgeeks.org/remove-all-occurrences-of-string-t-in-string-s-using-kmp-algorithm/?ref=rp
https://labuladong.gitbook.io/algo-en/i.-dynamic-programming/kmpcharactermatchingalgorithmindynamicprogramming#i.-overview-of-kmp-algorithm

Add chapter Segment Tree Beats

Introduction to Segment Tree Beats

• Construct tree node (sum, max1, max2, maxc, min1, min2, minc, lazy tag)
• Construct tree (build)
• Range modification
  • update_add / push_add
  • update_max / push_max
  • update_min / push_min
  • push_down
• Merge functions
• Range query

Add topic: how to set a problem

As title.

• introduce the workflow
• tutorial for some tool such as testlib.h, tps, polygon
• tips for generations testcase

Add chapter BIT(Fenwick Tree)

• Introduction of BIT
• Some advanced techniques of BIT
• Problem set

Add chapter basic dp

Based on: https://drive.google.com/file/d/1cks-b5ELqYp2el-V8-WfJxZbb2An8AQ-/view?usp=sharing

Add chapter Bit operation and their trick

• Introduction to bit and bytes
• Basic bit operation / truth table
• Some trick for using bit operation
• Eight queen
• Bit representation / bitmask
• Enumerate all subset and submask

Add Treap

Treap

Introduction to Treap

//Definition of Binary Search Tree, Heap, and Treap

Split-Merge Tree

Introduction

//How it keep self to balance

Treap node

//Create a Treap node

Merge

//Merge two Treap nodes

Split by key

//according to node's key split it to two nodes

Erase, Insert, K-th element, ... some BST operation

Range Queries

//Split by size, save information in Treap node, pull (merge two nodes and update information)

Lazy Tag

//how to push Treap node's lazy tag to node's son

Range Reverse

//use lazy tag to reverse

O(N) build a Treap

//introduction to cartesian tree

Proof Treap's deep is logN

Problems

//some problems use treap will be better or only can use treap to solve it
//for example: TIOJ 1169, cf 702F

References

https://codeforces.com/blog/entry/84017
https://oi-wiki.org/ds/treap/
https://oi-wiki.org/ds/cartesian-tree/
https://cp-algorithms.com/data_structures/treap.html
https://usaco.guide/adv/treaps?lang=cpp

//sorry for my poor English :(

Misc: Introduction to Interactive

Outline:

What's Interactive Problem

Example: Binary Search

Exercises

Codeforces 727C

Codeforces 809B

Codeforces 843B

Codeforces 835E

Codeforces 750F

Codeforces 1033E

Add Convex Hull Trick

Outline

Introduction

斜率/查詢皆單調

說明斜率優化觀念、使用 deque

• 點不用被 pop
• 點需要被 pop

查詢不單調、斜率單調

使用二分搜

斜率不單調

• 李超線段樹
• 動態凸包
• CDQ

/*
以上每個部分都有：

• 例題
• 提出觀察、列出&整理轉移式
• 時間複雜度、實作細節
• 範例 code
• 總結作法與重點

*/

總結

• 統整各情況、列出思考的步驟

Exercises

• 簡述題目、題解
• https://codeforces.com/contest/1083/problem/E
• https://codeforces.com/contest/311/problem/B
• https://codeforces.com/problemset/problem/319/C
• https://cses.fi/problemset/task/2087
  https://cses.fi/problemset/task/2084
• https://tioj.ck.tp.edu.tw/problems/1676
• https://tioj.ck.tp.edu.tw/problems/1745
• https://codeforces.com/contest/932/problem/F
• https://cses.fi/problemset/task/2085
• https://tioj.ck.tp.edu.tw/problems/1921

References

• Oi wiki - 斜率優化
• TIOJ 建中培訓講義
• Algorithms for competetive programming - Convex hull trick
• [Tutorial] Convex Hull Trick — Geometry being useful
• PEGWiki - Convex hull trick
• USACO Guide - Convex Hull Trick
• https://www.cnblogs.com/Xing-Ling/p/11210179.html

Add Huffman Coding and its related problem

Add this chapter under Greedy.

Outline

• Introduce Huffman coding
• Prove the correctness of the greedy algorithm
• Related problem

Add Persistent segment tree

持久化線段樹

引入

什麼是權值線段樹

什麼是持久化線段樹

回到題目

其他練習題

TIOJ 1827 Yet another simple task ^____^

洛谷 P2617 Dynamic Rankings

洛谷 P2633 Count on a tree

洛谷 P3168 [CQOI2015] 任务查询系统

洛谷 P3157 [CQOI2011]动态逆序对

References

https://oi-wiki.org/ds/persistent-seg/

https://tioj.ck.tp.edu.tw/problems/1827

https://www.luogu.com.cn/problem/P2617

https://www.luogu.com.cn/problem/P2633

https://www.luogu.com.cn/problem/P3168

https://www.luogu.com.cn/problem/P3157

Add SCC and 2-SAT

Introduction to Strongly Connected Component

Definition

Property

SCC Compression

Detail process

Time complexity and the correctness

Template code

Tarjan's Algorithm for SCC

Detail process

Time complexity and the correctness

Template code

Kosaraju's Algorithm

Detail process

Time complexity and the correctness

Template code

Introduction to 2-SAT problem

Definition

Transfer 2-SAT to a Graph

Krom's Algorithm

Problems

• Flight Routes Check
• Planets and Kingdoms
• Reachable Nodes
• Reachability Queries
• Giant Pizza
• The Door Problem
• hdu 3062

Add chapter Sqrt Technique

Outline

• square root decomposition on array
• square root decomposition on operation
• Some observation related to sqrt

References

• [Tutorial] Square Root Techniques
• Square Root Decomposition - USACO Guide
• Sqrt Decomposition - Algorithms for Competitive Programming

Add Rolling Hash

Outlines are as the following comments

Add Dynamic Programming on Trees

• Introduction to Dynamic Programming on Trees [1]

  • "Recursive" property of trees (very brief) [2]
  • Classic Example: CSES - Tree Matching [1] [3]
    • Defining a DP state
    • Implementation details
  • Classic Example: Finding the diameter and a center of a tree [4] [5] [6]
  • Exercise: AtCoder Educational DP Contest P - Independent Set [7]
  • Exercise: CSES - Finding a Centroid [8]
  • Exercise: NCPC 2021 NTHU preliminary problem G. Power Network [Reference?]
  • Exercise: Weighted version of some aforementioned problems (no judges known to me)
  • Non-classic Example: Codeforces Round 526 Div. 1 A. (== Div. 2 D.) The Fair Nut and the Best Path [9]
  • Non-classic Example: AtCoder Regular Contest 112 C - DFS Game [10]
  • Exercise: Codeforces Round 800 Div. 1 B. (== Div. 2 D.) Fake Plastic Trees [11]

• DP on Trees with Rerooting [12]

  • Preface: "Dynamic Programming" on Trees or "Divide and Conquer" on Trees? [2] [13]
  • Example: CSES - Tree Distances II [14]
  • Example: AtCoder Beginner Contest 223 G - Vertex Deletion [15]
  • Exercise: AtCoder Educational DP Contest V - Subtree [16]
  • Exercise: Codeforces Round 862 (Div. 2) D. A Wide, Wide Graph [17]

• DP on trees with $o(V)$ states

  • Example: Educational Codeforces Round 106 (Rated for Div. 2) F. Diameter Cuts [18]
    • Implementation: merging one subtree at a time
  • Exercise: Codeforces Round 833 (Div. 2) E. Yet Another Array Counting Problem [19]

• Related Topics
  (will use a few sentences to show how they are related, and links to other NTHU-CPP pages in the future)

  • LCA by Binary Lifting
  • Centroid Decomposition
  • Knapsack Problem on trees

• References

  • [1] https://usaco.guide/gold/dp-trees?lang=cpp
  • [2] https://tioj.ck.tp.edu.tw/uploads/attachment/11/54/7.pdf
  • [3] https://cses.fi/problemset/task/1130
  • [4] https://threadsiiithyderabad.quora.com/Dynamic-Programming-on-Trees-Tutorial/
  • [5] https://tioj.ck.tp.edu.tw/uploads/attachment/11/42/3.pdf
  • [6] https://mathworld.wolfram.com/GraphCenter.html
  • [7] https://atcoder.jp/contests/dp/tasks/dp_p
  • [8] https://cses.fi/problemset/task/2079
  • [9] https://codeforces.com/problemset/problem/1083/A
  • [10] https://atcoder.jp/contests/arc112/tasks/arc112_c
  • [11] https://codeforces.com/problemset/problem/1693/B
  • [12] https://usaco.guide/gold/all-roots?lang=cpp
  • [13] CLRS Introduction to Algorithms 3/e P. 384
  • [14] https://cses.fi/problemset/task/1133
  • [15] https://atcoder.jp/contests/abc223/tasks/abc223_g
  • [16] https://atcoder.jp/contests/dp/tasks/dp_v
  • [17] https://codeforces.com/problemset/problem/1805/D
  • [18] https://codeforces.com/problemset/problem/1499/F
  • [19] https://codeforces.com/problemset/problem/1748/E

Add AP, Bridge and BCC

AP, Bridge and BCC

• Introduction to connnected component
• Introduction to AP/Bridge
• Tarjan’s Algorithm for AP/Bridge
  • Detail process
  • Time complexity and the correctness
  • Template code
• Using DFS tree to find Bridge
  • Detail process
  • Time complexity and the correctness
  • Template code
• Introduction to BCC
• Tarjan’s Algorithm for BCC
  • Detail process
  • Time complexity and the correctness
  • Template code
• problems
  • https://codeforces.com/gym/102835/problem/I
  • https://codeforces.com/problemset/problem/700/C
  • https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=3549
  • others...

Reference

• https://cp-algorithms.com/graph/search-for-connected-components.html
• https://cp-algorithms.com/graph/bridge-searching.html
• https://cp-algorithms.com/graph/cutpoints.html
• https://oi-wiki.org/graph/cut/
• https://oi-wiki.org/graph/bcc/
• https://web.ntnu.edu.tw/~algo/ConnectedGraph.html#3
• https://web.ntnu.edu.tw/~algo/ConnectedComponent.html
• https://www.hackerearth.com/practice/algorithms/graphs/articulation-points-and-bridges/tutorial/
• https://www.hackerearth.com/practice/algorithms/graphs/biconnected-components/tutorial/
• https://codeforces.com/blog/entry/68138
• https://codeforces.com/blog/entry/71146
• https://www.facebook.com/algo.seacow/posts/pfbid0PMMPJEWmh3XgFtstTh8pptxjnJKK5jwpeVCQWEmfWVyRKT66LqccAv5DiSZ22zDhl

Add chapter C++ programming tips

Based on: https://docs.google.com/presentation/d/1IQgFE6kU_dydGDagsekbH_UP9gLaX9sDsZdsCx51cKg/edit?usp=sharing

Add chapter Basic Number Theory

Binary Exponentiation

• Integer version
• Matrix version
• Implementation
• Examples

Sieve of Eratosthenes

• Finding Prime Numbers
• Implementation
• Examples

Sieve of Euler

• Yet Another Finding Prime Numbers
• Implementation
• Examples

Greatest Common Divisor

• Properties
• Bézout's identity
• Extended Euclidean Algorithm
• Implementation
• Examples (e.g. Solving Linear Diophantine Equation)

Modular Arithmetic

• Modular Inverse
• Fermat's Little Theorem
• Extended Euclidean algorithm
• Finding the Modular Inverse for Array of Numbers Modulo any Positive Integer m
• Implementation
• Examples

Add chapter disjoint set

• Definition of set, disjoint set
• Naive find, union
• Time complexity of naive disjoint set
• Path compression and union by rank
• Optimized time complexity
• Template of disjoint set with explanation
• Problem set

Add Gauss-Jordan elimination

Outline

• introduction
  • solving linear equations
  • Gauss-Jordan elimination
• implementation
  • choosing the pivot
  • degenerate cases
  • acceleration
  • reducing error
• solving modular cases

Problems

https://www.luogu.com.cn/problem/P3389
https://www.luogu.com.cn/problem/P4035
https://www.luogu.com.cn/problem/P2973
https://lightoj.com/problem/graph-coloring
https://www.spoj.com/problems/XMAX/
https://codeforces.com/contest/167/problem/E
https://codeforces.com/problemset/problem/1411/G

Reference

http://e-maxx.ru/algo/linear_systems_gauss
https://cp-algorithms.com/linear_algebra/linear-system-gauss.html
https://oi-wiki.org/math/linear-algebra/gauss/
https://codeforces.com/blog/entry/65787
https://github.com/jaehyunp/stanfordacm/blob/master/code/ReducedRowEchelonForm.cc

Add CDQ and Parallel Binary Search

Outline

• CDQ Divide & Conquer
  • Introduction to partial order
  • N(>=2)-D partial order and examples
  • DP optimization
  • Operation Problems (操作分治)
• Parallel Binary Search
  • Concept
  • DP optimization
  • More examples

Reference

• https://www.cs.princeton.edu/~danqic/papers/divide-and-conquer.pdf
• https://oi-wiki.org/misc/offline/
• https://link.springer.com/chapter/10.1007/978-3-319-72547-5_15 (chap 15.4.2, 15.5.3)
• https://robert1003.github.io/2020/01/31/cdq-divide-and-conquer.html
• https://robert1003.github.io/2020/02/05/parallel-binary-search.html

Add LCA

Outline

• Definition of lowest common ancestor (LCA)
• Common implementations for finding LCA
  • Brute force
  • Binary lifting
  • Reduce to RMQ problem with Euler tour
    • How to reduce to RMQ problem
    • Some useful methods on solving RMQ (mentioned)
    • Farach-Colton and bender algorithm (detailed)
  • Tarjan's offline algorithm
  • Heavy path decomposition
  • Some related problems
    • CSES - Company Queries II
    • SPOJ - Query on a tree II
• Reduction from RMQ problem to LCA problem with Cartesian tree
• Summary

References

• https://web.ntnu.edu.tw/~algo/Tree2.html
• https://oi-wiki.org/graph/lca/
• https://cp-algorithms.com/graph/lca.html
• https://cp-algorithms.com/graph/lca_binary_lifting.html
• https://cp-algorithms.com/graph/lca_farachcoltonbender.html
• https://cp-algorithms.com/graph/lca_tarjan.html
• https://codeforces.com/blog/entry/43917
• https://www.topcoder.com/thrive/articles/Range%20Minimum%20Query%20and%20Lowest%20Common%20Ancestor
• https://oi-wiki.org/topic/rmq/
• https://oi-wiki.org/ds/cartesian-tree/

Add Heavy Light Decomposition

• Introduce to Heavy Light Decomposition

  • Intro
  • Definition of Heavy Node and Light Node

• Properties

  • All nodes belong to a heavy chain
  • Complete Decomposition
  • dfs time stamp is continuous

• Implementation

  • dfs first time to record father, deep, size, heavy node
  • dfs second time to construct heavy chain and light chain
  • Build data structures on each heavy chain
  • Queries
  • Definition of variables and code

• Prove the time complexity

• Problems

• Reference

  • https://oi-wiki.org/graph/hld/
  • https://codeforces.com/blog/entry/81317
  • https://cp-algorithms.com/graph/hld.html

Z algorithm

0. 大綱:
   Z algorithm介紹
   實作程式碼
   Z array性質
   相關題目

Add Trie

Outlines

• Trie basics (insert, delete, find)
• Binary on trie (01trie)
• Persistent trie
• Sample code (basic / binary / persistent)
• Problem set
  • dictionary problem
  • maximum xor sum path on tree
  • maximum xor sub-array
  • given int x and a set S, maximize x ^ y for y in S
  • given int x and a array A, maximize x ^ y for y in A[L: R]

References

• https://oi-wiki.org/string/trie/#%E7%BB%B4%E6%8A%A4%E5%BC%82%E6%88%96%E6%9E%81%E5%80%BC
• https://www.topcoder.com/thrive/articles/Using%20Tries
• https://iq.opengenus.org/persistent-trie/
• https://codeforces.com/blog/entry/93724

Need more explanation in topic Arithmetic Function

Make arithmetic_function.md complete.

Add sitemap

Description

NTHU-CPP 有許多不錯的資訊，但這些文章均未被 google 索引 (可搜尋 site:https://nthu-cp.github.io)。透過生成 sitemap.xml 並提交到 search console 可以讓 google 的機器人更了解網站的架構，增加文章被索引的速度 (可以參考google 的官方說明)。

References

• workflow 產生 sitemap
• 在網站加入 HTML 標記驗證

Add Linck cut tree

Outline

LCT實作

• splay_tree須知
• access
• make_root
• link
• cut

LCT用途

• LCT可以用來解哪些問題
• 時間複雜度分析

例題

• 模板題(Dynamic_Tree_Connectivity)
• DYNALCA - Dynamic LCA
• QTREE6 - Query on a tree VI
• Train Tracks
  除了模板題以外的三題會選兩題做講解

Reference

https://oi-wiki.org/ds/lct/
http://sunmoon-template.blogspot.com/2015/11/link-cut-tree.html
https://codeforces.com/blog/entry/80383
https://github.com/enkerewpo/OI-Public-Library/blob/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%20DATA%20STRUCTURE/Link%20Cut%20Trees.pdf

Add Generating Function

Generating Function

• Introduction to OGF/EGF
• Solving recurrence with GF
• GF with multiple variables
• Common series of OGF/EGF
• Operations on formal power series
• Problems

References

• https://codeforces.com/blog/entry/77468
• https://codeforces.com/blog/entry/77551
• https://codeforces.com/blog/entry/56422
• https://cp-algorithms.com/algebra/polynomial.html
• https://www.luogu.com.cn/blog/MoYuFang/sheng-cheng-han-shuo-di-shuo-xue-ji-chu
• https://www2.math.upenn.edu/~wilf/gfologyLinked2.pdf

Add chapter brute force

• Simple Complete Search
• Complete Search with Recursion
• Advance Technique for Complete Search
• Aesthetics of Brute Force

Add chapter Binary Search

• Basic of Binary Search
• Recursive Binary Search
• Iterative Binary Search
• close/open interval
• Binary Search on Answer
• Problem set