Simple & Quick Summary.

CF 285

A: The key point is Forest. So find the vertex node with degree of 1, we can get an edge. Repeat it until no more found.

B: Conversion between Factorial base and Normal decimal base. Use a binary indexed tree to keep numbers have appeared and find the amount of numbers less than the current number. Basically:

• Normal -> Factorial fnum[i] = num[i] - less_than_i
• Factorial -> Normal binary search k that k - less_than_k = fnum[i]

C: I misunderstood the meaning during the contest: find the number of sub-strings which can be rearranged to be a palindrome.

Then I tried to use a naive method, divide the array to K(usually sqrt(n)) blocks. For each block, use set<int> to record its state, do a "swap line" with each start point. The complexity can be reached O(N*sqrt(N)*log(N)), also huge.

The right task is: find the number of sub-strings which can be rearranged to make the total string to be a palindrome.

It should be easier, but still not interesting. So let it go.

CF 286

A: This is a strange problem. I failed to find the point of problem A while solving the CF-style contest for the first time.

Assume there are N grids, given the amount of goods on each grid. Goal of the game is to collect as many goods as possible.

Now you can jump between grids, the step must be positive, and if the previous step is l, the current step can only be l, l+1 or l-1. The limits of N is 30000.

Here is the key, N ≤ 30000. As we know (1 + 2 + ... + s) = s * (s + 1) / 2, even if we keep increasing(or decreasing, the same) the step length in every step, the maximum s is about 250, to reach the final destination.

So the dp state is about [position(30000)][step(-250,250)], approximate to 15 millions. But be careful, map or unordered_map is too heavy to keep the state, just use a big array.

B: Rebuild a directed graph to keep the original connectivity. It's NOT necessary to use the original edge.

Because we can rebuild it by our own way, a simple cycle to make all pairs of vertices connected. So for each connected component, by the way, here we treat the edge to be bi-directed, if it's a DAG, a tree is enough, otherwise use a cycle.

It's totally a different problem if you can only delete useless edges to keep the original connectivity. First find all the SCC(Strong Connected Component), shrink the original map to a DAG forest. Then for an edge i->j, if there exists i->k and k->j as the same time, we can delete it. Just like the Floyd algorithm. The total complexity can be O(N^3).

D: Color the edge of a map with a specified color, and a colored map will be simple. For each query (u, v), find the number of different color in which they are connected.

Hash vertex ID in each colored map, and use a disjointed set to keep the connectivity. Then do an offline traversal. One optimization is keep the color set for each vertex, only loop it when both of the vertices have that color. And verify it by looping the vertex with smaller number of colors.

Fortunately, it got Accepted. (And the only one I had passed TAT)