Hello people of Codeforces!
I'd like to introduce a website I've been working on and that I'm hoping to grow into something bigger: algoteka.com
In essence, it's a site for submitting code samples that solve various problems and for finding code snippets in the language and technology stack you want for your problem (and possibly compare different approaches). We are planning to grow and monetize this site, and to compensate our content submitters appropriately for the value they bring.
To start out, I decided to populate it with a lot of the algorithms I've used myself in competitive programming, for instance:
Data structures:
- Heap (and the STL implementation)
- Fenwick Tree
- Segment Tree
- Lazy Propagation Segment Tree
- Persistent Segment Tree
Mathematical Algorithms:
- Extended Euclidean Algorithm
- Sieve of Eratosthenes
- Miller-Rabin Primality Test
- Fast Fourier Transform algorithm (and its use for fast fast polynomial multiplication)
Geometric Algorithms:
Graph Algorithms:
- Depth-First Search
- Breadth-First Search
- Dijkstra's Shortest Path Algorithm
- Eulerian Cycle Alrogithm
- Bridge-Finding Algorithm
Network Flow Algorithms:
- Ford-Fulkerson Algorithm
- Dinic's Algorithm
- Cycle Canceling Min-Cost Flow Algorithm
- Successive Shortest Path Min-Cost Max-Flow Algorithm
- Primal-Dual Min-Cost Max-Flow Algorithm
String Algorithms:
Algorithms for NP-Hard Problems:
- Dynamic Programming Solution for the Knapsack Problem
- Meet-in-the-middle Solution for the Knapsack Problem
- Dynamic Programming Solution for the Travelling Salesman Problem
I hope you find my code snippets useful, and you are very welcome to join the site and start submitting your own code snippets for these problems (potentially in different languages or approaches), or even create new problems to submit samples for (we plan to cover more than just the topics of competitive programming). You are also welcome to use the forum features of the site to discuss samples or problems there, or any related topics.
Any thoughts, ideas and feedback are welcome!
Nice coding style.
I don't dislike the idea of your website. Your implementations are bad though.
Graham Scan Algorithm —
float
instead ofint
ordouble
; comparing byatan2
instead of cross product.All graph algorithms — an inconvenient way of storing nodes (just use indices); push backing nodes instead of resizing vector to N; using slow
deque
.DP knapsack — quadratic memory (which is usually fine but you can do make it linear for copy-pastable code).
MITM knapsack — using
int
instead oflong long
for the sum of values.TSP — using
int
type instead of template, which would work e.g. for non-integer distances.I didn't read more.
Thanks for the feedback!
I did decide to change the aspect you pointed out in the Graham Scan Algorithm, the previous approach was closer to the theory I suppose, so I just left it in as a comment.
Regarding graphs, the
std::deque
structure is usually not the bottleneck anyways, when I changed to astd::vector
with initial size, then for BFS I got an improvement of 202ms to 171ms and for Dijkstra I got an improvement of 343ms to 327ms, which is a fairly small difference. I personally like the pointer based approach as it can make graph traversal more intuitive IMO. For instance, doingnode->children[1]->linked_node->value
as opposed tovalue[linked_node[children[node][1]]]
, and I find it easier to associate new variables with a node that way (just adding the variable toNode
structure, rather than adding itsstd::vector
to the container class and then adding it to the constructor). Resizability of the graph can also be beneficial if the final size is not initially obvious.Not saying that approach is superior to an index-based fixed-size approach, but I personally like it for those qualities.
For the DP Knapsack problem, yes it can be done with less memory using a 1D array (and I mentioned it in specification), but it can be less intuitive (due to diverging from theory) and it's harder to compute the actual optimal set of items that way. In any case, it wouldn't be bad to have an additional sample that solves it with 1D array.
Though I'll mention that Algoteka is also intended to be a site where different samples with different approaches can be submitted to the problems and compared, so it's perfectly fine to have one sample that's a readability oriented direct implementation of theory (if inefficient), another sample that's heavily optimized, and other samples that are specialized for specific scenarios, striving for different characteristics (though at some point it might be better to create a separate 'Problem').
In any case, if you have code samples that are better in some (or perhaps all) characteristics for these problems, then you are actually very welcome to submit them!
int get(int pos) { // Returns sum of [0, pos)
prints 102129 axaxax
Thanks for pointing that out. The constructor of that class was confusing and misleading, and I decided to fix it.