A. You're Given a String...

The problem asks to find out such a substring that has the longest length and occurs at least two times, which is in fact equivalent to looking for two substrings (they might overlap with each other) with the longest length while they are exactly the same with each other. The solution might be simplified if one has noticed that the string consists of lower-case Lattin letters merely, i.e., a,b,...,z. The idea behind the simplification is that if two substrings are exactly the same, then their first letters must be the same as well. Thus, we can first use 26 arrays to store the positions at which each letter appears. For instance, we can assign 26 vectors (in C++ STL) for each letter, and "puch_back" the corresponding index. This can be done by traversing the string for a single time, with complexity O(N) (we use N to denote the length of string).

For each vector, we enumerate all the feasible combination of two indices (or positions), and start with these two positions and check their next one single letter at the same time. It is obvious that we will obtain two substrings and as we should keep them exactly the same, we must stop if the next one single letter of each substring is different. For instance, suppose that letter "a" has positions {1,5,7}. Then, we should check {1,5}, {1,7} and {5,7}. We adopt {1,7} as an example, i.e., we should check whether the two substrings {s[1],s[2]} and {s[7],s[8]} are the same or not. If they are the same, then we move on to check {s[1],s[2],s[3]} and {s[7],s[8],s[9]}; otherwise, we stop and store the current length. Finally, we output the maximum length as the answer.

Now, we calculate the complexity of the above solution. We denote the length of the 26 vectors as x1,x2,...,x26. For each vector, we should check xi*(xi-1)/2 combinations. For each combination, we will check at most 2N letters. Thus, the total complexity is {x1*(x1-1)/2+x2*(x2-1)/2+...+x26*(x26-1)/2}*2*N=O(N^3).

B. Party

Well, this problem is somewhat marvellous...

We first prove that the answer cannot be n. Note that each person can only have friends with number of 0,1,...,n-1. Therefore, when we count from 0 to n-1, some of them must leave.

Next, we prove that the answer cannot be n-1. Suppose that the person leaves when we count at x. This means that for the "stayed" n-1 people, the number of friends is reduced by one for x of them while nothing changes for the other n-1-x people. Due to similar reasons at the first case, the n-1-x people cannot all stay at the party, which is contradictory to our initial assumption. However, this can be true if and only if n-1-x=0, which gives x=n-1, i.e., the single person leaves when we count at n-1. This implies that the other n-1 people all have friends with number of n-1, since none of them leaves when we count from 0 to n-2. Nevertheless, this also means that when we count at n-1, all the n people will leave, which is contraditory to the initial assumption again.

Thirdly, we prove that the answer is n-2. Actually, the above two cases may have inspired us a little. Note that when some people leave when we count at x, the number of friends may be reduced by one for some of the "stayed" people, and it is just these people that have chances to survive until the end while for the other "unchanged" (number of their friends) people, they cannot all survive due to similar reasons at the first case. The reason is that: the "changed" people might have friends no more than x after some people leave, and as we count from x+1 to n-1, they will never leave. In a word, we should find out the minimum number of people that are "sacrificed" to protect the other people to survive till the end.

Here is one feasible construction. We let the two persons have friends with number of n-2 while the other n-2 people have friends with number of n-1. Then, when we count from 0 to n-3, all people stay at the party while when counting at n-2, the two persons leave and the currently "stayed" n-2 people have friends with number of n-1-1. When we count at n-1, the previously "survived" people continue to survive.

Finally, my question is: how could the first person come up with such a solution....I think it is more difficult to analyze this problem without any prior knowledge than to figure out the reasons and logics if I have been told that the answer is n-2. The above solution seems to be some "exclusive" method, but how to realize that I should try from n,n-1,n-2 other than 0,1,...

C. Oranges and Apples

To be continued...