
Match Editorial 
SRM 107Wednesday, August 7, 2002
The Problems
DivisionII, Level 1: (250pt)
Submission rate  92% (158/172)
Success rate  79% (124/158)
High score: n0vice, 243.79 points
This problem's hardest aspect was confusing wording. In essence, it's
telling you to find a string that's optimum in some way and put it at the
beginning of all the others  then write the others in series. So the
solution is pretty easy. Start at the first item in the array and see how
"good" it is. We can use a "quality" value without much trouble. For each
item, start quality at 0. Add 1000 if it's evenlength (thus ensuring that
evenlength strings will always be better than oddlength strings.) Now
subtract the length of the strings (giving shorter strings the advantage).
And now, if it's equal to or larger than your current "best", make it your
best.
Note that the "equal to" part is important  since we're doing this in
order, and it wants the one that appears latest, we have to replace our best
if it gets matched.
From there, it's easy. Start an empty string and add your "best" component
to it. Now iterate through the array again  if you're currently on the
"best", don't add it to your final string (since you've already got it), but
otherwise add it.
Now return that.
And that's all.
DivisionII, Level 2: (450pt)
Submission rate  91% (156/172)
Success rate  58% (91/156)
High score: n0vice, 447.23 points
I have to be impressed by derelikt's score on this one, which is quite
probably the highest percentage of possible points I've ever seen from
someone who isn't cheating. Five lines of code. This particular problem is
much easier in Java than C++, since you can use StringTokenizer to divide it
into blocks of A, and just add all those lengths into a HashSet, and return
its size.
On the other hand, it's not really hard in C++ either. Keep a counter  "how
many A's you've seen in a row"  start it at 0. Iterate through the string.
If it's D, add the current value to a set< int > and reset it to 0. If it's
A, increment the counter. Remember to add its current value at the end, and
then remove 0 from the set< int > (you might not have one, so you can't just
subtract one from its size, but myset.erase( 0 ); isn't hard to write) and
return the size.
I honestly don't know which of these would work better in C#, but if C#
doesn't have a Java stringtokenizer clone, the C++ technique will work with
whatever C#'s equivalent of set is.
DivisionII, Level 3: (1000pt) & DivisionI, Level 1: (300pt)
DivII
Submission rate  42% (73/172)
Success rate  41% (30/73)
High score: biomass, 823.56
DivI
Submission rate  76% (80/105)
Success rate  78% (62/80)
High score: kv, 284.83
There are really two major cases you have to look at  the one where the
axis of symmetry goes straight through one column, and the one where the
axis of symmetry goes between two columns. Neither of them are really hard,
though.
In the end, the algorithm comes down to "scan the entire logo, and its
mirror image, and add one for every time the squares on both sides aren't
identical". Do that for each vertical axis  remembering both possible
kinds  and return the smallest value you can achieve.
The actual implementation could be done in quite a few ways. Some people
used arrays to write the data to, translated along some axis, so that the
"mirror point" was always, say, location 50. In this case you could just
write it in verbatim for the "axis goes through a column", and shift
everything on the left side of the mirror point one more space to the left
for "axis goes between columns".
radeye set his up to do the reading directly from the input data, with some
logic to avoid running out of bounds.
I, personally, used a map< int, map< int, bool > >, which is nice because it
mimics an infinitelysized 2d array, defaulting to false. So I'd write the
data in, then just scan 0,0 to 50,50, along with the reflection, then clear
it for the next one.
DivisionI, Level 2: 550pt
Submission rate  37% (39/105)
Success rate  77% (30/39)
High score: ZorbaTHut, 452.58 points
I honestly don't know of anyone who did this the clever way  I ended up
talking with an admin afterwards, and he explained the Good solution. So
here's the good solution.
Instead of thinking of it as a series of resistors, just think of the nodes.
Right now our task isn't to figure out which resistors are redundant, it's
to figure out which nodes are redundant. It's pretty easy to see that if a
node is redundant any resistors linking to it are likewise redundant.
First build your handy adjacency matrix. Now you've got a big loop for each
point.
First, remove given point from the adjacency matrix. Then run Floyd's on the
whole thing. Now for each point remaining, check to see if there's a path
from it to A or B. If there isn't, then it's not part of a simple path.
Repeat for the next point, accumulating the simple paths.
In the end it's O(n^4), and you have a bunch of nodes that aren't part of
simple paths. Run through your original string and if either side of a
resistor isn't part of a simple path, add it to your list. Sort and return.
Now here's a somewhat hacked kludgy way that does, in fact, work :)
The way I ended up figuring out is (of course) a recursive algorithm. Keep
an array of which nodes are in a simple path from A to B (start them all at
"false", of course) and an array of which nodes you've been through. Now
just do a depthfirst search. If you find a path to B, you can set A, B, and
all the nodes in your path to "true". If you run into a path that's already
set to "true" from a different direction you can set all the nodes in the
current path to "true" also. However, if you run into a piece of the same
path you're already on, you can't take a node more than once, so don't set
anything to true.
It's a bit hard to explain  you may wish to look at my source. gd[] is the
"which nodes are in a simple path" array ("good"), and tk[] is the "which
nodes are in the path you're currently exploring" array ("taken").
A lot of people did clever things to try to embed the actual number of
connections inside the adjacency matrix. I didn't bother. I built an
adjacency matrix like normal, then just went through the connections
(snagging them out of the input string a second time) and tested them all.
Sort them as you go, then sort the final array and return it.
DivisionI, Level 3: 800pt
Submission rate  10% (10/105)
Success rate  40% (4/10)
High score: Yarin, 491.65 points
Oddly enough, this problem was actually bruteforcable today, and I believe
bruteforce may be its only solution. In general, what you wanted to do was
generate every combinations of rules, then make a really enormous array with
the start pattern in the middle and run every combination of rules on it,
seeing which gives you the best result.
The actual implementation was a little trickier. It's easy to calculate
"lightspeed", the fastest speed at which anything in the middle can effect
anything on the edges. It's one cell per iteration, since each cell only
pays attention to the cells on either side. That means that, after 300
iterations, with a 50cell starting pattern, your pattern will be, at most,
650 cells wide.
Of course, it's not *quite* that simple. Since you can have rules that
generate life where there is no life  say, for example, DDD  some
algorithms might start generating fringe effects on the side. My
implementation kept both cells on the very edges "dead", meaning that
invalid data could start creeping in from the sides at lightspeed also. So I
would need another 300 cells on each side to prevent that. In the end, to
keep from getting tripped up by an inevitable stupid offbyone error, I
made my entire array 2000 cells wide and started the "initial pattern" at
location 1000. This meant that locations 0300 were garbage, 7001350 were
important, and 17002000 were garbage.
The next thing that tripped me up was another problem, this time hinging on
"infinite life" on either side. However, with the way I'd set it up,
locations 500 and 1500 would be in this "infinite" area, if there was one.
No problem! I made a loop to start at 500 and find the first dead cell, and
another loop to start at 1500 and go backwards to find the first dead cell,
and then my main "diversity finder" just went from one side to the other.
Finding diversity wasn't really hard. Keep a counter of "how many alive
cells have you found in a row". Start from the first side and go to the end.
If the cell you're on is alive, increment the counter. If the cell you're on
is dead, add the current value of the counter to a list, then set the
counter to 0. Once you've iterated all the way through just scan the list
for duplicates (and zeros) and eliminate them all, then return the size of
the list. Note that C++ STL's set class does the job quite nicely, though
you have to remove 0 manually (not hard  myset.erase( 0 ); ).
The only remaining part is "run every combination of rules". Generating
every combination of rules isn't hard either. You can think of it as an
array of the possible eight rules, with a flag for whether that condition
brings life or death  in fact, that's exactly how I implemented it. Then
it's just a matter of trying every combination of those rules one after
another  256 tests, overall.
Of course, you need very efficient code for all of this, or it will time
out. My solution runs even the worst cases in under two seconds  look at it
if you want hints.
By
ZorbaTHut
TopCoder Member