Codeforces Round 346(div2 only)

Codeforces Round 346 screen cast by eddy1021

Finish A, B, C in about 11 mins.

D is a interesting problem. Given a contour of a lake, you will start from south-most west-most point and first go to north then go around the lake. You should count the number that if you skip a turn, you will fall into the lake. The point is that the lake is always at your right hand side. Thus, it equals to the number of left turn.

E is also a good problem. Given a graph, you can assign each edge to one of its end point. Then, find the minimum number of vertex which no edge assigned to. For each connected component, if it is a tree, there must be one vertex without assigned edge. Otherwise, we can always choose some vertex on a cycle then set it as root. Then, dfs the connected component and assign each edge to the child. Finally there must be at least one edge remained which can be assigned to the root (because it is on cycle).

F is a beautiful problem. Given a n x m(both up to 1000) tables consisting of positive value, you can minus some value of each cell such that the resulting table consisting only 1 kind of non-zero value and all of them are connected and sum of them equivalent to a given k and one of them must be equivalent to the original value. We can sort up all values from big to small. Then, maintain a disjoint set and add the value one by one. Once, we add a value v if there v divides k and v/k = u. If the size of connected component of that value v from is equal or more than u. Then, we find the answer.

G is a classical problem. Given a long fence of length n(up to 1000000), from left, i-th part has height ai(up to 1000000000). You should find the number of way to mark some continuous part of them such that for each column, the part will start from top and there shouldn't be any cell of first row from the ground marked. We can come up with a easy dp that dp[i][j] means the number of way ended at j from the top of i-th part. The transition will be something like dp[i][j]=1+sum of dp[i-1][k] if top k cells of (i-1)-th part and top j cells of i-th part are continuous. But, actually, the state is too much. Then, we can observe that we only care about whether that cell is continuous to prior part and/or next part. Thus, we divide each part into those both not continuous to pre and next part/continuous to prior part/continuous to next part/continous to both part. Then, we can run similar dp with O(4*N) states in O(N) time.

 With 2 hacks, rank 2 on final standing of both div1/div2.