JOIN
 Match Editorial
2005 TopCoder Collegiate Challenge
Qualification Problem Set 2

January 11-12, 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 Problems

Hiking
Used as: Division One - Level One:
 Value 250 Submission Rate 154 / 171 (90.06%) Success Rate 134 / 154 (87.01%) High Score B_Carvalho for 247.53 points (2 mins 16 secs) Average Score 198.23 (for 134 correct submissions)

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:
 Value 1000 Submission Rate 112 / 171 (65.50%) Success Rate 40 / 112 (35.71%) High Score kalinov for 869.10 points (9 mins 6 secs) Average Score 596.83 (for 40 correct submissions)

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*(M-1)/2 inversions, with the maximum occurring when the suffix is in reverse order. When the desired number of inversions is of the form M*(M-1)/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*(M-1)/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*(M-1)/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 N-K to the front of the suffix and leave the rest in decreasing order. Altogether, the final permutation looks like

1...(N-M) (N-K) N...(N-K+1) (N-K-1)...(N-M+1)
where M is the smallest integer such that M*(M-1)/2 is greater than or equal to the desired number of inversions, and K is M*(M-1)/2 minus the desired number of inversions.

By vorthys
TopCoder Member