
Match Editorial 
2002 TopCoder Invitational
Online Round #2Thursday, October 17, 2002
The Problems
Bullets
Used as: Level 1
DivI

Value

250 points 
Submission Rate

428/435 (98%)

Success Rate

414/428 (97%)

High Score

mbarb for 248.60 points

Considering the difficulty of the Level Two problem, perhaps it's a good thing that this one was so easy. Many people found testing took longer than writing the actual problem (myself included) even using copy'n'paste tricks  one case where an autotester plugin would be superbly helpful. mbarb completed his implementation in two minutes and eight seconds, which on its own would have won him a place in Round 3 (though mbarb also solved the Level Two, bringing him up to room leader status.)
The simplest way to accomplish this was bruteforce. Take each set of gun markings and rotate them as many times as necessary to make a full circuit, comparing at each step. If they match the bullet markings, return that element number. If none of them match, return 1.
Implementations can be split into basically three groups. The way I implemented it was to use three nested loops and do singlecharacter comparisons in the deepest one, using the seconddeepest as an offset, and modulus to find the actual character. My innermost test looked rather like if( gunmarkings[ currentgun ][ ( currentlocation + offset ) % size ] != bulletmarkings[ currentlocation ] ) this_isnt_it();
Some people decided to rotate the gun markings one character at a time, often making use of substring operations in the process. This had the advantage that they could get rid of a loop. The cleverest solutions I saw simply doubled the string, then did a substring search, looking for the bulletmarkings inside the doubled gunmarkings. If the gunmarkings could be rotated to match, there will be a
substring match, and if not, then not. This could be implemented as a single loop and a test.
Speed wasn't an issue, as in the worstcase you're doing 50^3 tests, which is well within the eightsecond boundary.
MatArith
Used as: Level 1
DivI

Value

500 points 
Submission Rate

219/435 (50%)

Success Rate

86/219 (39%)

High Score

bstanescu for 336.60 points

This one wasn't as hard as the numbers would have you believe . . . just very very long, bugprone, and with a flaw in the problem description. The first thing you did should have been to turn the input into a more usable form. I decided to use a vector< vector< int > >, due to its resizability and passbyvalue semantics. This won't have any meaning to anyone who isn't C++  I honestly don't know what you'd use otherwise, but since you're basically going for a 2d integer array, it shouldn't be hard to find something.
Once you've parsed the input arrays into your data format of choice, you should also write multiply and add functions. They should return something special if the arrays aren't compatible  in my case, an empty array, which happened to conveniently translate to exactly the error return. Remember to check for overflow in *both* addition and multiplication  many people didn't. Also remember to use the exact overflow numbers, or alternatively, just see if it's the same number after it's been cropped to 32 bits, since those are the 32bit overflow points.
Addition is easy, and nobody should have trouble with it. Multiplication can be a bit harder, and anyone who didn't already know it was probably doomed. I personally am not an expert in matrices  I've never gotten the hang of them for some reason  but your basic algorithm will look like three nested for loops. Unfortunately this is exactly where the glitch in the problem description was, and it went unnoticed for a long time because people who knew matrix multiplication simply skipped it, whereas people who didn't know it obviously had some trouble.
In any case, once those were completed, there was still the orderofoperations to deal with. Quite honestly, my expression parsing technique is horrible  in this case I made one pass through the string to take care of multiplication, adding new matrix names as I went ( "A*B" would be replaced with "D", and I'd add a D matrix to my matrix database), then passed through again for addition. There are doubtless better ways, but for this situation, this worked beautifully.
After all that, of course, you've got to take your 2d array format and turn it back into strings, being very careful to avoid terminating spaces on the end of each string.
You might be a bit worried about efficiency, but it's unnecessary. A pessimistic look at it gives us a maximum of 50^4 calculations, which is 6,250,000, well under the tenmillion point where I even start worrying. Looking a bit closer yields even smaller numbers  at most there are 24 operations (two letters each, plus one for the first operation, and 50 letters at most in the equation), and the arrays go up to 25 width at most  one space and one digit per item. As long as you're not being blatantly inefficient, it should be just fine.
Doorknobs
Used as: Level 1
DivI

Value

1000 points 
Submission Rate

53/435 (12%)

Success Rate

27/53 (51%)

High Score

memetic for 721.24 points

This is one of those problems where the only thing that saves you is the problem restrictions. Luckily, we only need to deal with six doorknobs, and that's what makes this problem possible.
First off, a bit of semantics. I realized pretty early on that it would simply things enormously if I considered the start position a "doorknob". No, it isn't a doorknob, but if we consider it one, the question changes from "find the shortest distance from start to any doorknob, then n1 more doorknobs" to "starting at doorknob 0, find the shortest distance to n more", which is much much easier.
So we're going to call the start position a doorknob.
Now what we want is the shortest distance from any one doorknob to any other. This actually isn't all that hard. You can do a floodfilllike algorithm, or a breadthfirst search, on the map. Efficiency might be a little worrying on the floodfill, since you might be doing it seven times on a 50x50 grid, so I found breadthfirst worked quite nicely. In any case, just keep in mind not to go through walls, and assign a suitably high infinity value (one million works fine) if you can't get there from here.
At that point it's trivial  just bruteforce all the combinations. At worst there's well under 1000 of them.
Problem solved.
A few other interesting stats. The lowest ranked competitor remaining in the tournament is Fingers, with a rating of 1037. Fingers actually did quite well this round, submitting a successful Level One problem in under five minutes for 243.04 points. Fingers was seeded #822 at the start of the tournament. The cutoff score from last round was gmenhorn, who spent 8 minutes and 40 seconds on the Level One to yield 229.34 points.
This means that if you spent more than 8 minutes and 40 seconds to complete the Level One, and didn't get any successful challenges, you didn't continue to the next round. I expect Round 3 to be hard enough that simply getting the Level One won't be enough, and by Round 4, there'll be figurative blood
in the water.
Good luck.
By
ZorbaTHut
TopCoder Member