Qualification Problem Set 2 January 1112, 2005 Summary This set was of the "Think. Think. Think. Type." variety rather than the "Think. Type. Type. Type." variety. Both problems were easy to code once you figured out exactly what they were asking for. Congratulations to newcomer B_Carvalho and kalinov for blazing fast solutions to the easy and hard problems, respectively. The ProblemsHikingUsed as: Division One  Level One:
This problem arose out of a math puzzle in which you must show that, given appropriate conditions, a man who walks up a hill one day and down the hill the next day must at some point have been at exactly the same place on the trail at exactly the same time of day both going up and coming down. The trick is to imagine that he is two people hiking on the same day and to realize that the two hikers would inevitably meet somewhere on the trail. To code this, you first add up the total distance covered by one of the hikers to find the height of the hill. Then you iterate through the two lists, looking for the point at which the cumulative combined distance traveled by the two hikers equals or surpasses the height of the hill. The main loop looks like combined = 0; for (int i = 0; ; i++) { combined += alice[i] + bob[i]; if (combined > heightOfHill) return i; if (combined == heightOfHill) return i+1; }You don't need to worry about running off the end of one of the arrays because the hikers are guaranteed to meet by the time one of them finishes. Inversions Used as: Division One  Level Three:
To make the lexicographically earliest permutation, you want to leave the largest possible prefix unchanged. Put another way, you want to confine the changes to the smallest possible suffix. A suffix of size M has at most Choose(M,2) = M*(M1)/2 inversions, with the maximum occurring when the suffix is in reverse order. When the desired number of inversions is of the form M*(M1)/2, then the permutation consists of a prefix of consecutive numbers in increasing order, followed by a suffix of consecutive numbers in decreasing order, as in 1 2 3 4 5 9 8 7 6 The question is what happens when the number of inversions is not of the form M*(M1)/2. Rounding up to the next higher value of M tells us how many elements must be involved in the suffix, but the suffix will no longer be in strictly decreasing order. Consider the amount by which M*(M1)/2 exceeds the desired number of inversions. This is the number of inversions that we want to remove from the strictly decreasing suffix, and we want to do so in the way that brings the smallest possible value in the suffix to the front of the suffix. Suppose the suffix was 9 8 7 6 5 4. If we bring the 8 to the front but leave the rest in decreasing order (8 9 7 6 5 4), then we have removed one inversion. Similarly, if we bring the 7 to the front but leave the rest in decreasing order (7 9 8 6 5 4), then we have removed two inversions. In general, if we want to remove K inversions from the suffix, then we move element NK to the front of the suffix and leave the rest in decreasing order. Altogether, the final permutation looks like 1...(NM) (NK) N...(NK+1) (NK1)...(NM+1)where M is the smallest integer such that M*(M1)/2 is greater than or equal to the desired number of inversions, and K is M*(M1)/2 minus the desired number of inversions. 
