A. Next Test

As the range of input size is only up to 3000, we can maintain an array to indicate which number has appeared in the given test. Then, we enumerate this array from index 1 to n, and the first number that cannot be found is the answer.

B. Tournament

It seems that there exist some other simpler methods than mine... The key idea of my solution is to build a directed graph. The players can be viewed as nodes in a directed graph, and node A has en edge directed to node B if we can find a match in which A wins against B. Then, we can maintain an array to count the number of matches that a player has participated in. It is straightforward that we will find out two players who have only participated in n-2 matches while the other ones all have participated in n-1 matches. After finding out the two players, without of loss generality, we denote them as A and B, and then we implement "graph traversal" for two times witht the starting point as A and B, respectively. If we can reach node B from node A, then it means that A wins against B, or if we can reach node A from node B, it implies that B wins against A. However, we might arrive at the third case where we cannot reach B from A or reach A from B, either. For this case, it means that we cannot tell who wins against whom based on the results of provided matches, and we can select any result as the answer.

C. Unordered Subsequence

It is easy to find out that if unordered subsequence exists, the shortest length should always be 3. Assuming that the shortest length should be some integer larger than 3, without loss of generality, we write the subsequence as x[1],x[2],...x[m], where m>3. Now, let us focus on the first three elements. Their relationship can only be x[1]>x[2] && x[2]<[3], or x[1]<x[2] && x[2]>x[3], since otherwise we can achieve a shorter length by deleting x[1]. However, this in fact has indicated that the shortest length is 3 since it is enough to keep x[1], x[2] and x[3] only while deleting all the following elements. For the following arguments, we denote the three indices as 'left', 'middle' and 'right', which should be initialized as '-1'.

Now, we can first enumerate the sequence and when we find that the next number is larger or smaller than the current one, we stop and adopt a 'flag' to indicate which case it belongs to. For instace, if a[i+1]>a[i], we denote flag=1 while if a[i+1]<a[i], we set flag=-1. Next, we enumerate the sequence from the first element again, and we have the following cases.

1) a[i+1]>a[i], if flag==1, then we can set left=i and middle=i+1; otherwise, we set middle=i and right=i+1 and stop the enumeration;

2) a[i+1]<a[i], if flag==1, then we set middle=i and right=i+1 and cease the enumeration; otherwise we set left=i and middle=i+1.

Finally, we check whether all 'left', 'middle' and 'right' have been given reasonable values, if it is, output them as the answer; otherwise we can conclude that no such unordered subsequence exists.

D. Ring Road 2

I think this is well known as the "2-sat" problem. I hope that the following arguments can serve a general method to solve such problems.

At first, for two given roads, we need to judge whether they are mutual exclusive, i.e., if they have to be built as 'io' or 'oi', they are mutual exclusive. For instance, for roads [4,6] and [1,5], they are mutual exclusive, and we cannot build both of them inside or outsied the ring. Without loss of generality, we denote any two roads as [a1,b1] and [a2,b2]. It is obvious that if they have common ends (a1==a2 || a1==b2 || b1==a2 || b1==b2), they are not mutual exclusive; otherwise, we can enumerate from a2 to b2 and if we can meet exactly one single end belonging to road [a1,b1], then they are mutual exclusive. Be careful that this enumeration should be done by implementing 'module operation' based on the number of cities 'n', so that it does not matter even if a2>b2. It is important to notice that when we obtain '0' during the 'module operation', it in fact means that we have reached position 'n', which should be handled specifically.

Then, for every road, we find out its mutual exclusive roads, which can be done with complexity O(m^2). We can build an adjacent matrix E[m][m] to store the results and thus establish a graph, for instance, if road A is mutual exclusive with road B, then E[A][B]=E[B][A]=1. Next, we implement breadth frist search (BFS) based on this graph, and when we meet a new node, set it as 'o' if its parent node is 'i' and vice versa. The root node is free to choose 'i' or 'o' (it can be proved that this will not affect the final answer). After all the nodes (or roads) in the graph have been visited, they are exactly divided into two groups with type 'i' and 'o'. The left thing to do is to check again whether there are any two roads that are mutual exclusive in one single group.

The above arguments can be summarized as the following steps:

1. find out a method to judge whether two nodes are mutual exclusive;

2. build a graph, and the edge means a mutual exclusive relationship between two nodes;

3. implement BFS and guarantee that all the nodes have been visited, while dividing the nodes into two groups;

4. for each group, check that whether there are mutual exclusive nodes

E. Number With The Given Amount Of Divisors

A little difficule problem for me...

At first, we should figure out how to compute the number of divisors for some given integer N. According to the Fundamental Theorem of Arithmetic, N can be uniquely written as N=(p1^n1)*(p2^n2)*..., where pi is a prime number. For any divisor of N, it must be some combination of p1, p2,.... Therefore, the total number of divisors can be calculated as n=(n1+1)*(n2+1)*...

The problem asks to find the minimum number which has exact n divisors, where n takes values from [1,1000]. As ni=0 means that N does not have a prime divisor pi, we only consider those prime divisors which has ni>=1. Thus, ni+1>=2, and it can be observed (n1+1)*(n2+1)*...(n10+1)>=1024>1000. This implies that it is sufficient to consider only the first ten prime divisors, i.e., {2,3,5,7,11, 13,17,19,23,29}.

With the above arguments, we can adopt Dynamic Programming to solve the problem. Let us use dp[i][j] to denote the minimum number which has exactly n divisors and the first j prime divisors, where i>=1 and j>=1 to simplify the description. Note that "has exactly the first j prime divisors" means that n1, n2,...nj should all take values that are larger than zero. Now we try to figure out how to calculate dp[i][j]. In fact, dp[i][j] can be uniquely determined based on dp[1][j-1], dp[2][j-1],...dp[1000][j-1]. The reason can be clearly seen through the following simple example. Assuming that N=(2^4)*(3^2)*(7^2) is the minimum number which has (4+1)*(2+1)*(2+1) divisors, nevertheless, this is incorrect sine we can immediately find a smaller N'=(2^4)*(3^2)*(5^2). This example implies that the prime divisors cannot "jump" but "show up" exactly one by one.

Therefore, once dp[1][j-1], dp[2][j-1],...dp[1000][j-1] are determined, dp[i][j] has already been determined as well. Thus, we can calculate dp[i][j] from every one of dp[1][j-1], dp[2][j-1],...dp[1000][j-1], and find the minimum one as the final answer. For dp[r][j-1], if r is a divisor of i and i/r-1>0, then we can obtain a reasonable dp[i][j] from dp[r][j-1], i.e., dp[i][j]=dp[r][j-1]*(p[j])^(i/r-1), where p[1]=2, p[2]=3, p[3]=5,...,p[10]=29. By enumerating all the feasible dp[r][j-1], we can find the minimum one and update dp[i][j] by this minimum number. However, the term (p[j])^(i/r-1) is likely to take a very large value. As the question ensures that the answer will not exceed 10^18, we can implement the multiplication step by step, i.e., whenever we find an appropriate dp[r][j-1], we start from dp[r][j-1]*(p[j])^(1), then dp[r][j-1]*(p[j])^(2), then dp[r][j-1]*(p[j])^(3), and so on, and if some dp[r][j-1]*(p[j])^(k)>10^18, we can immediately terminate the calculation since this is definitely not the answer. Finally, the initialization can be done by setting dp[r][1]=2^(r-1) (of course, the 10^18 limitation should be considered). As some dp[i][j] may not have a reasonable value, for instance, dp[2][2], which is at least 2^1*3^1 and thus have at least 4 divisors. For simplicity, we can assign -1 to such positions.

Now, the problem is equivalent to finding the minimum number among dp[n][1], dp[n][2],...dp[n][10], which serves as the final answer.