It doesn't work for s = "ab", t = "ba".
If c = lcs(s, t) = "a", the only answer you will find is "bab", though there are two answers.

Why can I sometimes see a "not solved" sign for a hidden test set in the scoreboard?

Your estimation can be improved. It seems you just count the number of independent sets in a rectangle 3 × n. But we can also use the conditions for truthful processors in the central column of this rectangle. This gives that the number of transitions is O(αⁿ) where α is the largest root of x⁵ - x⁴ - 3x³ - 6x² + 1, α ≈ 2.8.

In this case all f(n) are between 0 and k / 2. . .

You need to use fast exponentiation to find . Use the inequality 0 ≤ f(n) ≤ k / 2 to find the sign ( ± ).

If k = 1 and f(0) = 10⁹, the answer is very large. Do you need to find it modulo a prime? If not, you probably missed some inequality, like 2f(0) ≤ k.

We don't even need pairs because  - 1 is a quadratic residue modulo p (if p if NTT-friendly).

If , we want to get . It means that for each prime p its power in a^x is not less than its power in m₁. Power of p in m₁ is at most . On the other hand, if , power of p in a^x is at least .

Hmm, my solution with vector get TL, but this happened only because the random number generator is bad. All queries are of the first type. Is it possible to fail solutions with tree in the same way?

For arbitrary matrices it's false. For example, . M^p - 1 = 2^{(p - 1) / 2}E. If 2 isn't a square modulo p, M^p - 1 ≠ E.

Also you can use Lagrange's theorem for group. The order of this group is (pⁿ - 1)(pⁿ - p)... (pⁿ - p^n - 1). For n = 2 we get A^{(p2 - 1)(p2 - p)} = E. Doesn't look like the best estimation, though.

. For scalar matrices it's true: it's just a usual Fermat's Little Theorem.

map<int, vector<int>> pows;
int k = sqrt(m);
for (int i = 0; i <= k; ++i)
    pows[Pow(a, k * i)].push_back(i);
for (int i = 0; i <= k; ++i)
    find something in pows[b * Pow(a, i) % m]

If we want to find the smallest solution modulo prime, in the last line we just choose the smallest element from this vector. In our case we need to do some binary search here.

Did you know how to do it if m is prime? In the same manner we can find the smallest x such that and x is large enough (). It remains to check small values of x.

Nice example. That's why we should care about small values of x. , but for all x ≥ 2 .

If x is too small, we can look at x + tφ(m₂). . For sufficiently large t we get .

In this example φ(m₂) = 6, so for t = 1 we find x = 7.

m is product of some powers of primes p_i^k_i. Some of these primes divide a, some don't. m₁ is a product of those powers for which p_i divide a. m₂ is a product of other powers.

For example, if a = 60 = 2²·3·5, m = 126 = 2·3²·7, m₁ = 2·3² = 18 (2|a, 3|a), m₂ = 7 ().

As far as I understand, you want to solve the equation . If , you can use baby-step giant-step algorithm.

Let m₁ be product of all prime powers p^k such that p^k|m and p|a. m₂ = m / m₁. By construction m₁ and m₂ are coprime. For sufficiently large x (at least ) . Check the small values separately.

If , there are no solutions. Otherwise we need to solve the equation modulo m₂. . This case has been analyzed above.

We need to find max(p_i + a, ..., p_i + b) for all i where p_i are prefix sums. Easy way: use segment tree. Faster way: use queue with a maximum.

Use binary search on answer. We want to know if the answer is more than x. Subtract x from all elements. Now we want to find a segment with length from A to B and a positive sum. Can you do it?

If all steps of your path go down, you don't initialize the variable and get undefined behavior in the last cycle.

Yeah, it was a terrible idea to prepare this contest in just two days :(

At first, if the last value is negative, k[n] = 1, not k[n-1].

Of course, some k[i] can change when we add a number to the end. But I don't really understand where is the problem for the linear solution. In this case you can just re-find all k[i].

Blocks are needed to implicitly store k[i]. Navick has already explained about them.

If two characteristics are equal for all initial creatures, they are equal for all creatures. So, the characteristic is completely determined by the sequence of k zeroes or ones.

You are completely right. Thanks!

Auto comment: topic has been translated by khadaev (original revision, translated revision, compare)

No, in precomputation we only build two Dijkstra trees, from s and from t. We need them to find sets A and B.

For each query we find A and B, iterate through edges, and find the answer.

No, for each edge xy we just use precomputed values of d(s, x) and d(y, t) in the original graph.

The word "cut" does not mean that you need some mincut algorithm. Let's explain it in other words.

For a given edge e we can define two sets of edges: and . path(x, y) is some shortest path between x and y. We will assume that , otherwise the answer is obvious.

It's easy too see that each vertex lies either in A or in B. Consider the earliest moment when we go from the vertex in to the vertex in . By definition, we can go from s to x by the shortest path in the original graph, the same is true for y and t. So the path is uniquely determined by the edge xy. We just need to go through all edges xy such that and .

It works in O(qm) for queries and for shortest paths precomputations. Also there is a way to sped up it to .

No, you need FFT for the multipoint evaluation.

Think about binary search for the answer.

Hint: try to find all pairs (x, y) such that you can find two non-intersecting subsets with sums x and y. It's very similar to all possible sums of subsets.

There is some solution that's probably slow in practice, but for small A it's asymptotically faster than trivial:

Let's divide our numbers to almost equal groups and construct polynomials for each group separately. P_i is a polynomial for group i, P is a polynomial for all numbers. Find all products P·P_i using FFT.

For each query we can find a pair i such that P·P_i has a nonzero coefficient. Now let's just iterate over all numbers in i-th group and check does it fit.

Overall complexity is .

If A is an upper bound for elements in array, we can solve the problem in . Let's consider a polynomial where a is our array. k is sum of two elements if and only if coefficient of the term t^k in P² is nonzero. So you can find P² using FFT and handle queries in O(1).

Though, this solution can't find indices of these elements.

Are you sure you understand the statement correctly?

"1 1 1" is balanced, but your sets aren't equal. "1 1 2 2 2 2" isn't balanced, but your sets are equal.

Let's fix top-left corner of the square. We need to find the largest square with this corner. We can use binary search and check whether the square is filled, using prefix sums.

EDIT: sorry, misread

Another (quite standard) way to solve the original problem:

We need a queue with "get a minimum" operation. We can simulate a queue with two stacks. Stack with minima is easy: we just need to store pairs (value, minimum of values below this).

Finding best k minima can be solved in the same way. Stack with k minima is not harder: just store k minima of values below this. It obviously work in O(nk).

As far as I understand, solution from this forum also use matrix exponentiation, and matrix size is even more than in my solution, so I don't know how it can work fast without this trick.

Also you can read my code, it's much shorter than your. https://pastebin.com/8yeXvatX

I will explain only the second technique. The first thing is just some non-asymptotic optimization, probably you don't need it to get AC.

You don't really need to find A¹⁴, you need to find A¹⁴v for some vector v. So you can represent it in the form A⁸(A⁴(A²v)). All multiplications are matrix-by-vector, they are O(n²).

Denote by cnt_n, d the number of ways to get the score n if the last digit is d. Let's analyze the small case: d = 3. We have recurrence relations:

cnt_n, 0 = cnt_{n - 1, 1} + cnt_{n - 4, 2}

cnt_n, 1 = cnt_{n - 1, 0} + cnt_{n - 1, 2}

cnt_n, 2 = cnt_{n - 4, 0} + cnt_{n - 1, 1}.

Do you know how to convert usual recurrence relation (like Fibonacci numbers) to matrix expo? Here we can do almost the same. Let's define a vector v_n = (cnt_n, 0, cnt_{n - 1, 0}, cnt_{n - 2, 0}, cnt_{n - 3, 0}, cnt_n, 1, cnt_n, 2, cnt_{n - 1, 2}, cnt_{n - 2, 2}, cnt_{n - 3, 2}). These relations mean that v_n + 1 = Av_n for some matrix A, so v_n = Aⁿv₀.

As far as I understand your solution work like this: you have some matrix A and vector v which depend only on the base and you need to calculate Aⁿ·v for different n. When you use fast exponentiation, you find A^2k for all k up to logarithm, multiply some of them and then multiply it by v. We can do the same, but in different order. Let's precalculate all A^2k. Now instead of O(n³) matrix multiplication we can use O(n²) matrix by vector multiplication. We need to multiply matrices by vector, so time complexity is per query and for precalc.

Btw why 77? I got 100 and i can optimize it to 50.

If we can solve this problem in O(n), we can process q offline "upper_bound" queries to the sorted array of size n in O(n + q). Just reverse this array and add queries to the end. Answers for your problem are precisely these upper bounds.

I can't rigorously prove that it's impossible but i have some ideas. Let's assume that it's possible and construct sorting algorithm that looks to be linear in average.

We need to sort an array a₁... a_n. Let's randomly divide it into two subsequences b₁... b_k and c₁... c_n - k. Sort the first sequence. Now let's run hypothetical algorithm for upper bounds: b_i is an array, c_i are queries. How many elements of c_j lies between b_i and b_i + 1? It seems to be small in average, so we can sort them by any usual algorithm. Overall (average) complexity is f(n) = f(n / 2) + O(n), so f(n) = O(n).

For example, if we need to process online "push_back" updates.

If we can compress values, persistent segment tree is . If we can't, wavelet tree is also .

No, it's not in his parent's subtree. If optimal vertex for v is not in subtree of v, it's also optimal for parent cause path from v to this vertex goes through it's parent. But we need to find not the best city but best city different from the current, yeah? For example, we can find two best cities.

Q1: We can delete cats/dogs instead of moving them: just move them next to one of the remaining cats/dogs. The only tricky case is when we delete all cats or dogs, we will process it separately. Let's calculate dp[processed prefix][cat or dog][balance] = number of moves. Balance is the difference between number of "free" lions and number of cat-dog borders. Lion is free if it doesn't stay between a cat and a dog. All transitions are straightforward, answer is minimal value of dp for nonnegative balance. But i don't know any easy way to work with cases when we delete all cats or dogs, my implementation is really ugly.

Q3: subtree dp. For any vertex v we can find vertex x in the subtree of v with maximal a_x - d(x, v). Now let's run dfs from the root and find the vertex with maximal a_x - d(x, v) among all vertices. If it's in subtree, we know it. Otherwise we can use answer for the parent. For any vertex we know next vertex on our path. If k is small. we can just simulate it. But the path will quickly become a periodic! So let's find a cycle and get the answer.

Your coefficients looks correct. But in my first sentence i meant that there is an easier way: let's consider a function g(n) = f(n) + n. 1, 3, 8, 21, 55. Something familiar, isn't it? I don't know how I came up with this, though.

Generating functions are a rather universal way of solving such problems. I'm pretty sure that in this problem you can apply them, although I haven't tried.

Let's also add a decomposition of n to the one term, the answer will be easier. Can you write any slow solution (DP or even bruteforce) to calculate it? It's really easy to guess the formula by values for small n.

What about "change an element" queries? If we solve the problem offline, they can be reduced to two "toggle" queries. But is it possible to solve it online? For example, by using order statistic tree instead of BIT?

Also can someone explain why this structure is called a "wavelet tree"?