
Match Editorial 
SRM 121Tuesday, November 26, 2002
The Problems
ConvertBase
Used as: DivisionII, Level 1:
Value

250 points 
Submission Rate

148 / 198 (74.75%)

Success Rate

72 / 148 (45.68%)

High Score

goongas for 244.10 points

Average Points

175.94 
This one's actually a bit tricky if you don't know how to do it. While C++
has functions for turning a baseN string into an int, it doesn't have one
for the other way around. I don't know about the other languages, but I
presume they're much the same. The trick to this one is that it's much
easier to generate the string backwards than it is to generate it forwards.
You want to take the number and extract the smallest digit (using modulus),
adding that digit to your string. Then divide the number by the radix,
basically pushing the smallest digit off the bottom, and repeat until it
reaches 0. Reverse the string and return it. There's a pair of special cases
you need to look out for  if the number is negative, you'll need to add a 
on the beginning (or the end, before you reverse it.) Also, if the number is
0, you'll have to do that manually. A function for doing base 2 through 10
would look like
string convert( int x, int radix ) {
if( x == 0 )
return "0";
bool isnegative;
if( x < 0 ) {
isnegative = true;
} else {
isnegative = false;
}
string accumulator;
while( x != 0 ) {
accumulator += ( x % radix ) + '0';
x = x / radix;
}
if( isnegative )
accumulator += '';
reverse( accumulator );
return accumulator;
};
or something similar. Obviously this won't handle 11 and up, but that's a
matter of doing something just a little more complex than ( x % radix ) +
'0';  personally I'd make a small function to return the character
representation of a specific digit.
TicTacToe3D
Used as: DivisionII, Level 2 & DivisionI, Level 1:
DivII stats

Value

500 points 
Submission Rate

106 / 198 (53.56%)

Success Rate

83 / 106 (78.30%)

High Score

Anguissette for 499.04 points

Average Points

363.37 
DivI stats

Value

250 points 
Submission Rate

76 / 90 (84.44%)

Success Rate

74 / 76 (97.37%)

High Score

ZorbaTHut for 249.23 points

Average Points

207.33 
Yeah. Just look at those high scores. I did one of them and I still don't
believe it.
Visualize a cube. It's N units wide on each side. We have N Xs to use, and
we need to span the entire cube. Obviously we're going to be barely reaching
from one side to the other on every single one.
Now, first we've got the pure straight lines, reaching from one face to the
opposing face. There are 6 faces on a cube, but we ignore half of them,
because any line is going to be touching two. On each face we can start at
N^2 locations (since the face is, after all, square). So that's n * n * 3.
Then we've got diagonal lines, reaching from one edge to the opposing edge.
A cube has 12 edges (four on the top, four on the bottom, four in the
middle) and once again, we're going to be using two of them for each line.
Each edge has N locations we can start at. n * 6.
Last, there are the reallydiagonal lines (for lack of a better term),
reaching from one corner to the opposing corner. A cube has eight corners
(four on the top, four on the bottom) and again, each line touches two of
them. Let's just add 4 here.
We end up with the equation 4 + n * 6 + n * n * 3, which works in every
situation but the one where it's a 1x1x1 cube. That one's a special case, so
just test for it and return 1.
And that's the entire solution. I solved it quickly because I'd been
thinking about it from the 2001 invitational  it was an efficiency deal in
that case, not a calculation  and I happened to remember it. I'd be
surprised if Anguissette didn't do the same thing, and rather impressed,
actually.
NumCombine
Used as: DivisionII, Level 3 & DivisionI, Level 2:
DivII stats

Value

250 points 
Submission Rate

28 / 198 (14.14%)

Success Rate

8 / 28 (28.57%)

High Score

ishan_ritchie for 651.57 points

Average Points

548.15 
DivI stats

Value

500 points 
Submission Rate

49 / 90 (54.44%)

Success Rate

31 / 49 (63.27%)

High Score

Yarin for 468.28 points

Average Points

334.08 
This problem was one of those that's very easy to overcomplicate, as well as
being quite easy to undercomplicate. You can easily generate every possible
string and then parse it out and calculate it  unfortunately you'll time
out on the parsing, unless you do it extremely efficiently. The best
solution (I believe) is to write a recursive function with four parameters 
the digit you're currently looking at, an accumulator for the running total,
another accumulator for the current number you're creating, and a sign
multiplier, used for making the next operation positive or negative. The
base case for your recursive function is when it's finished with all the
digits. It should add the currentnumber times the sign multiplier to the
running total, compare it to the target, and increment your global counter
if the test works. Otherwise, you've got three cases  "continue with this
number", "add this number and start the next one positive", and "add this
number and start the next one negative". Take a look at Yarin's solution for
a good example of this, or mine if you ignore the minor logic problem (the
test is <=, not <, and the examples didn't catch it. Not my finest moment.)
The only other thing to watch out for is to make sure you have 64bit
integers in the important places, since the Big Number can be up to 15
digits long, and a 32bit number can overflow at 10.
Some people might think that the "sign" variable in the recursive function
isn't necessary, since you can just choose positiveornegative when you add
it to the accumulator. However, if you don't keep track of the sign, you
have the new (and slightly harder) problem of making sure you don't
accidentally subtract the first number instead of adding it  you're not
given a choice on this one.
LinAlg
Used as: DivisionI Level 3:
DivII stats

Value

1000 points 
Submission Rate

19 / 90 (21.11%)

Success Rate

1 / 19 (5.26%)

High Score

Yarin for 675.25 points

It probably says something when the only person who solves a problem is
someone who had the code prewritten, and they *still* only got about
twothirds of the maximum value. On the other hand, a lot of the carnage on
this problem was caused by a problem description that only stated
"whitespace". Most of the time the problems only specify the space
character, and in fact, getting any other whitespace character into the
testing window takes a little doing. However, this is exactly what lars did,
providing a testcase that included a tab character, and probably accounting
for a good half of the submission failures.
Anyone who's taken linear algebra will recognize this, and probably know how
to do it. As I did horribly at linear algebra, I'm probably not the right
one to be explaining this. But here goes anyway.
Your first step should be to get the equations into a standard format  2x +
3y + 4z = 9, where all the variables are on one side and the constant is on
the other side. While annoying, this isn't hard  split the equation at the
= point, parse them both into some handy data structure, and basically
subtract one from the other, then invert the constant. (Actually, for the
purposes of this problem you really don't have to invert the constant, but
I'm explaining this in terms of actually solving the problem.)
At this point you'd want to turn it into a matrix. Use one column for each
variable, as well as one for the constant, and one row for each equation.
From here you want to choose a single row with a value in the first column,
swap it with whatever's in the top row, and subtract it from all the other
rows below it however many times is necessary to zero out their first
column. Repeat this with the second column and a new row (moving it to the
secondtotop row) and so on, for all except the last column (the "constant"
column). This is an oversimplification, unfortunately, there's a lot of
subtlety that you could use for picking which rows. Plus you might find that
you don't have any remaining rows with a value in that column  but in that
case, you can just return 10, since that means an infinite number of
results.
Once you've done all those processes, you also want to look through the rest
of the rows. Each row will have all its variables 0, but if there's a
nonzero constant (representing something on the order of "0 = 15") obviously
there are no solutions, and return 0.
If you've gotten past both of these tests, there's only one solution. Return
1.
As for a proof for why this works, that's beyond me  that's linear algebra,
and I don't feel like reproving matrix math ;) There are plenty of websites
around, and if you're interested  it's a large subject, and has a lot of
ramifications in geometry also  take a class in it. But I'm not going to
say much more about it.
The only thing I *am* going to say is that I've been cheerfully mentioning a
"matrix". I haven't really talked about what data type it should be. It's
probably telling that Yarin used a fraction class with long longs. I suspect
you could pull it off with long double and appropriate epsilon constants,
but I'm not sure. This is the sort of thing that could easily destabilize
and blow your integers completely out of bounds, and only the low factors
(10 to 10) made it possible with long longs.
This is why I have a prebuilt fraction class, and why I'm going to write a
bigint class one of these days. Those of you who actually *have* bigint
classes in your language libraries . . . learn to use them!
By
ZorbaTHut
TopCoder Member