Hint: When does some vowel stay in string?

Hint 1: It's never profitable to go back. No prizes left where you have already gone.

Hint: At first we will solve the problem mentioned in the statement. The formula is . Firstly, each submatrix k × k should have at least one row with zero in it. Exactly non-intersecting submatrices fit in matrix n × k. The same with the columns. So you should have at least this amount squared zeros.

The function of the path length is not that different from the usual one. You can multiply edge weights by two and run Dijkstra in the following manner. Set dist_i = a_i for all and push these values to heap. When finished, dist_i will be equal to the shortest path.

Model solution

Hint 1: Count the number of times each number appears in the sum of all f_a.

Hint 2: Try to find a sufficient and necessary condition that a_i appears in f_a of a permutation.

More hints

Hint 3: Prove that a_i appears if and only if all elements appearing before it are strictly less than it (other than the largest element). And then try to solve the problem first in O(n²).

Now try to solve to simplify your solution with O(n²).

Solution

It is easy to see that i-th element appears in f_a if and only if all elements appearing before it in the array are less than it, so if we define l_i as the number of elements less than a_i the answer will be equal to:

By determining the index of a_i, if it is on the index j then we have to choose j - 1 of the l_i elements smaller than it and then permuting them and then permuting the other elements. We can find all l_i with complexity of O(n log n). If we were to implement this, the complexity would equal to O(n²).

Now let's make our formula better. So let's open it like so:

and then it equals to:

and now let's take out the l_i! ,

now let's multiply the inside the first sigma by and the second sigma by (n - l_i - 1)! and it gets equal to:

and it is easy to see it equals to:

and using the fact that

it will equal to:

So the final answer will equal to:

of which can be easily implemented in O(n log n). Make sure to not add the answer for maximum number in the sequence.

There is also another solution that you can read here.

Model solution

Let's denote n = |s|.

Hint: There is a simple solution: dp[m][mask] — best answer if we considered first m characters of the string and a mask of erased substrings. However, storing a string as a result of each state won't fit neither into time limit nor into memory limit. Can we make it faster?

This is a more complex version of problem G from Educational Round 27. You can find its editorial here.

To solve the problem we consider now, you have to use a technique known as dynamic connectivity. Let's build a segment tree over queries: each vertex of the segment tree will contain a list of all edges existing in the graph on the corresponding segment of queries. If some edge exists from query l to query r, then it's like an addition operation on segment [l, r] in segment tree (but instead of addition, we insert this edge into the list of edges on a segment, and we make no pushes). Then if we write some data structure that will allow to add an edge and rollback operations we applied to the structure, then we will be able to solve the problem by DFS on segment tree: when we enter a vertex, we add all edges in the list of this vertex; when we are in a leaf, we calculate the required answer for the corresponding moment of time; and when we leave a vertex, we rollback all changes we made there.

What data structure do we need? Firstly, we will have to use DSU maintaining the distance to the leader (to maintain the length of \textit{some} path between two vertices). Don't use path compression, this won't work well since we have to do rollbacks.

Secondly, we have to maintain the base of all cycles in the graph (since the graph is always connected, it doesn't matter that some cycles may be unreachable: by the time we get to leaves of the segment tree, these cycles will become reachable, so there's no need to store a separate base for each component). A convenient way to store the base is to make an array of 30 elements, initially filled with zeroes (we denote this array as a). i-th element of the array will denote some number in a base such that i-th bit is largest in the number. Adding some number x to this base is really easy: we iterate on bits from 29-th to 0-th, and if some bit j is equal to 1 in x, and a[j] ≠ 0, then we just set (let's call this process \textit{reduction}, we will need it later). If we get 0 after doing these operations, then the number we tried to add won't affect the base, and we don't need to do anything; otherwise, let k be the highmost bit equal to 1 in x, and then we set a[k]:  = x.

This method of handling the base of cycles also allows us to answer queries of type 3 easily: firstly, we pick the length of some path from DSU (let it be p), and secondly, we just apply \textit{reduction} to p, and this will be our answer.

Model solution