A. Bar

If the current input is a number, i.e., the age, then it suffices to check whether this is not younger than 18 or not. If the current input is the name of some drink, then it is sufficient to check whether this belongs to the list of alcohol drinks or not.

B. Spoilt Permutation

We can adopt two pointers p1 and p2, which start at the first position and the last position, respectively. Then, we move p1 to the right until we meet an element which is not equal to its index. Similarlt, we move p2 to the left and find the first element that is not equal to its index. It is obvious that if p1>=p2, then the answer should be "0 0"; otherwise we should further check that whether each element a[j], where p1<=j<=p2, will satisfy the condition

a[j]=p2-(j-p1)

If for all the elements from p1 to p2, inclusively, the above equation hold, the answer will be "p1 p2"; otherwise it is "0 0".

C. Corporation Mail

At first sight, this problem might seem a little complicated. Nevertheless, it can be solved by using "stack" in a simple and straightforward manner. It is convenient to use the "vector" to simulate the "stack" (also you can directly use the "stack").

Starting from the first character, whenever a name is found, we search the vector and whenever we find a string that is the same as the name, we add the answer by 1. Then, we also push the name into the vector (push_back). Next, whenever we meet a '.', the last string (or name) in the vector is taken out (pop_back).

D. Changing a String

This is well known as "Edit Distance" problem as far as I consider. One can search on the Internet and will find a lot of useful information.

E. Domino Principle

For each domino, denoted as D[i], we assign it with four parameters, position D[i].x, height D[i].h, original index D[i].idx and the index of the most right domino that it can hit, denoted as D[i].nidx. Note that here "hit" does not mean that the current domino must hit it directly. Instead, just as domino implies, we say that it can hit another domino if we push it to the right, this domino will fall down finally.

At first, we sort the dominoes in an increasing order of their positions, and then deal with the dominoes from right to left one by one. Suppose that we are now arriving at the i-th domino. Then, we start from the (i+1)-th domino and check whether the i-th domino can hit it or not. This is straightforward by checking if D[i+1].x falls into the interval [D[i].x+1, D[i].x+D[i].h-1]. If the answer is NO, it means that D[i].idx=i, i.e., this domino can only "hit" itself. Otherwise, we further whether the i-th domino can hit that one with index D[i+1].nidx+1. The reason is that since we can hit the (i+1)-th domino, and if it falls down, D[i+1].nidx implies that the (D[i+1].nidx)-th domino will also fall down. Thus, we can directly skip to the (D[i+1].nidx+1)-th domino and check whether it can be hit or not, and repeat the above operations. During this whole process, we can update and store the number of dominoes that every domino can "hit".

The complexity can be calculated by using the "Amortized Analysis" technique. Note that checking whether some domino can hit another one on the right contributes to the total complexity, and thus we count the number of such "checking". When "checking" occurs, if the answer is YES, i.e., it can hit another one on the right, we assign this "checking" to the right one which can be hit and denote this event as Type-1; otherwise, we assign this "checking" to the current domino and denote this event as Type-2. Now we prove that for each domino, both Type-1 and Type-2 event can occur for at most once. Therefore, the total complexity is O(N).

Proof: Suppose that the (i+1)-th domino is checked whether it can be hit by the i-th domino or not. If the answer is YES, then Type-1 event occurs at the (i+1)-th domino. Note that Type-1 event will never occur at the (i+1)-th domino any more, since when we later visit the (i-1)-th domino, we will compare it with the i-th domino while the (i+1)-th domino will be skipped (the reason is that if the i-th domino can be hit, then the (i+1)-th domino can be hit as well). Similarly, if the answer is NO, Type-1 event occurs at the i-th domino, however this Type-1 event will never occur at the i-th domino, either, according to the our definition.

An intuitive understanding of "Amortized Analysis" is that the same operation is amortized, or separately counted, and finally added together.