stjepan's blog

By stjepan, history, 3 years ago, In English,

Link: https://github.com/stjepang/snippets

Many problems require repetitive algorithms like network flows or suffix arrays. Whenever I need such an algorithm, I just copy-paste the same well-tested implementation.

This is my personal collection of algorithms and data structures, which have been in use during the last few years on hundreds of problems and two ACM-ICPC world finals. My favorites are FFT, suffix array, and convex hull.

I hope they will inspire you to write your own library or serve as a learning resource.

Enjoy! Let me know if you have any feedback or questions. :)

 
 
 
 
  • Vote: I like it
  • +356
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Great Job, thanks a lot.

»
3 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Your codes are really smart and well-written. Thanks for sharing! :)

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Just a brief suggestion from my side. It would be nice if you included the complexities of the code/functions. (For example: I had never thought of count primes below N other than sieve. Knowing the complexity of your code may help me in reading further the code to find something new. Since the space complexity was mentioned, I knew that your method was something different, but complexity analysis may help).

Also, what type of indexing is used 0-based/1-based could help us.

BTW, nice short templates. Also, not much headers in terms of for loops and typedef required, which I liked the most.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What exactly does this code do? How do you define the maximum amount of circulation around the graph? I believe that O(VE) would be too good time complexity for so simple code if you could compute mincost maxflow with it. (Though in practice it could be really fast)

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Suppose you have a directed weighted graph. All capacities are 1, while weights are the costs of edges.

    Let's say the maximum number of (edge-wise) disjoint cycles you can mark in the graph is F. That's the circulation flow.

    Now choose a set of F disjoint cycles such that the sum of costs of all their edges is minimum. This minimum cost is what the algorithm computes.

    Yeah, O(VE) is definitely too good :) However, when I'm solving problems and see the runtime of the algorithm, in practice it behaves as roughly O(VE). I'll change the comment to remove this confusion.

    Edit: Hopefully the comment about time complexity is clearer now.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +45 Vote: I do not like it

      Thanks for clarifications

      In programming contests it is good to know the worst case time complexity of an algorithm because the worst case could be included in the tests. Here is a test generator that generates a graph with 51 vertices and 196 edges where your code takes 21 seconds to run. In general it behaves exponentially to the argument of genBadGraph and therefore exponentially to the size of the graph. The test is based on figure 2 in this paper.

      However this test might be kind of irrelevant to programming contests since usually the capacities will be small or the structure of the graph does not allow constructions like this.

      • »
        »
        »
        »
        3 years ago, # ^ |
        Rev. 2   Vote: I like it +15 Vote: I do not like it

        Ah, but this is easy to fix. Instead of always augmenting cycles by one, we can augment by the minimum capacity on the cycle. I pushed a better version to the repo.

        Diff: https://github.com/stjepang/snippets/commit/4dc97bceb57a9edd0c4ebe9cef921e77c1d13ac8

        Now it takes 0.002 seconds on your test :) Also, this implementation holds the 3rd position on this problem: http://www.spoj.com/ranks/PHU09K/

        I apologize for my confusing "rough" complexity estimate. Shouldn't have mentioned O(VE) at all.

        What I wanted to say is: I've successfully solved problems where V <= 1000 and E <= 1000 using this algorithm.

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          Oh, I though that I was clever with that test but it seems that a trivial test would have been sufficient to make your old code TLE :). I tried to modify the test but I could not get it to break your solution. The same test case worked for breaking my cycle cancelling algorithm even though it augmented maximum capacity always, so it seems that you use some useful heuristics.

          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
            Rev. 3   Vote: I like it +10 Vote: I do not like it

            Yeah, on some problems with circulations it's crazy difficult to get AC even if you have a correct algorithm with good time complexity.

            One of past ACM world finals had a problem with circulations. If you want AC, you must put a lot of effort into heuristics/optimizations, otherwise you get TLE. Pretty frustrating. :)

            (My implementation passes on that problem.)

            If you're curious, I'll try to dig that problem from the archives.

            Edit: This is the problem.

»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Please, check the comment for "run" function in mcmf_dijkstra.cpp. Looks like this function returns {total_cost, total_flow} instead of {total_flow, total_cost}