A. What is for dinner?

The problem in fact asks to find out the minimum number in each row. As the number of rows is not quite large, less than 1000, we can adopt an array to record the minimum integer in each row, i.e., whenever a new integer is added to some row, we compare it with the previously stored integer and update the entry with the smaller one. Finally, we add up the minimum integer in each row together, and obtain the possibly "maximum amount of crucians". By comparing it with k, we select the smaller one as the output.

B. String Problem

Well, I got stuck in this problem for a quite long time, until I realized that not only can we change letter A into B or B into A, but also we can change both A and B into some other letter C, which may achieve a smaller sum of money...

This problem can be solved based on graph, where a letter is viewed as a node. The solution can be summarized as the following several steps:

1) Whenever a possible changing from letter A to B is provided, we can build a directed edge from A to B with the money as the cost; as more than one directed edge from A to B might be provided, we should only store the one with minimum cost to avoid multiple edges between any two nodes;

2) Implement the famous "Floyd-Algorithm" to calculate the shortest path between any two nodes; here is a simple example; suppose that letter 'a' can be changed into 'b' with cost 2 while 'b' can be changed into 'c' with cost 1; then 'a' can be changed into 'c' with cost 3, which can be updated by floyd-algorithm;

3) Compare each letter in string s1 with that in string s2; whenever they are different, enumerate every feasible changing, i.e., from letter 'a' to 'z', and select the one with the minimum cost as the common letter into which both letters should be changed.

C. Wonderful Randomized Sum

At first, we consider what form will the optimal option have. In fact, we can prove that the optimal prefix and suffix should not intersect with each other, since if they do, the integers belonging to the intersection will be multiplied by -1 for two times, which just gives their original values, and this results in a new prefix and suffix which do not intersect with each other at all. Therefore, the optimal prefix and suffix should not intersect.

Inspired by the above arguments, we can immediately come up with a straightforward method that enumerates the ending position of prefix and starting position of suffix, and find out the optimal one. However, this takes O(n^2) complexity, and it will almost surely lead to a Time-Limited-Error. To avoid this, we can try to reduce the number of enumeration, which actually turns out to work successfully by only enumerating the starting position of suffix. For each starting position of suffix, the original problem is equivalent to finding out the optimal prefix, which can be computed previously. The optimal prefix is in fact the one which has the minimum sum, since by multiplying -1 it turns out to be the maximum sum. However, this conclusion holds only if the minimum sum is less than 0, i.e., if no sum of prefix is less than 0, the optimal prefix is just empty.

Suppose that we use prefix[n] to denote the sum of a[0]+a[1]+...+a[n], which can be computed with complexity O(n) by using prefix[n]=prefix[n-1]+a[n]. Then, we use min_prefix[n] to denote the minimum sum of some prefix with ending position before n or at n. The initialization can be implemented by min_prefix[0]=min{a[0], 0}, and generally we have min_prefix[n]= min {prefix[n], min_prefix[n-1]}. Moreover, we use suffix[j] to denote the sum of a[n]+a[n-1]+...a[n-j], which can be calculated with complexity O(n) in a similar manner as computing prefix[n].

Now, we are ready to solve the problem. For each starting position j of suffix, the current maximum sum is just (prefix[n]-suffix[j]-min_prefix[j-1]) + (-min_prefix[j-1]) + (-suffix[j]). The maximum sum obtained during the enumeration of j serves as the final answer, which takes O(n) complexity.

D. Knights

This problem turns out to be not quite difficult if we have realized that it in fact asks to compute the total number of distinguishing circles that encircle the given two points.

At first, we sort the circles in an increasing order of their radiuses with complexity O(mlogm). Then, for each point, we calculate the number of circles that encircle it with complexity O(nm). Finally, we count the number of different circles that encircle the requested two points with complexity O(km). Thus, the total complexity is O(km). (I have hearded of an offline Tarjan' algorithm which can be used to solve this problem, also known as Lowest-Common-Ancestor problem)