JOIN
 Match Editorial
 Room 1 Review Archive Rookie Review Discuss this match Problem Set Want to write a feature?
SRM 100
June 24, 2002

# The Problems

Division-II Easy
200pt - LStrings.sumLength

This one was simple enough to just follow the instructions to get right. Keep a counter, set it to zero. For each character in each string, check to see if it's a dash. If it isn't, add one to the counter. At the end, return the counter. I haven't yet seen a single failed solution that would have passed the example cases.

Division-II Medium
550pt - PrimeCount.howMany

This one is straightforward at first glance - just set up another counter and a loop to go through each number and divide it by its factors until it reaches 1. While this works for most of the example cases, it fails rather dramatically when a number is a multiple of two large primes, or even worse, when a number *is* prime. A program can do 100,000,000 simple operations in eight seconds without much trouble, but there's no way you're ever going to manage 5,000,000,000 modulus operations in that much time.

The solution, however, is actually quite simple. The inner loop that times out looks like "for( factor = 0; factor <= number; factor++ )". Simply change it to "for( factor = 0; factor * factor <= number; factor++ )" and it will square-root the number of iterations you have. Once you're done, just add one to the count, since "number" will have a factor left over, and return that value.

Division-I Easy

There are various ways to code this - the string size limitation of 20 makes it quite easy. Probably the simplest way is as a recursive function. Take a hypothetical recursive function "count". At each digit, check to see if this digit and the next digit form a number less than 26. If they do, return count( position + 1 ) + count( position + 2 ). It's an O( 2^n ) algorithm, and 2^20 is only a million, so it'll run easily fast enough. If you were worried about speed, you could store the results as you continued and refer to the stored versions.

Another solution is to keep a small array of all the possible states it could be in. There are only three - "ready to start another number", "right after a one", and "right after a two". For each digit you just need to update the various positions, and at the end, return the "ready" count.

Division-II Hard/Division-I Medium
1100pt/550pt - RangeSort.valueAt

It's quickly clear that simple brute-force just won't cut it. That would be a lot of tests. My approach was to put together a list of all the locations where the number of ranges a given number in would change. For example, given [1,5],[3,7], it could change at 1, 3, 6, and 8 (the *first* number it changes it, not before the number). I did this by adding 1 to the upper bounds and putting all the numbers together into a giant set. Of course, this could generate a few false positives - [1,1],[2,2],[3,3], for example, would look at 1,2,3,4, but with this approach it's fast enough.

Once I'd put together this table I simply started from the lowest number and went up one "important point" at a time. Multiplying the number of ranges the number was in by the distance to the next number gave me how many total array items our theoretical array would contain. Once I knew it was in the current "section", dividing the number of array items left by the number of ranges, and adding the start of the current section, gave me the answer.

SnapDragon had a rather nice solution also. While it's too slow to scan 50 integers for each of twenty million numbers, it's fast enough to prepare the arrays intelligently and just count from the bottom on up. He doesn't bother keeping a relationship between which array is which, and it really doesn't matter - if it's a "lower bound" it means "add one to the number of arrays it's currently in", and if it's a "upper bound" it means "subtract one to the number of arrays it's currently in".

John Dethridge, on the other hand, used a binary search, although I have to admit I don't understand why he didn't just use a similar algorithm counting from the bottom.

Division-I Hard