A. Ultra-Fast Mathematician

This is a simple problem, and the result can be obtained by implementing "Xor" operations to the given two sequences. The "Xor" operation is also referred to as "mod-2 sum", which has been widely used in channel coding theory. In channel coding theory, for any two codewords c1 and c2, which both consist of only 0 and 1, the result of "c1 Xor c2" is referred to as the Hamming Distance between c1 and c2, and this distance in fact describes the capability to tell one of them from the other one.

B. Hard Work

This problem is really a "hard work"... At first, for the given three initial strings, we should delete all the signs since they do not affect the results, and then we should generate all the 3!=6 possible concatenations. Next, for the students' strings, we first delete all the signs as well, and then compare it with every one of the 6 concatenations. If it is equal to any one of the 6 concatenations, the answer is "ACC"; otherwise it should be "WA". Note that the uppercase and lowercase letters should be omitted during the comparison.

C. Capture Valerian

As the given integer c is in base a, we should first convert it back into an integer in base 10. If b is also an integer, the left task is just to convert c into an integer in base b and output the result. It turns out to be a little complicated if b is 'R'. For this case, we deal with the digit in a (the given integer) from the least significant digit to the most significant one. For each digit, denoted as D, it should be converted into Roman forms according to the following 5 cases.

1) D=1,2,3: repeat the corresponding symbols in Roman forms for D times;

2) D=4: this has a unique Roman form;

3) D=5: this has a unique Roman form;

4) D=6,7,8: first write down the Roman form of '5', and then repeat the corresponding symbols for D-5 times;

5) D=9: this has a unique Roman form.

Note that when we deal with the above cases, the position of the digit matters as well. For instance, a=xxxD, and we are dealing with D, then the "corresponding" symbols can only be 'I' and 'V'. For a=xxDx, the related symbols are 'X' and 'L'.

D. Eternal Victory

The hint is that "He can finish his travels in any city". Suppose that we are now at node-1, and node-1 has three child nodes, node-2,3,4. Without loss of generality, we visit the child nodes just in the natural order. We first move to visit node-2, and to visit node-3, we have to come back from node-2 to node-1. This means that the edge between node-1 and node-2 has been used twice. Furthermore, if node-2 has child nodes as well, by some simple induction, we can see that all the edges have to be visited for at least twice. However, when we finally visit node-4, it is sufficient to use the edge between node-1 and node-4 only once since "He can finish his travels in any city", which implies that "He does not have to come back to node-1 again".

With the above arguments, it can be seen that we will finally arrive at some leaf node, and finish the travel at that leaf node. Therefore, only the edges from the root node-1 to this special leaf node are used once while the other ones have been used at least twice. Thus, it suffices to find out the farthest leaf node from the root node-1, and the answer is just 2*sum(E[i])-D_max, where E[i] denotes the length of the i-th edge, and sum(E[i]) denotes the total length of all the edges while D_max denotes the maximum distance from node-1 to some leaf node.

E. Enemy is weak

This is really a nice problem to practice Segment Tree techniques as far as I consider...One can search on the internet and will find a lot of information about Segment Tree techniques. Thus, I will not give the details but only how I understand it, and when we should use it based on my own understanding.

We first give a trivial solution which has complexity O(N^2). We enumerate the integers in the given order, and adopt a hash table to record the integers that have been visited. When we are visiting a[i], we should find out the number of integers such that a[k]>a[i] with k<i, denoted as Head[i], and also the number of integers such that a[i]>a[j] with i<j, denoted as Tail[i]. It can be seen that the required answer is just Head[0]*Tail[0]+Head[1]*Tail[1]+...Head[n-1]*Tail[n-1]. To find out Head[i], we just query the hash table to count the number of recorded integers that are larger than a[i]. To find out Tail[i], we can enumerate the integers in a reversal order, and adopt another hash table. When we are visiting a[i] (note that reversal order), similarly we query the hash table but should find out the number of stored integers which are less than a[i].

However, the above solution has complexity O(N^2). Specifically, the first "N" comes from the enumeration of array a[n], which cannot be avoided. The second "N" comes from the query of hash table, which can be reduced to logN by using the Segment Tree technique. The trick is that when we try to count the number of stored integers which are larger (or less) than a[i], it is equivalent to adding all the "flags" and the sum is just the answer (for instance, we set flag=1 to denote that some integer has been visited while flag=0 means that it has not been visited), and Segment Tree technique can reduce the complexity of computing the sum to O(logN). Therefore, whenever we are using hash table to store the integers that we have visited, and we have to frequently query the hash table to find out the total number of some special integers, it is perhaps the right time to use Segment Tree technique.

Finally, one might have noticed that in many problems, often the range of integers is quite large compared with the total number of elements. To alleviate this dilemma, we can map the elements to a "new" but "small" range, and I think one can also find a lot of information about this step on the internet, which might be referred to as discretization.