Problem A: Object Clustering

The problem is the same as to find the N-K smallest edge in the MST. As there are 10000 points, it is impossible even to calculate the length of all edges(10000 × 10000). But we shall see there are many edges that are impossible to be in the MST: if d_ij = d_ik + d_kj, then (i,j) won't be in the tree. Then the number of edges is at most 500*2*10000, but in fact the number is much smaller. Use a simple DP or a good enum can rule out these redundant calculation. Then we use a Kruskal algorithm to construct the tree and can just get the answer when we go to the (N-K)th edge in the MST.

Problem B: Matrix Multiplication

The author gives an approximate algorithm rather than a precise one. Randomize a n ×1 matrix X, test if the equation A × B × X = C × X holds true. If it is not true we can safely say "NO" to this problem. If it is true, the possibility that  A × B ≠ X is extremely little.

Problem C: Dragon Slayer Qualification Exam

You may notice two important things in this problem:

• Black/white rooks are independent from each other
• You can do 2^m brute search for red cells because m is small.

Problem D: Jessica's Reading Problem

For every page in the book, evaluate the shortest section starting from the page that covers all the ideas. A good data structure such as heap will reduce the time complexity thus meet the time limit.

Problem E: Apple Tree

If we label the forks with their DFS-visit-time, then a sub-tree is a consecutive interval of labels. Then we can use segment-tree to handle this problem.

Problem F: Roll Box I

There're three states for the box on every cell, standing up, lying down towards right and lying down towards bottom. Therefore at most 500*500*3 states exists for the box so flood-fill  works.

Problem G: Roll Box II

Use any method to calculate a part of the plane, like [-10,10] × [-10,10]. You'll find some pattern hidden in it.

Problem H: Lucas-Lehmer Test

The solution idea is quite straightforward: evaluate the sequence {s_i} modulo M_p. In order to exploit the property of M_p being one less than a power of two, it is better to use binary in arbitrary precision arithmetic, which will simplify the process of taking modulo and conversion to hexadecimal.