Блог пользователя oml1111

Introducing Algoteka
Автор oml1111, история, 17 месяцев назад, По-английски

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:

Mathematical Algorithms:

Geometric Algorithms:

Graph Algorithms:

Network Flow Algorithms:

String Algorithms:

Algorithms for NP-Hard Problems:

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!

  • Проголосовать: нравится
  • +48
  • Проголосовать: не нравится

»
17 месяцев назад, # |
← Rev. 2   Проголосовать: нравится -10 Проголосовать: не нравится

Nice coding style.

→ Ответить
»
17 месяцев назад, # |
  Проголосовать: нравится +63 Проголосовать: не нравится

I don't dislike the idea of your website. Your implementations are bad though.

Graham Scan Algorithm — float instead of int or double; comparing by atan2 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 of long 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.

→ Ответить
  • »
    »
    17 месяцев назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    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 a std::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, doing node->children[1]->linked_node->value as opposed to value[linked_node[children[node][1]]], and I find it easier to associate new variables with a node that way (just adding the variable to Node structure, rather than adding its std::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!

    → Ответить
»
17 месяцев назад, # |
← Rev. 2   Проголосовать: нравится +15 Проголосовать: не нравится

int get(int pos) { // Returns sum of [0, pos)

FenwickTreeSum f(10);
cout << f.get(10) << endl;

prints 102129 axaxax

→ Ответить
  • »
    »
    17 месяцев назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    Thanks for pointing that out. The constructor of that class was confusing and misleading, and I decided to fix it.

    → Ответить