indy256 / codelibrary Goto Github PK

View Code? Open in Web Editor NEW

1.8K 1.8K 509.0 3.69 MB

:gem:Collection of algorithms and data structures

License: The Unlicense

C++ 29.42% Java 60.28% CMake 0.06% Kotlin 3.14% Python 6.58% Rust 0.52%

algorithm cpp data-structures java kotlin

codelibrary's People

Contributors

Stargazers

Watchers

Forkers

voldermort atychyna w00lf phiiaz ka4tik aichemzee ahtotruu chandershivdasani jainkshitij mhd8980 vizshat satyasumans crazyministr ravi1g enzlaur blue-lan eduardoveduard yubaowu balamurugan-r abhishekjt 764184369 lazy-ninja informationalert raakeshar topcoder-philosopher ankitsrv jgera anmol2307 firatkarakusoglu 0x0all isabek sameralshurafa simonzhangsm sureshmahato ihwanudien tilakchandlo srivassundar vkatharki krishnakalyan3 nphuc nonstopbv manish05 kshanmol jitendratheta bicho-kun cksharma nvthanh1994 zluo jeremyblum igor-bartashevich kpchaitanya flowndays weiru nana1220 k100rav nurseyit200 idispatch thotp-zz deyin sumeetvarma wpande thakkark1313 firedemon1 sagarpatel26 sankark animesh0353 soul-magnet fc2002002002 timofey no-glue alebr qlu11 4mda girish avineshwar akash-vartak robin2234 askmi kvadlamani92 dpzhou liangsheng minsuu mgashraf verstarr sodhanalibrary hcchen zcourts felix-halim igorflyunt zaytsevmm oleksandrlahutin leo777 mayatskiyv jpascale ashirborah denisbazhan sandkierkegaard ooccoob rubonz aleckoryak

codelibrary's Issues

Schreier–Sims algorithm

https://en.wikipedia.org/wiki/Schreier–Sims_algorithm
https://github.com/indy256/olymp-docs/blob/master/notebooks/codebook.pdf

Simplified heavy/light decomposition

https://pastebin.com/vkdiXhYJ
http://codeforces.com/blog/entry/53170

Incremental cycle detection, topological ordering, and strong component maintenance

http://sidsen.azurewebsites.net/papers/dto-journal.pdf

Codes for other languages

@indy256 Can I add codes for other languages that are not mentioned there? Such as C#. Also, can I add more Algos?

AhoCorasick broken

Looks like algorithm broken. For example

ahoCorasick.addString("a");
ahoCorasick.addString("aa");
ahoCorasick.addString("abaaa");
String s = "abaa";

Answer will be [0] - second string got lost.

Where is the code for code-library.herokuapp.com?

I aim to make some PRs to make the search criteria more flexible and possible integration with a description to make it beginner friendly.

Hoping to hear from you soon.

@indy256

Point location in O(log n)

https://cp-algorithms.com/geometry/point-location.html
https://github.com/indy256/codelibrary-sandbox/blob/master/java/src/geometry/PointLocation.java

Polynom class

https://github.com/zimpha/algorithmic-library/blob/master/cpp/mathematics/polynomial.cc

Polynom division, evaluation, square root in O(n*log^2(n))

https://github.com/the-tourist/algo/blob/master/numeric/poly.cpp
http://docplayer.net/25594945-Lecture-4-polynomial-algorithms.html
https://cs.stackexchange.com/questions/60239/multi-point-evaluations-of-a-polynomial-mod-p
https://drive.google.com/file/d/1B9BIfATnI_qL6rYiE5hY9bh20SMVmHZ7/view
https://ideone.com/whaSln

https://codeforces.com/blog/entry/56422
https://codeforces.com/blog/entry/63491
https://discuss.codechef.com/questions/83356/polyeval-editorial

NTT Polynomial Division: https://github.com/indy256/olymp-docs/blob/master/notebooks/teamnote.pdf
https://github.com/indy256/olymp-docs/blob/master/notebooks/kactl.pdf

Maximum weighted matching in general graph

https://arxiv.org/pdf/1611.07541.pdf
https://www.math.uwaterloo.ca/~bico/papers/match_ijoc.pdf

https://github.com/indy256/codelibrary/blob/master/cpp/graphs/matchings/max_general_weighted_matching.cpp

https://github.com/tzupengwang/PECaveros/blob/master/codebook/graph/BorrowedGeneralWeightedMatching.cpp
https://gist.github.com/min-25/aed29a23b004505d2094a5cddaf56ff9
https://gist.github.com/min-25/b984122f97dd7f72500e0bd6e49906ca

https://codeforces.com/blog/entry/63630
http://uoj.ac/problem/81/statistics
http://uoj.ac/submission/282287

Voronoi diagram and Delaunay triangulation

https://cp-algorithms.com/geometry/delaunay.html
https://github.com/dacin21/dacin21_codebook/blob/master/geometry/delaunay_randomized_incremental.cpp
https://github.com/indy256/codelibrary-sandbox/blob/master/java/src/geometry/DelaunayVoronoi.java
https://github.com/indy256/olymp-docs/blob/master/notebooks/codebook.pdf

Chu–Liu/Edmonds' algorithm

https://codeforces.com/blog/entry/20079
https://github.com/kth-competitive-programming/kactl/blob/master/content/graph/DirectedMST.h
https://en.wikipedia.org/wiki/Edmonds%27_algorithm
https://github.com/indy256/olymp-docs/blob/master/notebooks/teamnote.pdf
https://github.com/indy256/olymp-docs/blob/master/notebooks/codebook.pdf
http://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_двух_китайцев

Palindrome tree

https://codeforces.com/blog/entry/13959?locale=en
http://adilet.org/blog/palindromic-tree/
https://arxiv.org/abs/1506.04862
https://github.com/indy256/olymp-docs/blob/master/notebooks/teamnote.pdf
https://github.com/ADJA/algos/blob/master/Strings/PalindromeTree.cpp
https://github.com/zimpha/algorithmic-library/blob/master/StringUtility/eertree.cc
https://www.geeksforgeeks.org/palindromic-tree-introduction-implementation/

Graph planarity testing

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.217.9208&rep=rep1&type=pdf
https://www.emis.de/journals/JGAA/accepted/2004/BoyerMyrvold2004.8.3.pdf
https://people.mpi-inf.mpg.de/~mehlhorn/ftp/ImplementationPlanarity.pdf

I know that it might be a small nuisance, but could you please use a better description in your commits rather than just "update"? Something like "update Sort C++" would suffice to keep up with the library.

Cheers and keep up the great work!

Sqrt tree

https://codeforces.com/blog/entry/57046
https://cp-algorithms.com/data_structures/sqrt-tree.html

Minkowski sum

https://github.com/tzupengwang/PECaveros/blob/master/codebook/geometry/Minkowski_Sum.cpp
https://github.com/mfornet/campamento-colombia-2017/blob/master/geometry/minkowski.cpp
"Computational geometry algorithms and applications" p.295
https://github.com/indy256/olymp-docs/blob/master/notebooks/codebook.pdf

LUP decomposition

https://en.wikipedia.org/wiki/LU_decomposition
https://github.com/dacin21/dacin21_codebook/blob/master/numerical/markov_chain.cpp#L17
https://ru.wikipedia.org/wiki/LUP-разложение

SVD (Singular value decomposition)

https://en.wikipedia.org/wiki/Singular_value_decomposition
http://www.crbond.com/download/misc/svd.c

implementation request: partially persistent red-black tree

I want to emphasize that I am referring to an actual partially persistent tree in which multiple tree mutations may be grouped together into a single version, as opposed to a persistent tree in which each mutation generates a new version. Implementations of the later can easily be found. I have found no implementation of the former.

DFA minimization

https://en.wikipedia.org/wiki/DFA_minimization

Hirschberg's algorithm

https://en.wikipedia.org/wiki/Hirschberg%27s_algorithm
http://acm.math.spbu.ru/~sk1/courses/1718f_au/conspect/conspect.pdf

Kth shortest path

https://en.wikipedia.org/wiki/K_shortest_path_routing
https://en.wikipedia.org/wiki/Yen%27s_algorithm
https://github.com/indy256/olymp-docs/blob/master/burunduk1/lection-2012b.pdf
https://github.com/indy256/olymp-docs/blob/master/burunduk1/conspect-2017-1-2.pdf
https://github.com/indy256/olymp-docs/blob/master/notebooks/teamnote.pdf

Fast calculation of n'th element of linear recurrence

https://github.com/dacin21/dacin21_codebook/blob/master/nt/polynomial_mod.cpp
https://codeforces.com/blog/entry/52158
https://discuss.codechef.com/questions/65993/rng-editorial
https://vk.com/mindbun?z=photo-28114121_456239021%2Falbum-28114121_00%2Frev

Matroid intersection

https://codeforces.com/blog/entry/69287
https://codeforces.com/blog/entry/58135
https://en.wikipedia.org/wiki/Matroid_intersection
https://codeforces.com/blog/entry/43871
https://codeforces.com/blog/entry/14948
https://courses.engr.illinois.edu/cs598csc/sp2010/Lectures/Lecture17.pdf
schrijver p.708

Making requests

If it is appropriate, I'd like to make a request for an implementation. If so, where about would I make the request?

Stoer–Wagner algorithm

https://en.wikipedia.org/wiki/Stoer%E2%80%93Wagner_algorithm

LICENSE?

What is the license on this code? We would like to use your implementation of Tarjan's algorithm in one of our projects, but want to make sure we have the appropriate permission.

The project I'd like to use the code in uses the NCSA open-source license (http://opensource.org/licenses/NCSA) so some sort of BSD or MIT license would be preferable.

Minimum-weight closure

https://en.wikipedia.org/wiki/Closure_problem

Dominator tree

https://codeforces.com/blog/entry/22811
https://tanujkhattar.wordpress.com/2016/01/11/dominator-tree-of-a-directed-graph/
https://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/a%20fast%20algorithm%20for%20finding.pdf
https://github.com/indy256/olymp-docs/blob/master/notebooks/teamnote.pdf
https://github.com/indy256/olymp-docs/blob/master/notebooks/codebook.pdf
https://github.com/the-tourist/algo/blob/master/graph/dominators.cpp

Levenstein automata

http://blog.notdot.net/2010/07/Damn-Cool-Algorithms-Levenshtein-Automata
https://gist.github.com/Arachnid/491973
http://blog.mikemccandless.com/2011/03/lucenes-fuzzyquery-is-100-times-faster.html
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.16.652&rep=rep1&type=pdf
https://github.com/klawson88/LevenshteinAutomaton
https://en.wikipedia.org/wiki/Levenshtein_automaton
https://store.fmi.uni-sofia.bg/fmi/logic/theses/mitankin-en.pdf
http://www.aclweb.org/anthology/I08-2131
http://lml.bas.bg/~stoyan/J04-4003.pdf
http://julesjacobs.github.io/2015/06/17/disqus-levenshtein-simple-and-fast.html
http://norvig.com/spell-correct.html
https://habrahabr.ru/post/275937/
https://habrahabr.ru/post/276019/
http://habrahabr.ru/post/123320/
http://habrahabr.ru/post/114997/
https://fulmicoton.com/posts/levenshtein/
https://codeforces.com/blog/entry/20688

Minimum augmentation to strong connectivity

https://github.com/indy256/codelibrary/blob/master/java/graphs/dfs/StronglyConnectedComponents.java
https://codeforces.com/blog/entry/15102?locale=en
http://www.springer.com/cda/content/document/cda_downloaddocument/9780387235288-c2.pdf

Dynamic convex hull

https://codeforces.com/blog/entry/63823
https://github.com/kth-competitive-programming/kactl/blob/master/content/data-structures/LineContainer.h
https://cp-algorithms.com/geometry/convex_hull_trick.html
https://github.com/zimpha/algorithmic-library/blob/master/data-structure/DynamicConvexHull.cc
https://github.com/jakobkogler/Algorithm-DataStructures/blob/master/DP/LiChaoTreeDynamic.h
https://github.com/tzupengwang/PECaveros/blob/master/codebook/dataStructure/LiChaoST.cpp
https://github.com/indy256/olymp-docs/blob/master/notebooks/teamnote.pdf
https://github.com/indy256/olymp-docs/blob/master/notebooks/kactl.pdf
https://www.codechef.com/viewsolution/19207670
https://github.com/niklasb/contest-algos/blob/master/convex_hull/dynamic.cpp
https://codeforces.com/blog/entry/11155?#comment-162462

Problem for studying persistent tree

Thank you for your sharing the code. I'am a fresh man in acm and using Java to code. I like your writing sytle of the persistent tree, using linked list looks so good.
And I spent a whole night trying to rewrite it into a interval modification version, but I fail......
Can you give me some tips about it? The algorithms implement in Java is really hard to find......‎
Thanks a lot!

Minimum augmentation to biconnectivity

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.54.9579&rep=rep1&type=pdf

From static set to expandable via O(log(n))

https://codeforces.com/blog/entry/48417
http://acm.math.spbu.ru/~sk1/courses/1718f_au/conspect/conspect.pdf

Sorting strings in linear time

MaxFlowDinic does not find blocking flows

https://github.com/indy256/codelibrary/blob/master/java/src/MaxFlowDinic.java

In your implementation of Dinic's algorithm, you visit every edge only once in the DFS portion. This is wrong, in my opinion, as it does not guarantee that you create a blocking flow. Specifically, you may have to traverse edges more than once if you didn't saturate the path to the sink the first time.

https://github.com/aquaskyline/SOAP3-dp/blob/master/ssse3_popcount.cpp
https://codeforces.com/contest/472/submission/8014415
https://codeforces.com/contest/1097/submission/47943459
https://sites.google.com/site/indy256/algo_cpp/sse
FFT: https://github.com/indy256/olymp-docs/blob/master/notebooks/teamnote.pdf
https://codeforces.com/contest/573/submission/12760770
https://codeforces.com/blog/entry/48795
https://software.intel.com/sites/landingpage/IntrinsicsGuide/#
gauss, bitset, fft, matrix, hamming distance, n^2 dynamic programming
https://gist.github.com/sslotin/de9027f18f8794e95261a2586ab9ad2d
https://codeforces.com/blog/entry/68568
https://algorithmica.org/ru/sse
https://github.com/Michael-Tieying-Zhang/SIMD-Bitset
https://unix4lyfe.org/autovec/
https://habr.com/ru/post/685228
https://habr.com/ru/articles/785938/
https://github.com/ov3rdr1v337/sse_sort/blob/main/fixed_sort.h

Big Integer Template problems

https://github.com/indy256/codelibrary/blob/master/cpp/bigint.cpp

As far as I known, this code has 2 problems:

can't process long long integer as int. (It will not cause a compilation error, it will convert long long into int first, then process it as int)
divide by large negative integer will get wrong answer, for example 5 / -2 will return -2, expected result is -3 (at least python will give out answer -3).

I will try to fix it when I have time and file a pull request. Hope you guys noticed.

Subset convolution, Walsh–Hadamard transform

https://csacademy.com/blog/fast-fourier-transform-and-variations-of-it
http://codeforces.com/blog/entry/48232
http://codeforces.com/blog/entry/48417
http://codeforces.com/blog/entry/57250#comment-409514
http://codeforces.com/blog/entry/57250#comment-409117
https://drive.google.com/file/d/1B9BIfATnI_qL6rYiE5hY9bh20SMVmHZ7/view
https://codeforces.com/contest/914/submission/34394196
https://github.com/indy256/olymp-docs/blob/master/notebooks/kactl.pdf
https://people.csail.mit.edu/rrw/presentations/subset-conv.pdf
http://serbanology.com/show_article.php?art=A%20Bitwise%20Convolution%20Tutorial

Maximum density subgraph

https://www2.eecs.berkeley.edu/Pubs/TechRpts/1984/CSD-84-171.pdf
https://en.wikipedia.org/wiki/Dense_subgraph
jgrapht/jgrapht#712

Maximum density subgraph ( \sum W_e + \sum W_v ) / |V|
Binary search on answer:
For a fixed D, construct a Max flow model as follow:
Let S be Sum of all weight( or inf)
1. from source to each node with cap = S
2. For each (u,v,w) in E, (u->v,cap=w), (v->u,cap=w)
3. For each node v, from v to sink with cap = S + 2 * D
- deg[v] - 2 * (W of v)
where deg[v] = \sum weight of edge associated with v
If maxflow < S * |V|, D is an answer.
Requiring subgraph: all vertex can be reached from
source with
edge whose cap > 0.