A. Domino piling

If at least one of M and N is an even number, then the answer will be m*n/2; otherwise exactly one square cannot be covered, and gives (m*n-1)/2 as the answer. Nevertheless, by using integer division, m*n/2 will give the correct result for both the case.

B. Choosing Symbol Pairs

For a given string, we should calculate how many times a character has appeared in it. If a character 'c' has appeared for a[c] times, then the answer is just the sum of a[c]*a[c] where all the characters that have appeared should be considered.

C. Happy Farm 5

At first, I chose to "scan" first from left to right, and then from right to left, and during this process, I tried to find out the convex hull and record its length. However, this kept failing even though I have tried a lot of times...

Finally, I studied the codes from the other coders, and found out that most of them had used a quite simple method. The main idea is to first draw two lines with -45 degree, and one of them should pass the most upper right point while the other one should pass the most bottom left point. Similarly, we draw another two lines with +45 degree, and let one of them pass the most upper left point while the other one pass the most bottom right point. These four lines will form a rectangular (this is not always true, for instance if only one point exists, however it does not affect the following results), and the answer is just the perimeter plus 4. This works from an intuitive understanding, however I cannot figure out how to prove that it always works.

D. Bombing

I think two programming techniques are involved in this problem.

1) For given N events and the probabilities that each of them occurs, how to calculate the probability that at least K of them occur? A direct enumeration might fail since C(N,K), which means the number of diffierent ways to choose K elements from N elements, turns out to be quite large even for N=100 and K=50. An efficient solution is to use Dynamic Programming to calculate the result. We use Pr[n][m] to denote the probability that among the n events, exactly m of them occur. One can check that this can be computed according to the recursion

Pr[n][m]=Pr[n-1][m-1]*p[n]+Pr[n-1][m]*(1-p[n])

where p[n] denotes the probability that the n-th event occurs. With this recursion, we can calculate Pr[i][j] for every feasible i and j. Then, the required result is Pr[N][K]+Pr[N][K+1]+...+Pr[N][N].

2) Binary serach with required precision. The problem asks to compute the minimum radius R which can meet the requirement. We can start with R1=0 and R2=4000, and then check Rm=(R1+R2)/2 and update the values for the next loop according to the current results. The frequently used termination condition in binary search, i.e., the value that we have found out is exactly equal to the target value, cannot work successfully if we are dealing with "float" number rather than "integer" number. Instead, we can limit the maximum number of implementing the binary search to achieve a similar effect. If we set the maximum number of binary search to T, then the total search space M has been divided into 2^T intervals and each of them has length M/(2^T). To achieve the precision requirement, for instance, an absolute inaccuracy less than some E, we can just choose an appropriate value of T which can satisfy that M/(2^T)<=E.

E. Square Equation Roots

At first, we write the roots as -b+sqrt(b^2-c) and -b-sqrt(b^2-c), and consider the conditions under which two different pairs (b1,c1) and (b2,c2) can have at least one same root. Suppose that -b1+sqrt(b1^2-c1) and -b2+sqrt(b2^2-c2) are the same. If both sqrt(b1^2-c1) and sqrt(b2^2-c2) are not rational numbers, then we must have b1=b2 and b1^2-c1=b2^2-c2, which gives that b1=b2 and c1=c2. Therefore, no different pairs of (b1,c1) and (b2,c2) can have at least one same root unless both sqrt(b1^2-c1) and sqrt(b2^2-c2) are rational numbers.

With the above arguments, for each b, any c that results in an irrational value of sqrt(b^2-c) will contribute two different roots, while for the other c, their roots will form two integer intervals as we will see later. Therefore, we can first implement a loop for b, and for each b, we adopt the following steps:

1) Compute the maximum value that c can take, i.e., c<=c_min=min(b^2,m);

2) Compute all the feasible c that can result in a rational value of sqrt(b^2-c); suppose that x^2=b^2-c, then c=b^2-x^2, and thus 1<=b^2-x^2<=c_min, which gives ceil{sqrt(b^2-c_min)}<=x<=b-1; if ceil{sqrt(b^2-c_min)}<=b-1, we will have num2=b-1-ceil{sqrt(b^2-c_min)}+1 values of c that leads to a rational value of sqrt(b^2-c);

3) For those values of c that lead to an irrational value of sqrt(b^2-c), they will contribute 2*(c_min-num2) different roots to the final answer; while for the other values of c, it can be seen that the roots are -b+x and -b-x, with x belonging to [ceil{sqrt(b^2-c_min)}, b-1]; for convience, we can add 2b to the original roots to "move" all the intervals to the right so that we can adopt a hash table to record the intervals; therefore, we have obtained two intervals [b+ceil{sqrt(b^2-c_min)}， b+b-1] and [b-(b-1), b-ceil{sqrt(b^2-c_min)}], which just give the corresponding roots;

4) As we can have at most 5000000 values of b, it will cost a huge complexity if we "map" each point of an interval into the hash table; instead, for some interval [S,T], we can just set H[S]++ and H[T+1]--, where H[ ] denotes the hash table; when all the intervals have been processed, we scan from the start of the hash table to the end and calculate the prefix sum; the number of non-zero prefix sum is just the number of different points that all the intervals can cover up; intuitively, H[S]++ means that a new interval has began at point S while H[T+1]-- implies that some interval has just terminated at point T+1; whenever the prefix sum is larger than zero, it means that the current point is still covered by at least one interval.