116A - Tram

The solution is straightforward. It is sufficient to record the number of people in the tram, and find out the maximum value.

116B - Little Pigs and Wolves

This turns out to be a simple problem if one has noticed that there exists at most one wolf around any pig. Thus, it is not necessary to consider the case where some single pig can be eaten by multiple wolves. We can enumerate each wolf and check whether there is at least one pig around it.

116C - Party

We can find that there are multiple connected components, and then implement DFS or BFS to each component, starting from the node which does not have any superior nodes, to calculate the maximum depth. This is just the required answer.

116D - Lawnmower

Note that once we move to the lower floor, we can never return back. Thus, we must clean up all the weeds on the current floor, and then move downstairs.

For each floor, we denote the positions of the leftmost weed and the rightmost weed as pl and pr, respectively. Then, suppose that we reach the current floor at some position p. No matter which direction we are facing to, the minimum distance that we need to move is either |p - pl| or |p - pr|, and finally we stay at either pl or pr. Now, we find the next floor that has at least one weed (note that there might be several floors without any weeds during our moving).

After finding the next floor, we can find that we should move from the previous position to the leftmost weed or rightmost weed in “horizonal” direction, according to whether we face to the same direction or not. The above calculation resembles the Manhattan Distance, whose horizational distance and vertical distance can be independently computed.

116E - Plumber

Well, I think this is really a brain-storm problem. When I finally understand the tutorials, I feel that I have seen a new world...

Let us first consider that we have 1 × m empty cells. If we only focus on the horizonal pipelines, it can be seen that the pattern can only be either “LRLRLRLRL...” or “RLRLRLRLRL...”, where “R” means that the pipeline is connected to the right side while “L” means that the pipeline is connected to the left side. For the vertical pipelines, we have 2^m patterns, since they will never lead to “leaking” states.

Now, we extend the above case to 2 × m empty cells. Based on similar arguments, for the horizonal pipelines, we have 2² feasible patterns since we have two rows. For the vertical pipelines, one can check that for each column we always have “UD” and “DU”, two patterns, where “U” and “D” denote that the pipeline is connected to the upper and bottom side, respectively.

In general, with n × m empty cells, the answer is 2(m + n). If there are several cells that are not empty, then the patterns of the row and column to which these cells belong in fact have been determined. Suppose that the number of rows and columns that are fully empty is totally t, and then the answer will be 2^t. Note that the previously filled cells might have already led to “leaking” states, and thus for this case the answer should be zero.