Thank you! I hope we will find it :)

B:

The string is random, so borders are small (like 50), so you can solve it in length·n, with some suffix array (you can build it naively because the string is random).

Tricky case: all characters the same, when the seed is some solution of linear equation modulo.

G: Theorem in Page 3

Let , , . Then γ is the convolution of α and β. Since each number is of the form "(not very large number) / (odd number)", we can keep it modulo 2⁵⁰ (use modular inverses to divide by odd numbers), and we can use standard FFT. It seems you still need an optimized FFT.

Answer in F is a circulation of maximum weight in the given graph, where weights are equals to 1, and capacities are given.

Graph where we are making moves is bipartite. We can have more components(more graphs). In case players are playing in different components — first is the winner if he can make at least one move. If players are in the same component and in the same side of bipartite graph, winner is the first, otherwise if they are from different side winner is the second.

Is it something special (not square root idea for general modulo)? Can you describe the idea in few words? I mean 2^k FFT.

Actually, I don't even know if MCMF with FB on the queue is a polynomial solution.

For problem C, my solution just divides each integer into 3 pieces, like the trick used to module 10^9+7. I didn't know FFT module 2^k algorithm when I prepared this problem.

For F: did your MCMF have negative cycles? You have to find cycles of min average weight with FB if you want this to be polynomial at all.

There is a standard MCMF algorithm with cost scaling and push-relabel inside (edit: e.g.), it is challenging to implement it from scratch, but prewritten code is allowed, so...

I didn't know F beforehand, but I was pretty confident that my MCMF with push-relabel cost scaling would pass. My flow graph contains only m edges and n + 2 vertices. (It passed in 0.773s (or 0.829 if you model as min cost circulation with weights  - 1 instead), MCMF code is on github. The code is fast and works with negative cycles.).

Regarding C: I always use FFT (and not NTT), so I don't have to care about special modulos and the only possible issue is the size of the coefficients. There's a know trick of splitting the coefficient into lower and higher bits to handle larger numbers. My prewritten code (function poly_mul_split on github) already does this once to handle coefficients up to 10⁹ with only 3 calls to FFT per polynomial multiplication. One trick used there is to use both the real and imaginary part to run 2 FFTs in parallel.

To handle coefficients up to 2⁵⁰, split into 25 bits each and do a Karazuba step on the coefficients (compute convolutions using only high bits, only low bits and sum of low and high bits, subtract the sum of first two from the third, then add the results coefficient wise shifted by 50, 0 and 25.). This results in 3 calls to 10⁹-coefficient-polynomial multiplication, so 9 calls to FFT in total. My code runs in 0.666s, so there's quite a bit of leeway.

const int max_log = 32 + 18;
const ll MODMOD = 1ll << max_log;
void vec_mul(vector<ll> &c, vector<ll> const&a, vector<ll> const&b){
    const int bits = 25;
    int n = a.size();
    vector<ll> x(n), y(n), z1, z2, z3;
    c.resize(2*n-1);
    for(int i=0;i<n;++i){
        x[i] = a[i] >> bits;
        y[i] = b[i] >> bits;
    }
    fft::poly_mul_split(z1, x, y);
    for(int i=0;i<n;++i){
        x[i] = a[i] & ((1ll<<bits)-1);
        y[i] = b[i] & ((1ll<<bits)-1);
    }
    fft::poly_mul_split(z2, x, y);
    for(int i=0;i<n;++i){
        x[i] = (a[i] >> bits) + (a[i] & ((1ll<<bits)-1));
        y[i] = (b[i] >> bits) + (b[i] & ((1ll<<bits)-1));
    }
    fft::poly_mul_split(z3, x, y, MODMOD);
    for(int i=0;i<2*n-1;++i){
        ull v1 = z1[i], v2 = z2[i], v3 = z3[i];
        v3 -= v1 + v2;

        c[i] += ((((v1 << bits) + v3) << bits) + v2) % MODMOD;
    }
}

Technique in 2012 (wqs/clj binary search / tricks from aliens) + Technique in 2010 (http://codeforces.net/gym/100020/problem/I)

BTW, how to solve the line case in ? I can only solve it in or (using SMAWK algorithm).

The probability is P-recursive. You can read the blog of min-25 for his excellent code. And you can read the chapter 6 of enumerative combinatorial for the theory about the P-recursive sequence.

L:

Actually this problem is discussed in the paper. But my solution is not related to this paper.

You can think the problem in this way. We want to know the time when it gets contracted for each edge.

So we can solve this problem offline by a divide and conquer algorithm solve(l,r,E), which means we only know all the edges in the set E are contracted in time [l,r].

Let m=(l+r)/2, we added all the edges in E appeared before time m, and run the Tarjan algorithm on these edges, the time complexity for this part is O(|E|). E are divided into two sets E1, E2 depends on whether the edge gets contracted in time m. Then we can solve(l,m,E1) and solve(m+1,r,E2).

For each edge, it will only appear once in each level. The time complexity is O(E log E).

A:

Let be the product of factorials of sizes of groups of isomorphic children. For example, if v has 7 children {u₀}, {u₁, u₂}, {u₃, u₄, u₅, u₆}, then . The answer for the subtree rooted in x is the product of all in it's subtree.

will change only times in total: when new leaf is added it can only change value for light edge on the way to the root. Let's generate all such events.

Define hash of the rooted tree in the following way: if root has no children and over all children otherwise. d is the distance to the global root, {X} and {Y} are some random numbers.

Let return the following structure: key is some node x in the subtree of v, value is the hash of subtree rooted at v at the time when x was added. Now at node v we can simulate process of adding vertices, but with one exception: ignore vertices from the biggest child if it is already bigger than the second biggest child. It is enough to generate all needed events. For merging structures from children we will need to be able to apply some linear functions to subsegment of keys in structure, insert item in some position, merge 2 structures. Treap is sufficient here.

The final complexity is .

H:

Lets keep a set of directed paths where the following condition holds for each node of the path except the last: the node directly after this node in the permutation (if any) can only be an earlier node or the next node of the path. Initially each node is its own path. Now we search for the head of any path which has exactly one outgoing edge to another path. If this happens to be tail of the other path we can concatenate both paths and repeat. Otherwise we have special case 1 which we handle separately (see remarks at the end).

If after the process above finishes we have more than one path, there is no solution (we can never leave the path in which we start). Otherwise we have found one solution (just follow the path), but there may be more. When there is no edge from the head to the tail (which turns the path into a cycle) we have special case 2 which we also handle separately (see remarks at the end). Otherwise we can start in any node of the path, provided there is no 'back edge' (other than the cycle-closing edge) that 'covers' us, which is easy to check with a prefix-sum-like datastructure.

There are two special cases left that need to be handled. For special case 1 we know that the last nodes of the permutation must be either the path that points to the middle of another path or the nodes of the other path before the node that is being pointed at. We can just try both cases with minor modifications of the algorithm above (only extend paths outside the final vertex set, append the final vertexes at the head of the path afterwards, and there will never be more than one solution). For special case 2 an other solution is only possible if there is at least one edge to the tail of the path. In this case the last nodes of the permutation must be the prefix of the path upto the last node that has such an edge and we can handle this in the same way as special case 1.

The above can be implemented in . I enjoyed solving this problem, too bad I couldn't make it work during the contest (mostly because I was overcomplicating it), but I have it accepted afterwards. I have omitted most of the proofs, but when drawing some cases on paper they should be rather obvious.