ncduy0303's blog

My personal Competitive Programming templates in C++
By ncduy0303, history, 5 years ago, In English

I created my own repository for CP purposes. I have tried to include as many commonly used algorithms and data structures as possible (some are taken from different sources).

Link: https://ncduy0303.github.io/Competitive-Programming/

Hope that somebody will find it useful and feel free to report any bugs :)

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

Comments Comments (7)
| Write comment?
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Seems like quite a good starting point! Here are few suggestions. I won't write down what to add, because there are so many things to write in template and I don't know what you've intended to cover in your template. Hence these are only improvement suggestions. i.e, faster algorithm for a problem currently covered which are valid topics in CP, as far as I know.

  1. Maximum flow can be solved faster in Dinic's algorithm. I remember as $$$O(V^2 E)$$$ which is faster than Edmond-Karp. Unfortunately I do not recall a particular problem which is solvable by Dinic and not by E-K, but I am almost certain there are, since Dinic is actually faster than it looks in practice.

  2. I recommend studying $$$O(n^2 \log n)$$$ algorithm for 2D maximum sum subarray problem. I saw it twice, from ICPC Seoul Regional 2019 (I can't find this on CF Gym...) and Korean Olympiad. Here is a link to ICPC one, in Korean Online Judge. This can be done by segment tree + line sweeping technique.

  3. (I think you might know this) Precomputing factorials and using modulo inverse is usually cheaper for computing binomial coefficients

BTW, your codes look so much better than mine. Thanks for sharing :)

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    About a problem that can be solved by dinic but not E-K, just try any bipartite matching problem with around 1e5 vertices for example this.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks! However I don't still get it in my mind...
      If I remember correctly, I've learned that (as I wrote) Dinic is $$$O(V^2E)$$$ but faster in practice. Your link seems to have V, E both about 1e5, which I wonder why it is solvable with Dinic. It should be way too big V E even with dinic... Is there something I'm missing??

      Thanks in advance.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        On unit network Dinic works in $$$O(E * sqrt(V))$$$: https://cp-algorithms.com/graph/dinic.html

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
          ← Rev. 2   Vote: I like it +45 Vote: I do not like it

          The CP-algorithms analysis isn't correct for unit graphs.

          In their proof, they say that "As the network is unit, [the augmenting paths] can't have common vertices" which is clearly wrong. They can't have common edges.

          The proper analysis gives $$$O(E \min(V^{2/3}, E^{1/2}))$$$. See Wikipedia or these lecture notes.

          It is true that Dinic works in bipartite matching in $$$O(E*\sqrt{V})$$$, but not for unit graphs in general.

          → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I don't know if there exists any algorithm better than O(n³) for a general maximum sum submatrix problem. The problem you linked has only O(n) non zero entries in the matrix, so its solvable with a better complexity.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ah. My mistake.. I read the wrong thing on his original code. Sorry for misinformation...:(

      → Reply