Match summary

Delta Round 2 provided plenty of advancing slots for competitors. Just one room was enough for the competition, and the 20 competitors only needed a positive score to advance.

China brought the top four scorers to the match. ahyangyi, with the fastest submissions for all three problems and some extra points earned during challenge phase, won the match by a solid margin. Rounding out the top four were sunxiangtao, gooooodle and wintokk.

The Problems

FrequentPairs

Used as: Division One - Level One:

Value 250

Submission Rate 20 / 20 (100.00%)

Success Rate 17 / 20 (85.00%)

High Score ahyangyi for 247.64 points (2 mins 46 secs)

Average Score 225.40 (for 17 correct submissions)

The small number of words and their sizes made it possible to simply test for all possible pairs of letters in every position still under runtime restrictions, in about 26²*50²=1.7M iterations. It would be faster, however, to cycle through all word positions only once, counting the different letter combinations in a table. Keep in mind in any case that the order does not matter, so a single counter should be used for both "ab" and "ba," for example.

See tranquiliser's for an example of the simplest solution mentioned, and you can see how big the word set (or sizes) might grow before timing out. For the other type of solution (even if using strings and map as auxiliary tools), see gooooodle's -- and you can do the exercise of optimizing it without using maps as homework.

PipePatcher

Used as: Division One - Level Two:

Value 500

Submission Rate 19 / 20 (95.00%)

Success Rate 17 / 19 (89.47%)

High Score ahyangyi for 492.50 points (3 mins 31 secs)

Average Score 437.56 (for 17 correct submissions)

This problem also has a simple solution that doesn't require a complex algorithm, but only one strategy is optimal and quick to construct. Consider the leak positions ordered by distance the endpoint. To cover the first leak (which has to be done, at some moment) the most reasonable option is to put the L-inch tape in a way that it covers as many leaks as possible to the right. If this first leak was at position k, this will cover any leak up to position k+L-1, inclusive. There is no need to consider any more leaks up to that position. Following this strategy with the rest of the leaks will give an optimum way to choose where to put each tape.

Most successful solutions implemented exactly that with two nested loops. Refer for example to the fastest solution:

int patches(int L, vector  leaks) {
  int i, j, s;
  sort(leaks.begin(), leaks.end());
  s = 0;
  for (i = 0; i < leaks.size(); ) {
    s ++;
    j = i;
    while (leaks[i] - leaks[j] < L)
      i ++;
  }
  return s;
}

CalculatorDisplay

Used as: Division One - Level Three:

Value 1000

Submission Rate 17 / 20 (85.00%)

Success Rate 10 / 17 (58.82%)

High Score ahyangyi for 937.39 points (7 mins 26 secs)

Average Score 748.25 (for 10 correct submissions)

This problem was not about complex algorithms but was about paying attention to a few small details. Most coders submitted the problem, but about half of the solutions served as targets for the challenge round.

Some simple steps plus testing for some different border cases would solve it. First, let's forget about floating point numbers and do the division in small integers with the help of strings, as you used to do with paper and pencil in the old school days: take digits from left to right, divide and keep each remainder for the next step.

Compute all the integer and fractional digits if possible, or stop once you are past the number available in the display -- in such a case you already know the result does not fit, so you can return "E." If the number is less than zero, do as the calculator does and discard that leading "0" in the integer part. Also, if the number is an integer, do not include the decimal point in the result.

Finally concat the integer and fractional parts you obtained (which should not have extra zeros) and check if it fits in the display. Remember to not count the decimal point as occupying a position. If that result fits in the number of digits in the display, return it -- or return "E" otherwise.

Refer to ahyangyi's for a clear implementation of that solution. Many other coders simplified the procedure by dividing the integer part of the result in one operation and converting that intermediate result to a string, for example.

By ged
TopCoder Member