65A - Harry Potter and Three Spells

One should be very careful of this problem...If a*c*e<b*d*f, it is obvious that we can obtain infinite gold. Besides, if c=0 and d>0, it implies that we can obtain infinite gold as well. Next, if a=0 but all of b, c and d are not 0, we can still obtain infinite gold since we can first obtain infinite lead and thus convert all of them to gold.

65B - Harry Potter and the History of Magic

This problem can be solved by adopting a greedy algorithm. We first introduce a variable Y which is initialized with value 1000, i.e., the minimum year that meets the requirements. Then, we enumerate the input integers in the given order. For each integer, we start with the current Y, and increase Y by 1 until it reaches 2011. During this process, we check whether we can convert this integer into Y by changing no more than one digit. If the answer is yes, we can immediately stop the loop and just replace this integer with the current value of Y, and store the current Y for the next loop which deals with the next integer; otherwise it means that there is no solution.

65C - Harry Potter and the Golden Snitch

This is a nice problem for practicing binary search as far as I consider. We can use binary search to search for the earliest time when they will meet. As the search is based on "float types", it is better to limit the times of search to terminate the loop rather than adopting a small constant like /epsilon to check whether the answer has converged.

At first we set t_l=0 and t_r to be some sufficiently large value. Then, for each loop we will check whether they can meet at time t_m=(t_l+t_r)/2 or not. With this t_m, we can first calculate the ranges that the player can reach, which turns out to be a circle. Therefore, the left work is to calculate the position of the ball at time t_m, and check whether it falls inside the circle or not. If it is inside the circle, it means that they can meet at some earlier time, and thus we should set t_r=t_m for the next search; otherwise we should set t_l=t_m. At time t_m, we can first compute the total distance that the ball has moved, and then we can find out the segment at which the ball will appear. With this result, we can further calculate the exact position (x,y,z) of the ball, and thus determine whether the ball is inside the circle or not.

65D - Harry Potter and the Sorting Hat

A straightforward solution is to enumerate all the possible final patterns, and thus find out the houses that one can select. This process can be simulated by building a tree, and each node denotes the current pattern while each branch denotes the letter given in the string. However, we might run into a severer situation due to the huge expansion of the tree. To alleviate this problem, we can adopt set< > in C++ STL, since some patterns are the same in the trees. As a simple example, suppose that we first meet ????. It can be seen that no matter what the intermediate states can be, they will finally reach the state (GHRS). As set< > produces an efficient way to delete the duplicate states, the total number of states that we have to visit can be significantly reduced.