
Match Editorial 
2003 TopCoder Open
Online Round 1Wednesday, October 15, 2003
Summary
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
PowSum
Used as: Division One  Level One:
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 32bit 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 32bit signed
integer. Such an integer may only have a value between 2**31 =
2147483648 and 2**311 = 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
32bit 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 23579476912147483648 = 210464043.
A correct and very cautious approach is to carry
out the exponentiation using 64bit 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 32bit 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 64bit
integer and subsequently cast, with proper overflow, to 32 bits.
Logger
Used as: Division One  Level Two:
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 caseinsensitive, 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.
Planets
Used as: Division One  Level Three:
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
componentwise differences xd=x1x0, yd=y1y0, zd=z1z0 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 floatingpoint formats
don't respect the requirement that the exponent remain nonnegative 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.
By
Eeyore
TopCoder Member