A. IQ test

For a given array consisting of positive integers, the problem asks to find out the unique number which is different from all the other ones after implementing modulo-2 operations. We can count the number of odd integer and even integer as num_o and num_e, respectively, while storing any arbitrary positions at which an odd number and an even number appear. As the "unique" number only appears one single time, we can find out num_o==1 or num_e==1, and output the stored positions as the answer.

B. Phone numbers

This problem can be solved through a classification based on the value of n modulo 3, which contains the following cases:

1) n%3==0; the phone number can be seperated into groups of 3 digits;

2) n%3==1; we can seperate the first 4 digits into 2 groups of 2 digits, while the following digits can be seperated into groups of 3 digits;

3) n%3==2; the first 2 digits of the phone number is output, and the following digits can be seperated into groups of 3 digits

C. Roads in Berland

The solution is similar to the famous Floyd Algorithm. For two given cities S and T, let us consider how their minimum distance can be altered if a new road between A and B is built. We can imagine that there is a map which describes the roads between each pair of cities (if they exist), although this map is not explicitly known or given. For any given route from S to T, if this route does not use the newly built road betwwen A and B, the minimum distance between S and T stays the same, since nothing changes. Thus, the minimum distance might be updated if and only if the newly built road betwwen A and B is used. Then, the distance between S and T, d_m[S,T] can be divided into three independent parts, S to A, A to B and B to T. Note that according to the Minimum-Distance-Table, the minimum distance between S and T is d_m[S,A]+d_new[A,B]+d_m[B,T] for the current route, where d_new[A,B] denotes the length of the newly built road between A and B. Be careful that there is another feasible route which uses the newly built road as follows: S to B, B to A and A to T, which contributes a distance of d_m[S,B]+d_new[B,A]+d_m[A,T].

Finally, we should also notice that the newly built road may be "farther" then the old one. Therefore, the minimum distance between S and T should be d_m[S,T]=MIN{d_m[S,T], d_m[S,A]+d_new[A,B]+d_m[B,T], d_m[S,B]+d_new[B,A]+d_m[A,T]}. We have to implement the above operations for every pair of cities, which gives complexity O(n^2). As K roads are newly built, the total complexity is O(n^2*k). A last question to consider is the range of the final answer. Let us construct a worst case. Suppose that the cities form a linked list, where each node has exactly one single father node (except for the head node) and one child node (except for the tail node). Then, the largest answer can be

1000*(n*(n-1)/2+(n-1)*(n-2)/2+...+2*1/2)=1000/2*( (n-1)^2+(n-1)+(n-2)^2+(n-2)+...+1^1+1 )=1000/2*n*(n-1)*(n+1)/3>2^32 (choosing n=1000). Therefore, we should adopt the "long long int" type to compute the final answer.

D. Roads not only in Berland

I think perhaps I have used a little bit complicated method. One can refer to Union-Find (I am not sure of this terminology) for another simpler solution.

I adopt DFS (depth first search) for this problem. During DFS, when wemeet a node that has been visited, it means that this edge (might be referred to as backward edge) is not necessary to keep the current component connected, and thus this edge can be removed. However, there are seceral details that should be considered (all the following arguments are based on DFS).

1) Suppose that node A is the parent node of node B, and node B is the currently processed node. As the edge is not directed, node A will be visited again, but we cannot say that this edge is not necessary. The edge is not necessary if and only if the following two conditions are satisfied: a) a node that has been visited is met; b) this node is not the parent node of the currently processed node;

2) Any backward edge may be visited twice. Thus, they should be stored only once when it is visited for the first time;

3) As the graph may consist of several connnected components, it is likely to implement the DFS for several times. Whenever a new DFS is implemented, we can select any one single node belonging to this component as the "delegate";

4) Store all the backward edges and all the "delegates". The final answer is: remove all the backward edges and build new edges to connect every connected-component.