A. Translation

This is a simple problem. If the two strings have different length, then the answer must be "NO"; otherwise, we just reverse one of the strings and compare whether they are exactly the same or not.

B. Martian Dollar

A straightforward solution is to first enumerate the days when to sell, and for the i-th day, enumerate all days from the first one to the i-th one and find out the j-th day when one can buy with the cheapest price, where 1=<j<=i. Then, the money will be b%a[j]+b/a[j]*a[i], where "x/y" means "integer division". Finally, we output the maximum value as the answer. This solution has complexity O(N^2). However, we can further reduce it to O(N). The idea is to build another array p[N], where p[i] denotes the minimum value of a[0],a[1],...,a[i]. p[0] is initialized as p[0]=a[0], while p[i] can be computed as p[i]=min(a[i],p[i-1]), which takes O(N) complexity. Thus, if we sell on the i-th day, the money will be b%a[i]+b/p[i]*a[i], and the maximum one is just the answer. The total complexity will be O(N).

C. Email address

A feasible solution consists of the following steps:

1) change all the "dot" into '.';

2) change all the "at" into '@';

3) if the first or the last character is '.', then change it back to "dot"; while if the first or the last character is '@', change it back to "at" as well;

4) if there exists any other '@', change all of them back to 'at' except for the first one.

D. Pawn

A nice DP problem for a competitive programming beginner like me.

We use an array F[n][m][k+1] to implement the DP algorithm, where F[r][c][z] denotes the maximum value one can obtain in the r-th row and c-th column while the remainder divided by k+1 is z. Suppose that another array b[r][c] denotes the number of peas initially given in the r-th row and c-th column. Then,

F[r][c][z]=max(F[r-1][c-1][z-b[r][c]%(k+1)], F[r-1][c+1][z-b[r][c]%(k+1)]).

Remember to check whether the position (r-1,c-1) or (r-1,c+1) is a reasonable one or not. One should also note that if z-b[r][c]%(k+1) turns out to be a negative integer, modify it as z-b[r][c]%(k+1)+k+1. Once we have completed filling every cell of F[n][m][k+1] with a reasonable value, we can obtain the answer by finding out the maximum one of F[1][c][0], where c=1,2,...,m. Furthermore, we should adopt another array S[n][m][k+1] to store the steps by which we can reach the maximum value. The value of S[r][c][z] can immediately be computed when we update F[r][c][z], i.e.,

if F[r-1][c-1][z-b[r][c]%(k+1)]>F[r-1][c+1][z-b[r][c]%(k+1)], then S[r][c][z]=c-1;

if F[r-1][c-1][z-b[r][c]%(k+1)]<=F[r-1][c+1][z-b[r][c]%(k+1)], then S[r][c][z]=c+1.

When we trace back the steps, we can start from the first row, i.e., S[1][max_c][0], where max_c denotes the column in which we obtain the answer, and if S[1][max_c][0]=c-1, we move to S[2][max_c-1][0-b[1][max_c]%(k+1)]; otherwise we go to S[2][max_c+1][0-b[1][max_c]%(k+1)]. Similarly, if 0-b[1][max_c]%(k+1)<0, we just modify it by 0-b[1][max_c]%(k+1)+k+1.

E. 3-cycles

A famous problem in graph theory, and the solution is referred to as Turan's theorem. The original problem investigated by Turan's theorem is a more general one, which gives n points and asks what is the maximum number of edges one can connect while under the condition that the graph is (r+1)-cycle free. One can search on the internet to find some details about this problem. For this special one, the answer is just (n/2)*(n-n/2) with "/" meaning "integer division".