A. Second Order Statistics

This problem asks to find out the smallest element which is strictly larger than the minimum one. One simple way to solve this is to sort the array a[n] which stores the input data in an increasing order, and then find the first element that is different from a[0]. If such an element exists, then output this as the answer; otherwise output "NO" since all elements are exactly the same.

B. Bargaining Table

This is equivalent to finding out a rectangular which contains no '1's and has the largest perimeter at the same time. A trivial method is to check each feasible rectangular, i.e., enumerate the upper left point which takes O(mn) complexity and for each fixed upper left point, enumerate the bottom right point which takes O(mn) complexity as well, and finally check that whether this rectangular consists of only '0's or not, which takes O(mn) complexity. If it contains no '1's, then calculate the current perimeter and update the value of largest perimeter. Therefore, the total complexity is O(m^3n^3), which seems too slow...

The above solution can be improved by adopting a DP technique. We use an array a[x1][y1][x2][y2]=0 to denote that the rectangular with upper left point (x1,y1) and bottom right point (x2,y2) contains no '1's. Thus, a[x1][y1][x2][y2]=0 if a[x1][y1][x2-1][y2]=0, a[x1][y1][x2][y2-1]=0 and room[x2][y2]=0 all hold, where room[x2][y2] (just the input data) denotes the value '0' or '1' at point (x2,y2). Therefore, we can first compute a[x1][y1][x2][y2] for all the rectangulars, which takes O(m^2n^2) complexity. This can be done by starting with a[x1][y1][x1][y1] (just a point) and calculate the other values first column by column, then row by row, i.e., a[x1][y1][x1][y1+1], a[x1][y1][x1][y1+2],...a[x1][y1][x1+1][y1],a[x1][y1][x1+1][y1+1]... Note that when updating any arbitrary a[x1][y1][x1][y1], either a[x1][y1][x2-1][y2] or a[x1][y1][x2][y2-1] may not exist due to that x2-1 or y2-1 is out of index, and take care of this boundary case. After obtaining a[x1][y1][x2][y2], then we can enumerate the upper left point and bottom right point again and if a[x1][y1][x2][y2]=0, then we calculate the current perimeter which is equal to (x2-x1+1+y2-y1+1)*2 and compare this with the stored largest perimeter. The total complexity is O(m^2n^2).

C. System Administrator

First note that if m<n-1, then no connected graph can be constructed. Thus, m>=n-1 must be satisfied. The problem requires that if node v is deleted, then the previously connected graph is not connected anymore. Suppose that we first pick out node v, and then we seperate the left n-1 nodes into two parts so that any two nodes belonging to the same part can be directly connected to each other and to node v as well while any two nodes belonging to different parts can not be connected to each other directly. Denote the number of nodes in each part as x and y, and it is obvious that x+y=n-1. Furthermore, this division can 'consume' at most x*(x-1)/2+x+y*(y-1)/2+y edges. The formula x*(x-1)/2+x+y*(y-1)/2+y achieves the maximum value if we set x=1 and y=n-1-1, and suppose that the value is M after substituting. Now, we can say that if m>=n-1 && m<=M, then the answer is possible; otherwise impossible. We fisrt prove this conclusion. Suppose that m>M, and this actually implies that even if we set x=1 and y=n-1-1, where the y=n-1-1 nodes have been fully connected, there still exist some edges that are not used. Thus, we have to 'consume' the extra edges by connnecting the single node to some nodes belonging to this 'y=n-1-1 part'. As the 'y=n-1-1 part' is fully connected, it means that even if node v is deleted, the left 'x part' and 'y=n-1-1 part' are still connected.

Therefore, the answer for 'possible' or 'impossible' can be obtained by checking whether m>=n-1 && m<=M holds. Then, if this holds, then we can first connect the left n-1 nodes (except for node v) to node v, which 'consumes' n-1 edges (Note that this can always be done since m>=n-1 holds). Next, we can connnect arbitrary two nodes belonging to 'y=n-1-1 part' until the total number of 'consumed' edges is equal to m (This can always be done since m<=M). This can be done with O(m) complexity. For instance, we can use a vector to store the index of the y=n-1-1 nodes, and use two 'for' loops to enumerate the nodes that will be connected.

D. Segments

Suppose that all the segments have been drawn down explicitly along X-axis. Now we start from point -10000 and walk along the X-axis towards point 10000. Then, we will meet the first segment and denote it as [x1 y1], where x1 and y1 stand for its left end and right end (inclusive), respectively. It is obvious that at least one nail should be driven between the interval I=[x1 y1], since otherwise this segment can never be covered. We continue and might meet the second segment, which is denoted as [x2 y2]. If y2<y1, then one can see that if a nail between the interval I=[x2 y2] is driven down, both segments [x1 y1] and [x2 y2] can be covered simultaneously. If y2>y1, then a nail driven down between interval I=[x2 y1] can cover both segments [x1 y1] and [x2 y2] too.

One may have noticed that we should keep an interval I=[xi yi], and whenever we meet a new segment, we update the interval I by I=[x(i+1) min(yi, y(i+1) )]. The key idea behind this is that we want to always keep a feasbile interval between which all the met segments can be covered by just driving a single nail. Note that as we go along the X-axis, sometimes we might have I=[xi yi] with xi<=yi but I=[x(i+1) min(yi, y(i+1) )]=I(x(i+1) yi) with x(i+1)>yi. If this occurs, it implies that I=[xi yi] is the last feasible interval between which we can drive a nail to cover all the segments that have been met.

Thus, it is clear that the solution should be like this: we keep an interval I=[xi yi] and update it whenever we meet a new segment; if I=[xi yi] with xi<=yi but I=[x(i+1) min(yi, y(i+1) )]=I(x(i+1) yi) with x(i+1)>yi occurs, then we drive a nail at point yi and update the interval as I=[x(i+1) y(i+1)]. Specifically, the so-called "whenever we meet a new segment" can be done in this manner: we sort all the segments in an increasing order of xi, and if any two segments have the same xi, then they are sorted in an increasing order of yi; next we enumerate the segments one by one just as what "we start from point -10000 and walk along the X-axis towards to point 10000" describes, and update the interval I=[xi yi] and store the location yi where we drive down a nail while counting the number of used nails at the same time.

In fact, the above soluton is somewhat a greedy algorithm. We can prove that it will always achieve the optimal result (the smallest number of nails). The idea behind this proof is quite general when we try to prove the correctness of similar greedy algorithms, i.e., we assume that the optimal result different from the one found by greedy algorithm exists, and then we replace this "optimal" result by what is found by our greedy algorithm "little by little", while proving that the result is not degraded during this process. Then, the proof is completed by claiming a paradox since we have assumed that the optimal result is different from what is found by our greedy algorithm. Now, we give proof for this specific problem.

Proof: Suppose that the result found by our greedy algorithm is [g1,g2,...,gn], and the optimal result [b1,b2,...,bm] exists, i.e., m<n. Then, we walk along the X-axis from -10000 towards to 10000 again, and keep updating the interval I. Suppose that I=[xi yi] is the first interval that I=[x(i+1) yi] with x(i+1)>yi holds. Then, as indicated by our algorithm, all the segments that we have met before can be covered by driving a nail down at point yi, which gives g1=yi. Note that b1<=yi must be satisfied, since otherwise at least one segment with right end yi can never be covered. However, b1 can never be "better" than g1, since g1=yi can cover all the segments that have been met, and it is thus impossible for b1 to cover more segments. Therefore, if we replace b1 with g1, the modified result [g1,b2,..bm] can only be improved but not degraded! Next, we deal with b2. If b2<g1=yi, then it is obvious that b2 makes no sense since b1 is sufficient to cover all the previous segments and b2 can thus be deleted. This leads to a better result than the optimal one, and thus a paradox is found! If b2>g1=yi, then we can repeat what has been dealt with b1, and will end up with showing that b2 can also be replaced with g2 with no degradation. Finally, as m<n is assumed, it turns out that the optimal result can not cover all the segments, unless m>=n. Therefore, [g1,g2,...,gn] is the optimal result.

E. Scheme

This is somewhat quite intricate. The problem actually asks to build a strongly connected graph and thus we solve it by constructing a directed graph. First note that the out-degree of each node must be 1 while the in-degree can be any number. Then, if we start from a node with zero in-degree and implement a DFS (a linked list as a special DFS), it turns out that we will surely end up with a cycle. The proof is simple since if no cycle is met, then we can go along the directed edge and meet new nodes forever! However, there are only limited nodes, and this implies that we will always meet a node that has been visited before, which just forms a cycle.

A cycle is in fact a strongly connected component, and any node belonging to this component is equivalent when used to construct a strongly connected graph. Thus, all the nodes belonging to some strongly connected component can be reduced to any one of them. We implement this idea by the following algorithm: we start from a node s1 with zero in-degree and implement DFS until some node t1 is visited for the second time; then we store (s1,t1) as a pair. This (s1,t1) stands for a connected component but with only single direction, which is in fact a linked list, where s1 and ti denotes the starting node and ending node, respectively. For each node with zero in-degree, we can obtain its own (si,ti). Now, the solution might seem clear if we write them as (s1,t1),(s2,t2),...,(sn,tn). To build a strongly connected graph, we can add a link between ti and s( (i+1)%n ), which is equivalent to connecting several linked lists by adding links from head to tail.

One more thing to notice is that there might exist a strongly connected component, which can not be found out if we only take the nodes with zero in-degree into consideration. Therefore, after we have tried all the nodes with zero in-degree, we should check if there still exist some other nodes that have never been visited, and these nodes must form several (or a single one) independent strongly connected components. We can use a special (si,ti) with ti=si to denote such a component (actually a special linked list with only one node), and never forget to add such (si,ti).