Div 2 C:

It doesn't depend at all if there exists any letter other than a or b in the given string. You can for sure ignore those letters, so the editorial says to erase them. Now, what you have is a string consisting only of a and b's. Also two consecutive b's can be merged as one. So your final string will look something like (a...a)b(a...a)b(a...)...

You can now consider this problem as sum of all possible product of subsets of a given set, where each element in the set is the number of a's delimited by b.

For example: In the string "aaabaabaaab", set formed will be {3,2,3,0} (0 can be ignored). Now if you have a set {a1,a2,...,aN}, then sum of all possible products of this set is equal to (1+a1)*(1+a2)*...*(1+aN)-1.

Proof:

Write the required answer as follows:

S = Sum of products of subset with (size=1)+(size=2)+...(size=N)

S = (a1+a2+...aN)+(a1.a2+a1.a3......+aN-1.aN)+...+(a1.a2.....aN)

After factorization,

S = (1+a1)(1+a2)...(1+aN)-1

Hope it helps..:)

if you don't understand the math here is my dp solution code

Basically dp[i] stores the number of valid subsequences from first i characters of the string. If the current character is not a then dp[i]=dp[i-1] otherwise we need to find the index of rightmost a to the left of i such that at least one b follow that a then dp[i]+=dp[index]

Because if we have x 'a' symbols in the block we can pick the first 'a' from this block or the second 'a' or the third or ... or the n-th or we can just not pick any of 'a' from the block.

For a given block you need to decide the number of ways to pick an "a". As it is possible that you do not choose any "a" from that segment we need to add 1 to each segment. Addidtionally you'll be required to subtract 1 from your thus obtained answer as it includes the case where no "a" is selected in all the segments and thus an empty subsequence.

a + b + ab = (1+a)(1+b) -1; a + b + c + ab + bc + ac + abc = (1+a)(1+b)(1+c) -1 in this fashion we can calculate our ans i.e sum of product of every possible combination

Suppose we have a string aaabaabaaa which can be represented by set {3,2,3} which represent 3 consecutive a's followed by b, 2 consecutive a's followed by b and 3 consecutive a's. Now from the set {3,2,3} to choose a subsequence we can choose any one of the first 3 a's and we also have an option to choose non of the a's, therefore we have total (3+1) ways of choosing the first element in our subsequence, similarly for each consecutive a's we have one more way of choosing element from it i.e to choose nothing from it. Thats why we decrease total ways by 1 as it includes complete empty sequence where we chose nothing from all sets. Hope it clears your doubt.

I did using 3 parameters:

• i: the current position in the string;

• n: meaning if i have or not a 'b' in the current subsegment;

• p: meaning if i already formed a valid subsegment.

Basicaly,

• if the current caracter is 'a' and i already have a 'b' i can start a new subsegment or continuos a previous;

• or, if the current caracter is 'a' and i don't have a 'b', i can just continuos the subsegment;

• if is 'b' i set that i have a 'b';

• else, i just go.

submission

I made it bottom up this way: The state will be the current index, with the guide question: "how many ways to make valid sequences 'til here?".

the answer for dp[i], will be all the ways to dp[i-1], plus, if the current char is 'a', you can start one new sequence here (so, plus one), or extend all the previous valid sequences before the last 'b' (because you must have an 'b' between 'a's), which means that you can extend all the valid ways until the index of the last 'b', that turn out to be dp[index_of_last_b].

solution: https://mirror.codeforces.com/contest/1084/submission/46886918

Guy, I read your code and your error is make the division integer, if you variables is unsigned long long all your operation with your variables will give a result with this type,backing to the problem when you user (int) will give error when the division gives a large result. My submission 46889415 of your code.

If at any moment the sum becomes negative then the path is not optimal since you can remove the negative part, so even if you incorrectly consider it, the answer wont change since there will be a better solution anyways.

That are the same thing.

Google Kadane's algorithm (for finding maximum sub-array sum) and then compare that technique here also. It helps me!

After struggling for some time on this problem, I finally have a proof of the algorithm that the author is proposing. Here it goes (along with the detailed explanation on how to solve the problem):

First, some terminology, that I'll use (I assume that we initially root our tree at the vertex 1): Let's define the sum on a path starting at a vertex u and ending at a vertex v as the sum of weights of all the vertices on the path minus the length of all the roads on the path, and the sum on a path starting at a vertex u and leading to a vertex v as the sum of weights of all the vertices on a path (excluding v) minus the length of all the roads on the path. Note: In this, I consider that v is always an ancestor of v.

We propose that the answer is simply the maximum of the (sum of the 2 longest paths leading to a vertex v + w[v]) over all the vertices in the tree. In case there are lesser than 2 such paths having a positive sum, we can take the other path(s) as having a sum of 0, they simply include no other vertex except v.

To elaborate more on the paragraph above, we can perform a dfs starting from the root node and since we know that there are only 2 possibilities: either the optimal path passes through the vertex v that we are currently at or it does not. I can compute the answer as the max. of the 2 possibilities. The thing proposed above is the max. sum of a path that passes through the vertex v, the other possibility can be considered by recursively computing the answer over all the children of the vertex v.

This is almost a standard kind of an approach that can be solved by a dfs. Here is my code for reference: 46893082 .

Now, onto the proof of this approach, mainly the thing about how can it guarantee that at no instant the fuel becomes negative. We prove this by contradiction.

Let us assume that our algorithm finds an optimal path in which the fuel becomes negative somewhere in the middle. Let's assume that the path goes from a vertex a to a vertex b and the answer was found at a vertex x. In this case, I can decompose the path (a -> b) as (a -> x -> b). Now, there are 2 cases:

1) The fuel becomes negative on some edge on the path (a -> x): Let's assume that the corresponding edge is from u to v. Now, consider that the total fuel at u was x and the edge weight is y. Now, in this case, the max. sum on the path that gives us our optimal answer is the max. sum on the path (u -> b) + (x - y), and (x - y) < 0. So, following the path from (u -> b) gives us a greater sum than the optimal path, which is a contradiction to our choice of optimal path, and since (x — y) < 0 , our algorithm would not consider this as the longest path ending at v, but it would rather consider some other path having a positive sum or simply the path starting off at this vertex whose sum is 0. This shows that the algorithm would never fall into such a situation.

2) The fuel becomes negative on some edge on the path (x -> b): Let's assume that the corresponding edge is from u to v. The same reasoning as above can be applied and we can get a better path (having a greater sum) than the optimal path by starting off at vertex v, and since our final answer is the maximum over all the vertices, it would rather consider that path as the answer as the optimal path. Again a situation that is not possible.

This shows that on the path chosen by our algorithm, we would never run out of a fuel. Further, our algorithm considers for all the vertices the optimal path passing through them and takes their maximum. Thus, our algorithm gives us the correct answer.

Hope it helps. :)

Look at my reply to the above comment.

If we have 3 rects and lowest negative value at middle. There is can be situation when optimal solution is only middle. But your algo will exclude it. For instance: 3 3 7 1 4 3 4 1 3

If deleted rect will be always utmost than it will give correct solution.

They are overlapping, but not nested. If they were, finding area of intersection would not be as easy as x_j·y_i.

As I see only reason is that with this assumption simpler to build envelope.

Even as sad in editorial total time "O(n) if rectangles are already sorted".

We must create an array 'p' of indices that correspond to the letters 'a'. Between all adjacent elements of this array should be an index corresponding to 'b'

This approach could also be extended if the question did not limit to using only 'a' and 'b' but had rather used the entire lowercase letters.

Solution: https://mirror.codeforces.com/contest/1084/submission/46911068

Thanks man! I loved this solution

so elegant !

helped a lot

Never mind found it: Convex Hull Trick

Each string is a path in trie. We want to choose k pathes between s and t and maximize c, which is equal to number of vertexes in union of them. For every "a" in string s and every "b" in string t we have complete binary tree in trie with some height.

In complete binary tree with height h we can consider multiset {h, h - 1, h - 2, h - 2, h - 3 (4 times), ...}. It can be proved that maximal union of l vertical ways in complete binary tree is sum of first l elements of this array, and if we want to choose some number of ways in two trees, we can combine their multisets. Let's store this huge set as array p, where p_i is count of element h - i. For complete binary tree p looks like {1, 1, 2, 4, ...}. We can sum arrays to combine multisets.

It's not difficult to sum arrays for O(n) complete binary subtrees fast.

You can do it in O(1) using Sparse-Table.

Actually if you store middle node for non-vertical path too, you'll need to compute lca not more than once per query, because it happens only when you merge to vertical paths and in result you get a non-vertical one. So you can still compute lca with binary jumps.

Your mod constant is wrong. It's 1e9 + 7, not 10e9 + 7.

For a node i, dp[i] denote the answer when you start at node i and move down. you calculate dp[i] as d[leaf] = w[leaf] and dp[i] = max{dp[j] + w[i] - c(i, j) : j is direct child of i }. Consider a path which has maximum value, this path has a node N which is at minimum depth, either the path starts at this node and goes straight down or passes through N and divides into two paths both of which moves down. So to calculate the answer you take maximum of

dp[i] — path moves straight down or,
dp[j1] + dp[j2] + w[i] - c(i, j1) - c(i, j2) — path passes through node i and moves down to j1 and j2 with j1, j2 as direct child of i.

and update the answer. here is the code https://mirror.codeforces.com/contest/1084/submission/46876865

Thanks, you are right. I'll fix it.

Try submitting your solution with GNU C++ compiler without diagnostics.

we can get 1 liter of kavss from any not empty kegs, and each time we pour 1 liter from a keg, the level of it will decrease by 1. After we get s liters, the levels in some kegs will be decreased. So our task is to maximize the lowest level.

If we expand modules we will get this:

So we know from problem situation that it is always true.

When you get the formula |p−x|+|x−1|+|p−1|, you know that x >= 1 && p >= 1, so then you will convert it to |p-x| + x + p - 2. Then just expand the module and you will get the final formula.

You are using values of uninitialized variables

Please read the original statement again. It says "the chosen path CAN consist of only one vertex". This means the answer can be the amount of gasoline that can be filled at a particular station.