I want to append const to several method declarations in atcoder::segtree.

Some complicated DP problems require to maintain two segtrees to improve time complexity. In such situations, coders always have to pay attention to them. If one of them is not modifed at all (used like (disjoint) sparse tables), I want to declare it as const to reduce the risk of updating the wrong segtree.

In current ACL, all atcoder::segtree methods are not declared as const, so we cannot declare the instances as const when there is no update query. On the other hand, it seems that the methods get(), prod(), all_prod(), max_right() and min_left() do not affect any member variables. I suggest that these methods have const like this to enable such usage of atcoder::segtree.

What do you think of this modification?

I think this should be:

x*u0*g % (u1*g) = (r1-r0) % (u1*g) (u0*g = m0, u1*g = m1)

For example, when (r0, r1) = (4, 0) and (m0, m1) = (5, 3), we have (x, g, u0, u1) = (-2, 1, 5, 3). So x*u0*g % (u1*g) is -1 (or 2 if we consider non-negative mod), but (r1-r0) is -4.

Anyway, the code itself seems correct.

The documentation currently have instructions for Visual Studio on Windows (see path in the doc with C drive, I don't know where the include folder is in macOS case). I guess most of the programmers use Windows and hence the lack of documentation on MacOS. I had tried to set it up a few weeks back and had a great trouble in getting it compiled in Visual studio. (Command line compile is fine but visual studio doesn't see the library).

It will be helpful for macOS users.

The document at GitHub Pages of this repository is tracking production branch. Is this intended?
I recommend to use master for GitHub Pages, or make clear what branches are used (e.g. use https://atcoder.github.io/ac-library/production/document_en/ as the URL).

For example, the fix for #2 is merged into master but not merged into production yet, and the document at GitHub Pages is still wrong.

The following code works because we don't add explicit for the constructor.

segtree<...> seg = 10;

Should we add explicit for some constructors for more intuitive behaviors?

Reporter: NRK7 (https://codeforces.com/blog/entry/82400?#comment-693895)

The format of flow_limiw is broken

    <link rel="stylesheet" href="https://judge.yosupo.jp/public/css/uikit.min.css" />
    <script src="https://judge.yosupo.jp/public/js/uikit.min.js"></script>
    <script src="https://judge.yosupo.jp/public/js/uikit-icons.min.js"></script>

I just copy-pasted those lines and forgot to fix...

By definition in the document appendix.html, it should return 0 I believe.

g(v, f) = Sum{...} - Sum{...}

This implies the sum of g(v, f) over all vertices is zero.

g(v, f) = g(v, f') holds for all vertices v other than s and t.

Since s = t, this also implies g(t, f) = g(t, f'). (∵ everywhere except t is fixed, and the sum is fixed)

g(t,f′)−g(t,f) is maximized under these conditions. It returns this g(t,f′)−g(t,f)

Since g(t, f) = g(t, f'), the returned value should be 0.
Though, the actual implementation returns inf or the third argument (limit),

The current return value also makes sense if you view the problem as an instance of MaxFlow formulated as LP. You'll most likely get a primal unbounded, dual infeasible instance, depending on the choose of formulation.

Since there are multiple return values that makes some sense, both fix (fix documentation / fix implementation) would still leave confusion. So it might be better to assert(s != t) and document it.

https://github.com/rust-lang-ja/ac-library-rs/pull/24/files#r485363476

Mathのcrtにある説明から常人が「**の剰余定理」という名称（あるいはCRTが何の略か）に辿り着くには（コンテストの成績を左右するには十分に長い）時間が掛かるのではないかと思います。

crt

pair<ll, ll> crt(vector<ll> r, vector<ll> m)

同じ長さの配列 $r, m$ を渡します。この配列の長さを $n$ とした時、

$$x \equiv r[i] \pmod{m[i]}, \forall i \in \lbrace 0,1,\cdots, n - 1 \rbrace$$

を解きます。答えは(存在するならば) $y, z (0 \leq y < z = \mathrm{lcm}(m[i]))$ を用いて $x \equiv y \pmod z$ の形で書けることが知られており、この $(y, z)$ をpairとして返します。答えがない場合は $(0, 0)$ を返します。$n=0$ の時は $(0, 1)$ を返します。

Should this be if (m_ <= v) v -= m_; instead of +=? Or is there some other trickery happening?

All #include <atcoder/...> links in the index.md lead to something.html, while it should be something.md I guess.

This line doesn't seem to be correct me. Instead, we should update this variable by d.
Also, it would be better to name it cost_per_flow or something like that to avoid confusion.

A test case would be

TEST(MincostflowTest, SameCostPaths) {
    mcf_graph<int, int> g(3);
    ASSERT_EQ(0, g.add_edge(0, 1, 1, 1));
    ASSERT_EQ(1, g.add_edge(1, 2, 1, 0));
    ASSERT_EQ(2, g.add_edge(0, 2, 2, 1));
    auto expected = std::vector<std::pair<int, int>>{{0, 0}, {3, 3}};
    ASSERT_EQ(expected, g.slope(0, 2));
}

Reporter: maspy(Japanese tweet: https://twitter.com/maspy_stars/status/1303540527984328704)

The constraints of floor_sum may be too tight. Should we improve this? (e.g. negative input, return value with mod 2^64 and allow overflow, return value with arbitrary mod ...)

Reporter: NRK7

https://codeforces.com/blog/entry/82400?#comment-694155

Can we use the documents under document_ja/ and document_en/ library in ports to other languages? If possible, under which license shall we use?

In now, we can compile the following code, but it is confusing.

using mint = modint998244353;

mint x = 2.0; // static_modint(bool) is called
assert(x == mint(1)); // because bool(2.0) -> true -> 1

We wrote the time complexity of mincostflow as O(F(n+m)log n), but it should be O(F(n+m)log m)

Could you please add input streams for Modint so we can cin>> a modint directly

May I use/modify the expander.py for my personal competitive programming library? If so, under which license shall I use it?

Please consider adding a BigInt library containing basic arithmetic operations to work with BigInts.

Its implementation is already present in many other languages like Python and Java. So I believe, C++ users also deserve easy access to BigInts.

The document says O(log(m+a)), but now (by #92) m+a may be negative or zero. I suggest O(log(a mod m)).

By the way, maybe, its complexity could be bounded by O(log(min(n, a mod m))). It might be wrong because I guessed just intuitively (and empirically). So I'm glad if anyone can analyze this.

Hello.

Is there any place I can learn about the minimum cost flow algorithm which is in the library?

Edit: Actually, it seems to be the same algorithm in this topcoder tutorial. However, they claim the complexity is O(nmFlogn) instead of O(F(n+m)logn). Which one should I trust? xD

Reporter: NRK7(https://codeforces.com/blog/entry/82400?#comment-693874)

Minor mistake in maxflow.html of document_en: function prototype of change_edge should be

void graph.change_edge(int i, Cap new_cap, Cap new_flow);
instead of

void graph.change_cap(int i, Cap new_cap, Cap new_flow);

We investigated reactions for this library.

It is appeared that includuding header files and running expander.py needs the knowledge about PC.

We should provide the everything combined header file so that we can use AC Library by just copy-paste it to the top of main.cpp.

Input the following numbers into Problem J
1 1
4
3 1 3

The output should be 2 because there is no number of Aj that less than 3. But the output is 1.

#include <atcoder/all>
#include <iostream>

using namespace std;
using namespace atcoder;

const int BIG = 9'000'000; // Constraints 0 <= n <= 10^8

int main() {
    scc_graph g(BIG);
    for (int i = 0; i < BIG - 1; i++)
    {
        g.add_edge(i, i + 1);
    }
    auto scc = g.scc();
    cout << scc.size() << endl;

    return 0;
}

English:
When Run the code on Custom Test, it exit with exit code 139, which probably a segmentation fault due to stack overflow.

日本語:
コードテストで上記のコードを実行すると終了コード139(おそらくスタックオーバーフローによるセグメンテーション違反)で終了します。

vector<modint998244353> a(0), b(1_000_000);

atcoder::convolution(a, b); // it consumes long time!

We shouldn't run copy-constructor when convolution(empty, long_array) is called

Can we use the test cases in the test/ folder as the tests of foreign-language port of this library? If possible, under what license shall we use?

I completely forgot to add assert for mcf_graph.add_edge.

Reporter: tomarint (Japanese tweet: https://twitter.com/tomarint/status/1303348359046987776 )

We don't write usng namespace atcoder into first sample of modint.html. So this sample cannot compile

Expander.py cannot handle CPLUS_INCLUDE_PATH with colons

By #107 , we add const to some methods of lazysegtree.

But it seems that const method should be thread safe.

• https://stackoverflow.com/questions/14127379/does-const-mean-thread-safe-in-c11

Reporter: keymoon(Japanese tweet: https://twitter.com/kymn_/status/1303092030445297665)

We wrote the constraint of SA as 0 <= n < 1e8. We should fix this to 0 <= n <= 1e8 though this isn't the important constraint.

in AtCoder, precomputed binomial coefficients are frequently used.

e.g.
https://atcoder.jp/contests/arc116/tasks/arc116_c
https://atcoder.jp/contests/arc116/tasks/arc116_d

How about adding precomputed binomial coefficients to ACL?

If this comment is about the range of m0, I think this would be suitable:

|m0 - (m1 * u)| <= |m0| + |m1 * u|
<= |m0|*t +|m1|*s  (since t >= 1)
<= b

Otherwise, I might not have understood the comment correctly, sorry.

I couldn't find which version of ACL is currently installed on my computer. It would be more convenient if the document contains the version information.

Reporter: Mi_Sawa (Japanese tweet: https://twitter.com/Mi_Sawa/status/1303170874938331137)

max_flow / min_cost_flow cannot handle self-loops "correctly".

This is the code of max_flow.add_edge(). We can notice that we cannot handle an id of reverse edge correctly.
In now, in spite of this code wrong, everything goes well. However, cleary we should fix this.

    int add_edge(int from, int to, Cap cap) {
        assert(0 <= from && from < _n);
        assert(0 <= to && to < _n);
        assert(0 <= cap);
        int m = int(pos.size());
        pos.push_back({from, int(g[from].size())});
        g[from].push_back(_edge{to, int(g[to].size()), cap});
        g[to].push_back(_edge{from, int(g[from].size()) - 1, 0});
        return m;
    }

https://github.com/atcoder/ac-library/blame/master/document_en/segtree.md#L155
https://github.com/atcoder/ac-library/blame/master/document_ja/segtree.md#L159
https://github.com/atcoder/ac-library/blame/master/document_en/lazysegtree.md#L165
https://github.com/atcoder/ac-library/blame/master/document_ja/lazysegtree.md#L166

English:
I guess g(op(a[l - 1], a[l + 1], ..., a[r - 1])) = false should be g(op(a[l - 1], a[l], ..., a[r - 1])) = false.

Japanese:
g(op(a[l - 1], a[l + 1], ..., a[r - 1])) = falseはg(op(a[l - 1], a[l], ..., a[r - 1])) = falseの誤りではないでしょうか。

Reporter: kimiyuki_u (Japanese tweet: https://twitter.com/kimiyuki_u/status/1303172022214615045 )

In appendix.html, we show CPLUS_INCLUDE_PATH="/path/to/ac-library/atcoder" as the example of CPLUS_INCLUDE_PATH. This is wrong, we should set CPLUS_INCLUDE_PATH="/path/to/ac-library/"

The description of the function get_edge of mf_graph in ac-library/document_en/maxflow.md seems to lack the constraint of 0 <= i < m.

Visual Studio causes an error '_umul128': 識別子が見つかりませんでした when using #include<atcoder/math>.
The following three lines may be needed in internal_math.hpp.

#ifdef _MSC_VER
#include <intrin.h>
#endif

Instead of having #ifndef to guard against the multiple includes, #pragma once can be used. Looks a bit cleaner that way.

I had cloned the ACL repository and I tried to convert all the markdown files into HTML files using the generate_document.py script which is given in the /tools directory when I ran into this error:

❯ ./generate_document.py
12:45:37 [INFO] start converting, lang=en
12:45:37 [INFO] convert ../document_en/twosat.md
Traceback (most recent call last):
File "/home/tusky/Tushar/ac-library/tools/./generate_document.py", line 89, in
statement = convert(open(md_file).read(), base_dir, opts.tag)
File "/home/tusky/Tushar/ac-library/tools/./generate_document.py", line 50, in convert
if tag == 'production' or re.match(r'v[0-9].[0-9]', tag):
File "/usr/lib/python3.9/re.py", line 191, in match
return _compile(pattern, flags).match(string)
TypeError: expected string or bytes-like object

After a little bit of googling, I was brought to an answer on Stack Overflow which urged me to wrap the variable tag with the str function which seemed to do the trick.

Thus changing line 50 of generate_document.py to

if tag == 'production' or re.match(r'v[0-9]\.[0-9]', str(tag)):

seems to do the trick and I can now see the desired output:

❯ ./generate_document.py
12:50:49 [INFO] start converting, lang=en
12:50:49 [INFO] convert ../document_en/twosat.md
12:50:49 [INFO] read example: twosat_practice
12:50:49 [INFO] convert ../document_en/dsu.md
12:50:49 [INFO] read example: dsu_practice
12:50:49 [INFO] convert ../document_en/maxflow.md
12:50:49 [INFO] read example: maxflow_practice
12:50:49 [INFO] convert ../document_en/appendix.md
12:50:49 [INFO] convert ../document_en/scc.md
12:50:49 [INFO] read example: scc_practice
12:50:49 [INFO] convert ../document_en/index.md
12:50:49 [INFO] convert ../document_en/convolution.md
12:50:49 [INFO] read example: convolution_int_practice
12:50:49 [INFO] read example: convolution_practice
12:50:49 [INFO] convert ../document_en/lazysegtree.md
12:50:49 [INFO] read example: lazyseg_practice1
12:50:49 [INFO] read example: lazyseg_practice2
12:50:49 [INFO] convert ../document_en/modint.md
12:50:49 [INFO] read example: modint_usage
12:50:49 [INFO] convert ../document_en/fenwicktree.md
12:50:49 [INFO] read example: fenwick_practice
12:50:49 [INFO] convert ../document_en/string.md
12:50:49 [INFO] read example: sa_usage
12:50:49 [INFO] read example: sa_practice
12:50:49 [INFO] convert ../document_en/segtree.md
12:50:49 [INFO] read example: segtree_practice
12:50:49 [INFO] convert ../document_en/mincostflow.md
12:50:49 [INFO] read example: mincostflow_practice
12:50:49 [INFO] convert ../document_en/math.md
12:50:49 [INFO] read example: floor_sum_practice
12:50:49 [INFO] start converting, lang=ja
12:50:49 [INFO] convert ../document_ja/twosat.md
12:50:49 [INFO] read example: twosat_practice
12:50:49 [INFO] convert ../document_ja/dsu.md
12:50:49 [INFO] read example: dsu_practice
12:50:49 [INFO] convert ../document_ja/maxflow.md
12:50:49 [INFO] read example: maxflow_practice
12:50:49 [INFO] convert ../document_ja/appendix.md
12:50:49 [INFO] convert ../document_ja/scc.md
12:50:49 [INFO] read example: scc_practice
12:50:49 [INFO] convert ../document_ja/index.md
12:50:49 [INFO] convert ../document_ja/convolution.md
12:50:49 [INFO] read example: convolution_int_practice
12:50:49 [INFO] read example: convolution_practice
12:50:49 [INFO] convert ../document_ja/lazysegtree.md
12:50:49 [INFO] read example: lazyseg_practice1
12:50:49 [INFO] read example: lazyseg_practice2
12:50:49 [INFO] convert ../document_ja/modint.md
12:50:49 [INFO] read example: modint_usage
12:50:49 [INFO] convert ../document_ja/fenwicktree.md
12:50:49 [INFO] read example: fenwick_practice
12:50:49 [INFO] convert ../document_ja/string.md
12:50:49 [INFO] read example: sa_usage
12:50:49 [INFO] read example: sa_practice
12:50:49 [INFO] convert ../document_ja/segtree.md
12:50:49 [INFO] read example: segtree_practice
12:50:49 [INFO] convert ../document_ja/mincostflow.md
12:50:49 [INFO] read example: mincostflow_practice
12:50:49 [INFO] convert ../document_ja/math.md
12:50:49 [INFO] read example: floor_sum_practice

We should rewrite this line

m=641 ( =2^7*5+1, prime ) and |A| = |B| =61 ( 2^6<|A|+|B|-1=121<2^7 ), convolution returns wrong result.
I think this for-loop's condition should be i <= cnt2 - 2.

Reporter: TumoiYorozu (Japanese tweet: https://twitter.com/TumoiYorozu/status/1303198406513291264 )

It seems that some Visual Studio failed to compile internal_math. We need to take a look into.

As a temporary solution, replacing

    for (long long a : {2, 7, 61}) {

into

    int v[] = { 2, 7, 61 };
    for (long long a : v) {

works, but we have to find the reason.

To include headers from other headers in the same library, we should use #include "...". This is a common manner (examples: 1, 2, 3).

However, the current AtCoder Library uses #include <...> (e.g. https://github.com/atcoder/ac-library/blob/114e690ade7fe839db3ea0e5f169207672ef0886/atcoder/all).
#include <...> is for headers in the standard system directories (see https://gcc.gnu.org/onlinedocs/cpp/Search-Path.html), but AtCoder Library is not system's one.

IIUC, if you use #include <...>, a problem will happen when multiple versions of the this library are installed.
For example, let say we have /usr/include/atcoder/segtree.hpp, /home/user/kimiyuki/GitHub/ac-library/atcoder/segtree.hpp, and /home/user/kimiyuki/GitHub/ac-library/atcoder/all. Under such situation, even when you include /home/user/kimiyuki/GitHub/ac-library/atcoder/all with #include "atcoder/all", this atcoder/all ignores /home/user/kimiyuki/GitHub/ac-library/atcoder/segtree.hpp and includes /usr/include/atcoder/segtree.hpp. This will cause mysterious bugs.

Why do you need the "iter" variable in maxflow.hpp? It seems it is only initialized to 0 and never changed.

https://codeforces.com/blog/entry/82400?#comment-694160