Oh, hi there, ICPC superstars!

Today we got the news that ICPC Challenge will be based on LLMs.

Are you ready??? (I can't hear)

Danya says good night.

I was forced to make a post with the #ICPCAstana hashtag, but I don't have any other pubic social media, so here we go.

TL;DR; You might want to go to ACL repo and get the latest version if you haven't done that in a while, same goes for any other algorithm library I guess.

Today I was solving a min cost flow problem and I decided to use atcoder library. It is very easy to use, you just add an include and run a script to expand it if you're submitting to sites that aren't atcoder. I got a WA.

After some debugging I concluded that it's a bug in atcoder library... Which they fixed 3 years ago! I downloaded my ACL on Sept. 20 of 2020 and never updated it.

I don't know if there's already a blog about this, I couldn't find one. But I even if there is I think another one won't hurt. Updating software is useless, who cares about security? But updating algorithm library is essential, because everybody cares about fake internet points.

Hello Codeforces! I got some interesting tricks to share with you.

1. a_i := (a_i + x)%mod Range Updates, Max Range Queries

Apply usual range addition, but after each update run the following code:

void normalize(int l, int r) {
    while(getmax(l, r).max >= mod) {
        set(getmax(l, r).pos, getmax(l, r).max%mod);
    }
}

What is the complexity of this code? We all know that each time we %%=mod$ number which is $$$\geqslant mod$$$ it halves, that means each number will be updated $$$O(log)$$$ times, we will perform $$$O(n\cdot\log{n}\cdot\log{a})$$$ operations in total. So each update will be $$$O(\log{n}\cdot\log{a})$$$ amortized!

2. $$$O(\log^2{\log{n}})$$$ Segment Tree

Segment tree queries are queries on path. Instead of doing them in the usual brute force-ish way we can use HLD! Since maximum path length is $$$2\cdot\log{n}$$$, thus operations are now operations are $$$O(\log^2{\log{n}})$$$, which is better than $$$O(\log{n})$$$.

3. Faster Dinic's

We know that after $$$i$$$ operations Dinic's algo finds flow which is at least $$$\frac{i}{i+1}\cdot{maxflow}$$$. In some problems we just want to check whether flow is at least $$$x$$$. Using the fact above we can run one iteration of the algorigthm which will get us $$$\frac{1}{2}$$$ of maxflow and multiply that by two. Now just compare $$$x$$$ and maxflow.

4. Linear FFT

Usually, we use roots of unity ($$$e^{\frac{\tau\cdot t}{n} \cdot i}$$$) or primitive roots (for ntt). But why would we limit ourselves to those?

Instead of roots of unity, we can choose roots of something else, that looks complex enough. This, for example:

$$${e^{\sqrt[x]{6 \cdot \pi ^ 2 \cdot \prod_{1 \leqslant i \leqslant 10} {(x - i \cdot x^{\frac{1}{i}})}} + i\cdot\frac{\pi}{2}}} = i$$$

Let's choose a few roots of this thing which we'll use for FFT. We can notice that $$$(-1)^{\frac{i}{2\cdot i - 2}}, 1 \leqslant i \leqslant 10$$$ work. So using them we have $$$O(10\cdot n) = O(n)$$$ FFT!

5. Linear Interpolation(Actually Point Evaluation Without Finding The Polynomial)

We can interpolate in linear time if given x coordinates of given points are n consequential integers (check out 622F editorial for details). We can use this approach to perform general interpolation in $$$O(n)$$$. Let $$$f$$$ be the polynomial interpolated, n be the number of points given, $$$v$$$ be the x value in which we want to evaluate $$$f$$$, $$$x$$$ be x coordinates, and $$$y$$$ be y coordinates of given points. Let's introduce a new polynomial $$$g$$$, such that $$$g(i) = x_i, 0 \leqslant i \lt n$$$. We can solve $$$g(x) = v$$$ easily using HS math in $$$O(n)$$$ time. Now, let's interpolate $$$h(x) = f(g(x))$$$ instead of $$$f(x)$$$. We just evaluate $$$h(g^{-1}(x))$$$ since input of $$$h$$$ is n consequential integers we can do it in linear time. Easy as that!

Thanks for reading, I hope your rating will skyrocket after applying those in contest! If you have any questions feel free to leave commments or DM me(kostia244) or AryaPawn

Since there isn't any forum-like feature on atcoder I thought CF would be the best place to post it.

So I've been experiencing the following issue: editorials for ABCs are not accessible from English interface.

I used word accessible because they in fact exist you just can't get to the editorial page through English interface. Lets take a look at abc137 for example.

So here's what English page for abc137 looks like. As you can see there's no editorial link.

And here's Japanese one. It has a link to the editorial.

And if you open PDF and scroll down to page 9 you can see English version of the editorial!

Interestingly enough editorials for other contests(e.g. AGCs, jsc2019-qual) can be accessed through English interface.

I think the link to this PDF should be available from the contest page with English interface. This issue is not new, as far as I'm concerned, the same thing applies to all ABCs that have English editorial(starting from abc076). I tried opening atcoder from different browsers both logged in and out and the results are the same as on screenshots above. Do you guys have the issue or maybe it's something really messed up on my PC?

P.S. I use Ubuntu.