/
NOTES.txt
58 lines (42 loc) · 2.5 KB
/
NOTES.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
Most problems can be solved by referencing the Competitive Programmer's Handbook
available at: https://usaco.guide/CPH.pdf
Open questions:
- what is the complexity of concert-tickets-2.cc?
Important problems:
- elevator-rides.cc (bin packing in O(N × 2^N))
Interesting that the problem becomes easier by calculating more information!
- high-scores.cc ("shortest path" with cycle detection, Bellman-Ford)
Shows how to handle cycles correctly (they may exist but not lie on the
path from start to finish).
- cycle-finding.cc (Bellman-Ford)
Shows how to collect cycles in a graph.
Note: this assumes you may start from any vertex in the graph!
TODO:
- cycle-finding.cc: prove that following prev[v] always leads to a negative-weight cycle
- ”Shortest Path Faster Algorithm” (variation of Bellman Ford)
test with cycle-finding.cc?
- implement min-stack / min-queue and add them to code library
https://cp-algorithms.com/data_structures/stack_queue_modification.html
- test with maximum-subarray-sum-II.cc
- Strongly Connected Components should be put in codelib (from flight-roughts-check.cc)
and be changed not to rely on call-stack recursion!
- Add a note about 2SAT (giant-pizza.cc) to codelib2/
- finding-a-centroid.cc: find a nicer way to memoize each edge than with an unordered set?
- in principle the memo needs only N-1 entries instead of 2*(N-1) because
SubtreeSize(v, w) == N - SubtreeSize(w, v)
- we shouldn't need to hash anything because the edge indices can be represented as
integers between 0 and N-1 (exclusive).
- Add a note about Eulerian tours (Hierholzer's algorithm) (mail-delivery.cc, teleporters-path.cc) to codelib2/
- Min Cost Max Flow:
- maybe improve pathfinding using edge list?
- maybe add implementation of Dinic's algorithm? (max flow only!)
https://codeforces.com/blog/entry/104960
https://github.com/kth-competitive-programming/kactl/blob/eee7d5991ad944311f157e106082528be602fe73/content/graph/Dinic.h#L25-L36
https://cp-algorithms.com/graph/dinic.html#implementation
Compare with MPM algorithm?
I want O(V^2 E) performance (but I already have push-relabel for that!)
and the ability to easily extract the flow graph and the edges in a min cut
need a problem to test it on!
- Combine usages of min-cost-max-flow into a single header?
- string-matching.cc: deterministic algorithm? (e.g. KMP-like?)
- finding-borders.cc: deterministic algorithm? (e.g. KMP?)