Given a directed graph G that consists of (multiple of) a node connected to a segment of nodes, how would you find its SCC?

But here I propose a very simple algorithm that can solve this problem in the same time complexity ($$$O((M + N) \log N))$$$ (with M being the number of segments and N being the number of nodes).

set<int> _mark;
void dfs(int i)
{
    _mark.erase(i);
    for (auto &[a, b] : adj[i])
    {
        auto x = _mark.lower_bound(a);
        while (x != _mark.end() && *x <= b)
        {
            dfs(*x);
            x = _mark.lower_bound(a);
        }
    }
    tp.push_back(i);
}
void dfs_T(int i, int c)
{
    _mark.erase(i);
    for (auto &[a, b] : adj_[i])
    {
        auto x = _mark.lower_bound(a);
        while (x != _mark.end() && *x <= b)
        {
            dfs_T(*x, c);
            x = _mark.lower_bound(a);
        }
    }
    IDX[i] = c;
}

Why this works: dfs or dfs_T will always call on an existing node, so it'll be called n times. The time complexity is obvious from the set complexity.

Application: https://atcoder.jp/contests/arc069/submissions/78513905.

But what about the graph consisting of segments connected to segments? It probably can be solved in $$$O((M+N)\log^2(N))$$$ with the segment tree method, but doesn't apply here. I guess...

Also the problem above has a trivial transpose ($$$|M^T|=|M|$$$) of the graph. This probably makes it easier...

Given a tree, you're asked to calculate a function $$$f(d)$$$ for $$$1\leq d \lt n$$$. Each node of the tree contains two values: $$$A_i$$$ and $$$W_i$$$. Let $$$f(d)$$$ being the sum of values of paths that have the product of $$$A$$$-values being $$$K\times t^2$$$ (with $$$t$$$ being a positive integer) and distance $$$d$$$. $$$K$$$ is given as a square-free number.

The value of a path is the product of $$$W_i$$$ for every $$$i$$$ in the path.

I've thought of $$$O(n\sqrt{n \log n})$$$, but I don't know how to optimize it more. This is done by bounding the convolution size (for FFT) in centroid decomposition. Is it really that, or is it a better time complexity if done optimally?

https://qoj.ac/contest/2506/problem/14018

I've reformulated this problem to finding the shortest path from $$$0$$$ to other vertices in the graph G that connects from vertex $$$i$$$ to vertex $$$j$$$ with weight $$$a[(j-i+\text{minpos})\text{ mod }n] - a[\text{minpos}].$$$

This is equivalent to substituting $$$minpos$$$ with $$$j-i$$$ (in the list of elements that constructs $$$j$$$). But I don't know where to go from here.

The fastest solution iterates through the distinct edges and for every vertex, it basically jumps repeatedly on that edge until it can't relax more.

Can anyone prove the asymptotic behavior and the correctness of the above algorithm?

This is my hand-unroll of the well known (?) 64-ary tree, or, "bitset" tree used for predecessor problems. I tried to squeeze a pretty rudimentary implementation of 200A - Кино in $$$O(k \sqrt{k} \log_W(n))$$$ using my usual bitset tree template, but it fell pretty short (1.7s). Rewriting made it go down to just 0.6s, which is seen in these two submissions: 376029723, 376055924.

struct PredProblem {
  static constexpr int B = 64;
  uint64_t tree[32];
  int treeID;
  PredProblem() {
    for (auto &i : tree)
      i = -1;
    treeID = -1;
  };
  void erase(const int i) {
    tree[i / B] &= ~(1ULL << (i % B));
    if (!tree[i / B])
      treeID &= ~(1 << (i / B));
  };
  bool get(const int i) { return tree[i / B] & (1ULL << (i % B)); };
  int next(const int i) {
    uint64_t a = tree[i / B] & -(1ULL << (i % B));
    if (!a) {
      int x = treeID & -(1ULL << (i / B + 1));
      if (!x)
        return 2048;
      int nb = __builtin_ctz(x);
      return nb * B + __builtin_ctzll(tree[nb]);
    } else
      return i / B * B + __builtin_ctzll(a);
  };
  int prev(const int i) {
    uint64_t a = tree[i / B] & ((i % B == 63 ? 0 : (1ULL << (i % B + 1))) - 1);
    if (!a) {
      int x = treeID & ((1 << (i / B)) - 1);
      if (!x)
        return -1;
      int nb = __lg(x);
      return nb * B + __lg(tree[nb]);
    } else
      return i / B * B + __lg(a);
  };
};

This can probably beat the DSU implementation suggested (technically not in TC, since they treat $$$O(\alpha(n))$$$ as $$$O(1)$$$). At least it uses much lower memory.

It's that when I looked at this code: https://codeforces.me/contest/2231/submission/375517331.

I tried to maximize the run-time on this code on my PC, but it took at most 800ms, even if I generated very similar tests as test 20 for example. (I'm trying to maximize mp's size, which is over $$$2.3\times 10^6$$$ in my tests, while test 20 is only $$$2.2\times 10^6$$$. I've also considered umap killer tests, and they peaked at about 1.5s on my system.)

This is probably a compiler/OS difference on Codeforces.

I'm using a 3.6 GHz Core i7-10750H (the extra L3 cache doesn't have much effect) and GCC 16.1.1 on Linux... Codeforces is using the same 3.6 GHz Skylake core with less L3 cache. Could anyone reproduce this?

Preparing a lookup table in binary GCD can be somewhat effective if the inputs are small. I've seen a 30% time reduction with a 512x512 table (which consumes almost no memory and time) for inputs less than $$$2\times10^9$$$. It scales quite linearly with the log.

int lut[512][512];
uint32_t faster_binary_gcd(uint32_t u, uint32_t v)
{
    auto zu = std::countr_zero(u);
    auto zv = std::countr_zero(v);
    auto shift = std::min(zu, zv);
    u >>= zu;
    v >>= zv;
    do
    {
        if (u < 512)
            return lut[u][v % u] << shift;
        uint32_t u_minus_v = u - v;
        if (u > v)
        {
            u = v, v = u_minus_v;
        }
        else
        {
            v = v - u;
        }
        v >>= std::countr_zero(u_minus_v);
    } while (v != 0);
    return u << shift;
}

It comes to my mind that while some problems have obviously wrong solutions, they're still accepted in an algorithmic contest. E.g. https://codeforces.me/blog/entry/147991, or (possibly) https://qoj.ac/contest/1901/problem/8614, https://dmoj.ca/problem/coci16c4p4. Would this be regarded as an error, or actually acceptable? (Output only, or partial scoring problems are excluded from this).

A common "excuse" is to generate weak tests to deliberately make the intended etc. solutions pass.

It seemed that this problem got not much more development going to it since its introduction, so my solution is still the fastest after nearly a year: https://judge.yosupo.jp/submission/268155.

There're only two main optimizations: AVX input, and back-substitution using Method of Four Russians (this is how I became the fastest over adamant's lead.)

Would there be a faster solution to this problem?

I've discovered two more GP modes:

https://codeforces.me/contests/2147,2164,2180,2179/gp10/best4/standings?mobile=false

https://codeforces.me/contests/2147,2164,2180,2179/gp30/best4/standings?mobile=false

https://codeforces.me/contests/2147,2164,2180,2179/gp100/best4/standings?mobile=false

Please respect the function $$$dmax(n)$$$ by actually using it, instead of masquerading it for a random function that serves as a very rough approximation. Context: $$$dmax(n)$$$ is $$$max_{1\leq i \leq n}\tau(n)$$$.

Hey MikeMirzayanov, can you fix the mirror website of codeforces, it's useful for many people. Thanks!
UPDATE: mirror codeforces is back!!