197A - Plate Game

The trick is that if the first player can put down a circle, then he will win. The strategy is to put the first circle exactly on the center, and as long as the second player can put one circle, the first player can simply put another one on the center-symmetric position. Thus, the problem has been reduced to determining whether the first circle can be put on the table or not.

197B - Limit

For , it can be written as ( is similar). Thus, as x -  > ∞, , we can further reduce the term x^n - m based on the value of n - m.

197C - Lexicographically Maximum Subsequence

We should first select all the “z”. By denoting the position of the last “z” as i_z, we should further select all the “y” with indices larger than i_z. Suppose that the last position of “y” is i_y, and we select all the “x” with indices larger than i_y. The above process is repeated until we reach the end of the given string. If some letters do not appear in the given string, we can simply skip them.

197D - Infinite Maze

The main observation is that starting from “S”, if and only if we can reach two different points (x₁, y₁) and (x₂, y₂), while x₁%n = x₂%n and y₁%m = y₂%m, then the answer is yes (see proof in tutorials).

I can only prove the “if” part. We can construct a scheme to go infinitely far away. We can draw a line from “S” to (x₁, y₁), and from “S” to (x₂, y₂), respectively. Although these may not be straight lines (in fact they are paths), we can still treat them as “straight” and thus they form an angle. Next, (x₂, y₂) also serves as (x₁, y₁) of some other “S*”, and “S*” also has its own (x₂, y₂). If we repeat the above step, one can see that they just form some pattern which consists of the same copy but have infinite extension.

As for the implementation, we can just use simple bfs and adopt some extra indicators to tell to which board the current (x₁, y₁) belongs.

196E - Opening Portals

I follow the turotials.

At first, we run a “parallel” Dij's algorithm to find out, for each node, the distance to its nearest portal node. This algorithm can be implemented based on SPFA (shortest path faster algorithm, and one can find a large number of materials on the internet). Specifically, we use dis[i] to denote the distance from node i to its nearest portal node, amd use pre[i] to denote this nearest portal node. These two arrays should be updated in the SPFA framework.

Next, we try to construct a new graph which only describes the “distance” among portal nodes. We can enumerate each edge given in the original graph, and for each edge connecting two nodes u and v, we find the corresponding two portal nodes pre[u] and pre[v]. We add a virtual edge between pre[u] and pre[v], with weight of dis[u] + w + dis[v], where w denotes the weight of edge between u and v. After constructing the new graph, we can run Kruskal's algorithm to find the MST.

However, I still have two questions...

1) How to prove that the shortest path (virtual path) between any two portal nodes are always included in the new graph. We only know that for some two portal nodes u and v, the shortest path must go through some edge in the original graph. This means that if we want to find this shortest path, there must exist at least one edge having u and v as its two nearest portal nodes, but how to guarantee this...

2) I think this is a “steiner tree” problem (see 152E - Garden), and if I am correct, this is NP-hard and it is weird to have a polynomial solution. Where am I wrong...