Match Editorial

Those who hesitated were lost as nearly 500 of TopCoder's best jockeyed for position in the first elimination round of the 2003 Open. Nine out of ten contestants made Level One and Level Two submissions, but only one out of four went on to complete a Level Three problem that asked for a simulation of orbiting planets. It was evident that Newtonian physics posed no obstacle for reid, WishingBone, and bmerry, who led their respective rooms with scores over 1400 when the coding phase drew to a close. WishingBone reaped 100 more points during the challenge phase, giving him the victory in this early skirmish.

Although the leader board was thronged with coders from the red and yellow portions of the rating spectrum, blue coders port6000, fiveEasyPieces, and TheFaxman were room winners, along with Division 2 veteran irulet. With so many agile minds solving the Level One and Level Two problems, rapid submission times made all the difference. The quick thinkers who made the cut can look forward to increasingly profound challenges in coming weeks. The rest will watch with keen interest from the sidelines and plot a spectacular comeback in some future match.

The Problems

Value	250
Submission Rate	454 / 460 (98.70%)
Success Rate	417 / 454 (91.85%)
High Score	hamster for 249.47 points (1 mins 19 secs)
Average Score	234.80 (for 417 correct submissions)

We are asked to take each integer in a given range, raise it to every power from one to a given limit, and compute the sum of the whole lot. A solution can be rendered in pseudocode as follows, where ** is the exponentiation operator.

def powsum(low, high, pow):
    tot = 0
    for i in range(low, high+1):
        for j in range(1, pow+1):
            tot += i**j
    return tot

This doesn't tell the whole story, however, if we're using a programming language that restricts the size of integers. If this function were implemented in C++ using 32-bit signed integer variables but with the incremental calculation

tot += (int) pow((double) i, (double) j);

then the value of i**j would overflow in an ugly way and produce an incorrect answer.

The problem statement guarantees that the final result will fit into a 32-bit signed integer. Such an integer may only have a value between -2**31 = -2147483648 and 2**31-1 = 2147483647, inclusive. This is not necessarily true for the intermediate results.

Consider the case where low, high, and power are respectively -11, 10, and 9. For i = -11 and j = 9, we have i**j = -2357947691, which is less than the lower bound of a 32-bit signed integer. If such a value is represented as a double and cast to an int, its value becomes simply -2147483648, throwing off the final result by 2357947691-2147483648 = 210464043.

A correct and very cautious approach is to carry out the exponentiation using 64-bit integers, which easily accommodate the intermediate results of our calculation. The following will do the trick.

def powsum(low, high, pow):
    tot = 0
    for i in range(low, high+1):
        m = 1
        for j in range(1, pow+1):
            m *= i
            tot += m
    return tot

Then again, thanks to the properties of modulo arithmetic, this pseudocode yields correct results when implemented with 32-bit unsigned or signed integers. Consider, for example, that (x mod b + y mod b) mod b = (x + y) mod b. Full proof is left as an exercise for the reader.

Another way to preserve adequate precision is to implement the earlier version with

tot += (long long) pow((double) i, (double) j);

so that the result of the exponentiation is first stored as a 64-bit integer and subsequently cast, with proper overflow, to 32 bits.

Value	500
Submission Rate	435 / 460 (94.57%)
Success Rate	370 / 435 (85.06%)
High Score	ZorbaTHut for 477.98 points (6 mins 9 secs)
Average Score	359.64 (for 370 correct submissions)

We iterate over the messages in order, deciding to log each one only if its priority is equal to or greater than the minimum logging priority. A priority is a pair of values, the first of which is a string, while the second is an integer. If we say that the minimum logging priority is (s_min, i_min), it can be compared with an arbitrary priority (s, i) in the following manner.

If s occurs later in the precedence vector than s_min, the given priority clearly exceeds the minimum, so we may disregard the integer values. If s occurs earlier in the precedence vector than s_min, the given priority falls well below the minimum.

But if s matches s_min, the integers are decisive. In such a case, the given priority meets the threshold only if i is at least as great as i_min.

Pseudocode follows. First comes a helper function for parsing priority strings, and then the main function.

def split_priority(priority):
    tokens = priority.split()
    s = tokens[0].lower()
    i = 0
    if (len(tokens) > 1):
        i = int(tokens[1])
    return (s, i)

def logger(messages, priorities, precedence, priority_min):
    (s_min, i_min) = split_priority(priority_min)
    s_lookup = {}
    for i in range(len(precedence)):
        s_lookup[precedence[i].lower()] = i
    log = []
    for j in range(len(messages)):
        (s, i) = split_priority(priorities[j])
        if s_lookup[s] > s_lookup[s_min]:
            log.append(messages[j])
            continue
        if s_lookup[s] < s_lookup[s_min]:
            continue
        if i >= i_min:
            log.append(messages[j])
    return log

Notice that because priorities are case-insensitive, we render s, s_min, and the contents of precedence in lower case. We store the precedence strings in an associative array (also known as a map or a hash) for ease of lookup and comparison.

Value	1000
Submission Rate	109 / 460 (23.70%)
Success Rate	57 / 109 (52.29%)
High Score	reid for 768.25 points (16 mins 41 secs)
Average Score	496.58 (for 57 correct submissions)

The problem statement supplies formulas with which we are to implement a crude simulation, leaving to us the details of handling the vectors and formatting the output.

We recall from Cartesian geometry that the distance between two points in space (x0, y0, z0) and (x1, y1, z1) may be obtained by calculating the component-wise differences xd=x1-x0, yd=y1-y0, zd=z1-z0 and taking the square root of xd*xd+yd*yd+zd*zd. To see why this makes sense, observe that an analogous result for points in a plane follows directly from the Pythagorean Theorem.

Because the mass of each planet as well as distances between planets are linear quantities, the formula F = (G*m1*m2)/(d^2) yields a linear result. We then apply v[p] = v[p] + F/m[p] * t individually to each component of a planet's velocity.

The following fragment of pseudocode will carry out the simulation, assuming that the arrays p_x, p_y, p_z, v_x, v_y, and v_z are filled with the components of the initial position and velocity of each planet, while m holds the respective mass.

for i in range(t):
    for j in range(len(p_x)):
        for k in range(len(p_x)):
            if j == k:
                continue
            xd = p_x[k] - p_x[j]
            yd = p_y[k] - p_y[j]
            zd = p_z[k] - p_z[j]
            d = math.sqrt(xd*xd + yd*yd + zd*zd)
            F = G*m[k]/(d*d)*t
            v_x[j] += F*xd/d
            v_y[j] += F*yd/d
            v_z[j] += F*zd/d
    for j in range(len(px)):
        p_x[j] += v_x[j]*t
        p_y[j] += v_y[j]*t
        p_z[j] += v_z[j]*t

Now for the question of formatting. The input is straightforward, since real numbers in the specified format can be read directly by the C++ format "%lf" and the Java method Double.parseDouble, for example. The output is trickier to deal with, due to the fact that standard floating-point formats don't respect the requirement that the exponent remain non-negative for small values.

In Java, lars2520 suggests that we tweak the format as follows.

String s = new DecimalFormat("0.000E0").format(dd);
if(Math.abs(dd)<1)
    s = new DecimalFormat("0.000").format(dd)+"E0";
if(s.equals("-0.000E0"))
    s="0.000E0";

There are many ways, some more broadly applicable than others, to accomplish the same in C++. Here's how SnapDragon pulled it off.

string dtos(double d) {
    char buf[1000];
    if( fabs(d) < 1.0 )
        sprintf(buf, "%.3lfE00", d);
    else
        sprintf( buf, "%.3lE", d );
    string s = buf;
    int x = s.find('+');
    if( x != -1 )
        s.erase(x, 1);
    x = s.find("E0");
    if( x != -1 )
        s.erase(x+1, 1);
    if( s == "-0.000E0" ) return "0.000E0";
    return s;
}

After selecting a printf format based on the size of the number, SnapDragon erases any extraneous symbols from the string. These include a plus sign or leading zero in the exponent, or a minus sign in the special case of 0.000, against which the problem statement specifically warned.