Codeforces Round 250 | Div. 1

Posted on 02 Jun 2014

By sping128

Here is my analysis of this contest.

Problem A

I will just give a hint for A. The idea is that disconnecting the graph requires cutting all the edges. Cutting an edge e(v1, v2) can cost either v1.value or v2.value. Of course, we want the cost to be the lower one, and we can always force it by some cutting sequence.

Problem B

This problem is very interesting for me. It took me a large amount of time in order to solve it. So suppose that x is the minimum number of animals among the routes areas from p to q. If we set the cost of each edge to be the minimum value between its ends, x will be equal to the minimum edges’ cost along the path. f(p, q) is the maximum value of x’s among all simple routes between p and q. It looks really hard if we consider all the routes. We have to calculate the sum value of f(p, q) for all pairs p, q (p ≠ q). But actually this sum is equal to c(e1) + c(e2) + ... + c(em) where c(ei) is e_i.cost × the number of all pairs p, q whose f(p, q) is e_i.cost.

To find c(ei), we need to start with the largest edge. If e(u, v) is the largest edge, f(u, v) is surely equal to e.cost. Then we put u, v into the same set. Then move to the second largest edge and so on. Notice that for each edge e(u, v), f(p, q) = e.cost where p ∈ the set of u and q ∈ the set of v, so c(e) = e.cost × |u| × |v|. Then we union u and v. Doing this to all the edges in descending order of their weights will give you the sum value of f(p, q) for all pairs p, q (p ≠ q). And the best data structure that can do this very efficiently is Disjoin Set.

Problem C

One can easily realize that this problem is a dp problem. The question is: what is the best way to do dp? Well let dp[i][j] = the number of ways to split the polygon p[i], p[i + 1], ... ,p[j] into non-degenerate triangles. Note that i can be greater than j and that will represent a polygon p[i], p[i + 1], ..., p[n], p[1], p[2], ..., p[j]. How can we calculate dp[i][j]? We can try splitting the polygon(i, j) by a non-degenerate triangle(i, k, j) where k is between i and j. We need to check that triangle(i, k, j) doesn’t cross the entire polygon. So dp[i][j] will be the sum of dp[i][k] × dp[k][j] for all valid triangles(i, k, j). By doing this, we don’t have to encounter double-counting problem, because we split the polygon by different triangles(i, k, j).

Problem ​D

This problem is basically a classic problem that can be solved by Segment tree if we don’t have the second type of operation. Let’s think about the second type of operation (mod). Does it really increase the difficulty of this problem? If we handle the second operation by simply mod-ing down the tree, we can stop when the maximum value of all the values in a subtree is less than the mod value. If x < mod, x % mod = x. Another fact is that mod-ing significantly decrease a value. Even if we mod everything down the tree, their values will become less than some mod value pretty fast. By these two facts, we can just solve this problem straightforwardly by using the normal segment tree. Each tree node keeps two values: sum (the sum of this subtree) and max (the maximum over all the leaves of this subtree).

Lesson learnt