Исправлено

Fixed

so I decided that I do the contest and I did.

Reverse psychology — Activated!

You missed this I guess :)

I asked him. He didn't reply :/

yes!Next regular time is 9:45pm, I think this is ok,but too far.

Yes，it is

:((

3 problems

I was confused by Div1A not mentioning that you can choose u,v freely and talking about 'the city u/v' and 'the path' (not a city/path).

So I asked 'what are u,v, they are not in the input' — answer: 'Yes'

Problem statement in russian was very unclear too — I doubt we should blame google-translate here.

yeah, difficult to understand

Use a segment tree to quickly calculate, for any segment [l, r], if there is a path that contains all values in [l, r].

Each node should store a pair representing a path, but combining pairs requires a lot of casework and isn't fun :(

for each prefix, calculate the maximum string you can make, then add it to the answer.

The characters being 'a', 'b' allows for a pretty easy solution that is barely programming. You can consider s and t as binary strings and iterate through their prefixes. While the prefix difference is less than k, you add it to the sum and when it grows larger you add k instead.

→ Reply

We have to find the no. of index sequences where in which all the string elements at those indexes are equal to 'a' and between every two adjacent indices there must be atleast one 'b'.

So, we divide the string into pieces, where each piece contains those "a's" which are preceded by same no. of "b's". e.g. : "aabaabbaaabab: is divided into "aab" "aabb" "aaab" "ab".

Now, from each piece, we have the choice of taking either 0, 1, 2... till count of "a's" in that piece. So, total "count of a's in that piece + 1" choices.

Now, to find the total required sequences, we multiply the no. of choices from each piece. But, since we want to choose a non-empty sequence, we subtract 1.

Problem — Count number of subsequences of the string which consists of only a's and every two a's should have at least one 'b' between them in the original string.

Solution — Pretty standard approach. Iterate over the string. Maintain a counter. When you get an 'a' increment the counter. When you get a 'b' multiply the counter to answer and set counter to 0. Do not forget to multiply the counter again for trailing a's.

It's a classic dynamic programming problem. The first thing is that you should save the position of 'a' beforehand. Okay, so f[i] is the way to choose the array with the positions of all elements are not greater than the position of ith 'a'.
f[i] = f[i-1]; f[i] += 1 (Should take care of the case that the array contains only one 'a'). Now if we choose ith 'a', we should find the previous proper 'a' that has the largest index, which means that between that 'a' and the ith 'a' contains a least on 'b'. This can be done by binary search. The overall complexity of this sol is O(nlogn)

Well, you also may consider it and honestly push maximum possible sums in two dfs, one for pushing them to the root and another one for pushing them from the root.

What? How?

can you please elaborate why that condition is useless?

https://www.geeksforgeeks.org/sum-products-possible-subsets/

Check this case:

6
100 100 5 5 5 5
1 3 0
2 3 0
3 4 0
4 5 0
4 6 0

The right answer here is 205.

why you used double dude? i am sure there is no fraction needed

Maybe they wanted to block O(nlogn) CHT. But it is poor because there is a sort involved already.

Maybe they were overly paranoid of n² dp?

You wrote the blog about li chao tree, so I'm surprised you don't have a fast CHT implementation :O

why overflow? isn't the answer always within long long?
Update: sorry my implementation is probably different from yours.

DFS, where each node returns the best path in its subtree that ends at this node. Do this while maximizing the answer among the sum of best 2 children of each node with each other, i.e sum the paths returned from the best 2 children and check if they're better than your answer, they resemble the best path passing through this node, also try taking the best path alone, or just the gas of the current node.

dp on tree.

first, make the tree rooted. dp[u] = maximum gasoline that can be starting from u and ending to node that have u as its ancestor

for each node, you can find the maximum of the path passing that node by finding the best two children of that node.

Centroid decomposition — force the centroid to have a depth of 0, and find depths of subtree accordingly (add weights, subtract lengths of edges).

Then add in the w[centroid] when considering the answer.

Unfortunately,

I put for (auto e : arr) ARR.insert(e); in the wrong layer of looping causing it to do nothing at all! :(

First notice that an edge and a vertex only comes into the picture along with some other vertex when w(vertex)-w(edge) is positive. In this case it will only increase the gasoline upon reaching some vertex. You need to maximize this.

The way to do it is calculate (in) value for the vertex which denotes answer if you start with this vertex and travel down...Also calculate (out) for each vertex which denotes max answer you can get starting from the node and not traversing the children of it.

As wewark says keep 2 best children for it to do it in linear time.

It is the in-out dp trick. Sad it is for I wasn't able to complete its implementation on time.

Below is the link to its video tutorial. https://www.youtube.com/watch?v=Xng1Od_v6Ug

Please give proper respect to the power of #define int long long xD

Wait where did E require that check? I didn't have it and got AC

Also I dont see any point in characters in B being 'a', 'b' instead of 'a' to 'z'.

it's hard for me to explain but I can give the hint to forget about all characters that are not 'a' and 'b', and count number of adjacent 'a's and store it in vector. Then find formula for it. Check my submission for maybe more info about formula.

It's simple combinatorics.

You need to have atleast a 'b' if you consider more than 1 'a's of the sequence. So, what you can do is count 'a's in each segments seperated by a 'b'. Now, suppose for some segment you have x a's. So, you have x+1 choices(select 0, 1, ...x) to select 'a'. Multiply each segment's (x+1) values. Now, you need to subtract 1 as you need to have a subsequence of length atleast 1.

hey i used a dp approach: consider there are x continuous segments of b's in the string which divide the string in (x+1) parts. Let the no of a's in the (x+1) segments be a1,a2,......a(x+1). Then DP[i]=(a[i]+a[i]*DP[i-1]+DP[i-1])%Mod, DP[i]->no of ways considering first i 'a' segments. Base case: DP[1]=a1 and final answer would be DP[x+1]. Also you would need to check separately when the string would contain no 'a' or no 'b'.

That's pretty easy to see since if you would have negative amount of gasoline after some prefix, you can just disregard this prefix and get strictly better answer.

Seeing your performance in recent contests I don't think it's going to be just a moment, congratulations!

Yeah I think tourist has a script that registers him automatically to the next contest if he is not in the first place anymore,..

((i-x)+(i-1)+(x-1))*2. So x cancels out. Similarly when x> i.

Ways to choose some subsequence(not necessarily continues) of ‘a’ that between 2 element of this subsequnce there exist a ‘b’