Codeforces Round 343(div2 only)

Codeforces Round 343 screen cast by eddy1021

Solved A,B with about 5 mins.

C is a good dp problem. Given a round brackets with length m, you should find the number of way to add some prefix and suffix then make it a valid brackets sequence with length n such that n-m <= 2000. Dp state is dp[a][b] being the number of way for a valid prefix brackets sequence with length a and b opening brackets not matched yet. So we can enumerate the length and the number of opening brackets remained of the prefix. And suffix is as a symmetry prefix. Thus, we can also take the dp value of our dp state.

D is a classical problem. Given n cylinders, you should find some of them with maximum total volume. i-th and j-th cylinders can take at the same time if and only i<j and volume of j-th is strictly greater than that of i-th. Direct dp state is dp[x] as the maximum total volume ended at x-th cylinder. Transition is that dp[x]=Volume of x + max(dp[y]) for all valid y. Thus, we can use a copy on write segment tree to maintain the maximum dp answer of each volume.

E is a interesting problem. Given a tree and m querys,for each query, you should find the expected length of the loop when we add a edge in that tree the given pair will on that loop. Denote the given pair as u and v. The answer will be the expected length to u + distance(u,v) + expected length to v + 1. Thus, we can compute each part then add them. The way to calculate the expected length to u is that for those nodes not on the the v side of u, we can sum up their distance to u. Thus, expected distance to u will be the summation divided by the number of nodes. And don't forget u should also be counted. The summation of distances and number of nodes can be calculated by tree-dp. In first time, dp the answer of subtree. In second time, we can use the dp value to extracted the actually summation of distances and number of nodes.

rank 8 on final standing of both division.