Codeforces Round #374 (Div. 2) Editorial

In this problem we have to compute the lengths of all blocks consisting of consecutive black cells. Let's iterate from the left cell of crossword to the end: let i be the number of the cell where we are currently; if s[i] = B, let j = i, and while j < n and s[j] = 'B', we increase j by one. When we come to a white cell or to the end of the crossword, we can compute the length of the block we have just passed (it is equal to j - i, and we need to store this value), and now move to cell j (make i = j). And if we are in a white cell, all we need to do is increase i by one. When i = n, it means that we have gone through the whole crossword, and now we print the answer.

Time complexity — O(n), and memory complexity — O(n).

The author suggests a solution with formulas: let's count two variables — cntl (the number of passwords that are shorter than Vanya's Codehorses password) and cntle (the number of passwords that are not longer than Vanya's Codehorses password). Then it's easy to see that in the best case answer will be equal to , and in the worst case it will be .

Time complexity of solution — O(n), memory complexity — O(n).

Author's solution uses dynamic programming. Let dpi, j be the minimum time required to arrive at the vertex i, if we visit j vertices (including vertices 1 and i). We have a DAG (directed acyclic graph), so we can compute it recursively (and memory constraints were a bit strict in this problem, so it's better to use recursion to compute it). Let's store the transposed version of the graph: if we had an edge (u, v) in the input, we will store (v, u). Then our function calc(i, j), which will compute the answer for dpi, j, will be like that: the base of dynamic programming is dp1, 1 = 0, all other states are equal to «-1». If we call calc(i, j), then it will work like that: if the state we want to compute is incorrect (j < 0), we return a very large integer number (any number that is greater than 109, because T ≤ 109). If the answer for this state has already been calculated, then we return dpi, j (it is easy do determine: if dpi, j ≠  - 1, then it has already been calculated). Else we begin to calculate the state. Firstly, let's put INF (a number greater than 109) into dpi, j. Then look at all the edges beginning in i and try to update dpi, j with the value of calc(to, j - 1) + w (to is the vertex at the endpoint of current edge, w is the weight of this edge). If this value is less than dpi, j, then we update dpi, j and store the information that our last update in dpi, j was from the vertex to. If we try to go by path which doesn't end in the vertex 1, then we get a value which is greater than 109, that's because that the only value we didn't denote as  - 1 is dp1, 1. So, now we have our calc function, let's compute the answer. We will iterate on the number of vertices in the path from n to 1 in descending order, and if calc(n, i) ≤ T, then we have found the answer, now we iterate on the parent vertices we stored while calculating our dp, until we come to vertex 1 (it's important because some participants sent solutions that continued even past vertex 1!) and print the answer.

Time complexity of this solution — O((n + m)n), and mempry complexity — O(nm).

Main idea: we act greedily, trying to make the best possible answer every action (each time we choose an action with minimum possible product after it).

Detailed explanation:

1. While we have zeroes in our array, we have to get rid of them, changing each of them exactly one time. Also we keep the quantity of negative numbers — we need it to make the product negative after changing the last zero. Let m be the number of zeroes in the array. If m > k, then we cannot make the product negative or positive (it will always be equal to 0), so any sequence of operations will lead to a correct answer. However, if m ≤ k, then we are able to come to negative product (if the number of negative elements was even, then we subtract x from one zero and add it to all other zeroes; if the number of negative elements was odd, then we can just add x to all zeroes).
2. If current product is still positive, then we want to change the sign of exactly one element. Its absolute value has to be minimal: suppose we have two elements a and b, |a| < |b|; let's prove that if we change b's sign, then our answer is wrong. Let m be the minimum number of operations required to change b's sign. If we perform m operations with b, then the absolute value of a won't change, and absolute value of b will become x·m - |b|. If, on the other hand, we perform m operations with a (this may not be optimal, but now we need to prove that if we change b, then the result will be worse), then the absolute value of a will become x·m - |a|, the absolute value of b won't change. The product becomes negative, so we need to maximize the product of absolute values. And then x·m - |a| > x·m - |b| and |b| > |a|, so if we change b, then the product of absolute values will be less than if we change a.
3. Now, until we have performed k operations, we choose a number with minimum absolute value and enlarge it (add x if this number if positive, subtract if negative). Let's prove that the answer will be optimal. Suppose that this algorithm chooses a on some iteration, but we can't get optimal answer if we change a. This means that we can't change a after this iteration at all (we can reorder our operations in an arbitrary way, and the answer won't change). Suppose we have to change b instead, and |b| > |a|. Let's consider the sequence of operations leading to the optimal answer when we choose b, and replace change of b with change of a, and let the product of all remaining numbers (the whole array excluding a and b after all operations) be c. If we change a, the total product will be  - (|a| + x)·(|b| + x·m)·|c|, and if we change b, we get  - |a|·(|b| + x·(m + 1))·|c| (m is the number of times we change b). Now |a| < |b| + x·m, so (|a| + x)·(|b| + x·m) - |a|·(|b| + x·(m + 1)) = |b| + x·m - |a| > 0, so the absolute value of total product will be greater if we change a. This proves that we won't come to unoptimal answer if we change a.

Time complexity: if we use a data structure similar to set or priority_queue to get the number with minimal absolute value. Memory complexity: O(n).

Firstly, if we are in some segment and we are going to sing in it, we want to sing as much as possible in this segment. So there are two cases for each segment: either we sing in the segment while we can or we just skip it.

Now we consider two different cases:

1) p ≤ 100

If we have stopped singing in the segment, then the distance we need to walk to reach the end of this segment is strictly less than p. Let's calculate two values — dpleft[i] — the answer (how many times we can sing a song) if we start from the beginning of segment number i (from li), and dpright[i][j] — the answer if we start from ri - j (0 ≤ j < p, as we already said before). To calculate the value using the value from point x, we have to find the segment which contains the point x + t and the segment which begins after this point. If we are in segment number k, we either skip it and update next segment (dpleft[k + 1]), or start singing and update the value in the point y where we stop singing (dpright[k][y]).

To find the segment containing point x + t, we can use binary search or precalculate the required indices using iterations on the array of segments.

Time complexity: or O(np).

2) p > 100

Let's use the fact that the answer is not greater than . For each value i we calculate lfi - the leftmost point where we can get it. We will iterate on those values considering that we have already calculated lfj for every j < i when we start calculating lfi. Then if lfi is before the beginning of some segment, and lfi + 1 is after its beginning, then we can try singing starting from the beginning of this segment with i performed songs currently, updating lf for next values (from i + 1 till with the values rk - (rk - lk) mod p). Using this fact we update the value for the largest answer, skipping the points in the middle of the segment. To calculate these values we need a data structure (for example, Fenwick tree) which sustains the minimum value on the suffix (lfi is the minimum on suffix beginning from element number i). All lf values are increasing, so we need only one variable to sustain the index of the segment we are using to update.

How we have to consider the points in the middle of some segment. So we have a variable storing the index of the rightmost segment which begins before lfi for current answer i. It may seem that the values from the beginning and from the middle of some segment may be used in the wrong order, but it's easy to prove that it's not true.

Copmplexity: . We can use a special updating structure based on stack to get rid of Fenwick tree, then complexity will be .