Is it a closed contest? How to register for it ? My Yandex username password does not seem to work it says "Authorization failed. Please, try again or contact your coordinator"

Div.2 contest ended 40 mins later, hopefully no-one answered during contest time.

Problem + solution is more or less equivalent to problem E here: https://agc002.contest.atcoder.jp/tasks/agc002_e.

Surprised that not more teams solved it.

Solution for J:

Let A[b, e] = a_b, a_b + 1, ..., a_e.

For the initial sequence A[b, e], Win[b, e] = 1 if Alice wins the game. otherwise Win[b, e] = 0.

If A[b, e] is monotone(nonincreasing or nondecreasing), then Win[b, e] = 0. For other cases, Win[b, e] = (!Win[b, e - 1])|(!Win[b + 1, e])

Key idea : Except a few cases, Win[b, e] = Win[b + 1, e - 1]. then we can calculate Win[b, e] easily by its b + e value.

For a sequence S, if there is a contiguous monotone subsequence with length L and there is no contiguous monotone subsequence with length L + 1, we call S is L - monotone.

1. If A[b, e] is (e - b + 1) - monotone, then Win[b, e] = 0.

2. If A[b, e] is (e - b) - monotone, then Win[b, e] = 1.

1. If A[b, e] is (e - b - 1) - monotone

3-a. A[b, e - 2] is monotone or A[b + 2, e] is monontone

without loss of generality, A[b, e - 2] is monotone. Then Win[b, e] = !Win[b + 1, e] = Win[b + 2, e] = !Win[b + 3, e] = .... it continues until Win[i, e] which A[i, e] is monotone. So if we precalculate L(e) := (the minimum value of x that satisfies A[L(e), e] is monotone) for all e, then we can calculate Win[b, e] by the value L(e).

3-b. A[b + 1, e - 1] is monotone

It is easy to show that Win[b, e] = 0

For other cases, it is easy to show that Win[b, e] = Win[b + 1, e - 1].

How did you solved it?

Was problem I solvable with suffix array or suffix automata was intended? And how to solve F?

I: Build suffix automaton for the whole string. After that you can start feeding string s to the automaton. If you go to the vertex v, this will mean that we added  + 1 occurrence for all its suffixes.

Hopefully all such suffixes lie on path via suffix links of vertex v, thus you have to add  + 1 on the path from v to the root (noting that any vertex u has multiplicity len[u] - len[link[u]]) and output sum of squares of numbers in all vertices taking into account their multiplicities. It can be done with heavy-light decomposition. Code: code.re/bbW

I is solvable with suffix array + divide and conquer.

The answer for a single string can be calculated if you know Sum(LCP[i, j]) for all unordered pair i < j. kriii will explain details / proofs in this part. We should solve this problem for every suffix.

One naive strategy is to build a suffix array sfx[], and LCP array lcp[] for a given string, then performing a[min(sfx[i], sfx[j])] += Min(lcp[i+1], lcp[i+2], ..., lcp[j]) for all i < j.

We can solve this by divide and conquer — We will process this for all pairs . The strategy is to batch process all pairs with same LCP value in "conquer" stage.

We start from m / m+1. If LCP[m] < LCP[m+2], then we increase right end, otherwise we decrease left end. To generalize. If current left end is s, and right end is e, then you know either or have same LCP value. (I strongly recommend you to simulate by hand). In the end, we end up having O(nlgn) "slices" to process.

Now, we can process those slices with sweep line, in total O(nlg²ⁿ) time.

That is the ordinary random case N=99998, L=94633361, R=475442794.

A: For each point, the possible center of the donut to contain that point is also a donut. After adding each score to the corresponding region, the answer is the one with maximum score. It's equivalent to add the score to a square with length r and subtract the score to a square with length l.

It can be done with sweep line and segment tree in .

How to squeeze FFT approach in L? I know that some participants done it..

K

I wouldn't say that 3 teams is many.

NVM. It works. I used find instead of lower_bound/upper_bound to BS in the set. Stupid mistake.

I'm not sure if it helps, but it has some similarity with this this task, although this one is a lot harder.