Match Editorial

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

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;
    }

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)