
Match Editorial 
SRM 133Wednesday, February 5, 2003
Match summary
It seems that SRM 131 was no exception, and that 400+ competitors in a SRM will become standard. The problem set was written by yours truly, thus any comments I make will definitely be biased  I wouldn't write a problem if I didn't think it was "good"! For a change though, no problem required dynamic programming. Instead two of the problems could be considered to be graph theory, although of different kind.
Division 1 contained two rather easy problems and one quite difficult, which only 5 people got successfully. A funny thing was that the top 4 scorers in Division 1 all competed in room 3 (SnapDragon, bstanescu, antimatter and WishingBone). The level of the Division 2 problems was fairly standard, maybe with a slightly harder level 1 problem than usual. Winner was first timer mr_nice_guy, who was notsonice to some of his roommates, delivering three successful challenges (and one failed).
The Problems
Anonymous
Used as: DivisionII, Level 1:
Value  300 
Submission Rate  177 / 239 (74.06%) 
Success Rate  125 / 177 (70.62%) 
High Score  coshx for 289.97 points 
Reference implementation: Yarin (practice room)
Implementation
This problem is pretty straightforward, although most likely a successful solution required more code than what was normal for a DivisionII, Level 1 problem (hence it's 300 points).
First we need to find out the frequency of each letter in the headlines (not considering if it's upper or lower case). Thus we start by looping through all characters in all headlines, and update the frequency count for each letter (and ignore all space characters).
The second step is to loop through each message, and check if the frequency count of the letters is less (for each letter) than those in the headlines. This can be done in at least two ways:
 Make a backup copy of the frequency array and for each letter in a message decrease the frequency. If any frequency goes below 0, this message clearly can't be written.
 Loop through all 26 letters, 'A' to 'Z', and for each letter verify that there are no more occurrences of that letter in the message than in all headlines. If this is true for all letters in a message, clearly this message can be written.
FEN
Used as: DivisionII, Level 2:
Value  500 
Submission Rate  162 / 239 (67.78%) 
Success Rate  142 / 162 (87.65%) 
High Score  MisterZimbu for 483.47 points 
Reference implementation: Yarin (practice room)
Implementation
First, we don't really have to think of the input as a chess position.
All we should do is replace consecutive dots ('.') with the appropriate digit.
Since we should only consider consecutive dots on the same line, clearly we should process each line by itself, and make sure to add a slash ('/') between the lines in the output. The probably easiest way is to initialize a FEN string to the empty string and then add characters to it whenever we find a chess piece (plus the appropriate digits).
For each line we loop from left to right. We initialize a counter to 0 for each line  this counter represents how many dots we have seen so far on this line consecutively. If the next character on the line is a dot, we increase the counter and don't append anything to FEN string. Otherwise we have a piece at this square. Then we should first output the number of empty squares before this piece (that is, the counter) if this number is greater than 0, and then output the piece. Once we're finished with the line, we must also make sure to output the number of empty squares to the end of the line, if greater than 0.
Internet
Used as: DivisionII, Level 3:
Value  1000 
Submission Rate  46 / 239 (19.25%) 
Success Rate  23 / 46 (50.00%) 
High Score  mr_nice_guy for 820.56 points 
Used as: DivisionI, Level 2:
Value  450 
Submission Rate  113 / 141 (80.14%) 
Success Rate  91 / 113 (80.53%) 
High Score  WishingBone for 439.93 points 
Reference implementation: Yarin (practice room)
Implementation
A network of routers connected to each other is a typical example of a graph. A graph is a structure containing vertices (nodes) and edges, connecting the vertices with each other. In this problem, the routers are the vertices in the graph, and the connections are the edges.
The problem of finding the articulation points (also called cutvertices) in a graph is a wellknown one, and can be done quite efficiently. In this problem, efficiency is of no importance since the graph is so small (at most 50 vertices). The most straightforward solution is to loop through all vertices, remove it (and all edges connecting this vertex with another vertex), and check if the graph has now been split into at least two components. Actually, you don't have to explicitly remove a vertex, you can simply mark in a variable that a vertex is removed and abort whenever you reach it.
To check if the graph, after the removal of a vertex, is still connected (i.e. contains only one component) can be done by a graph search. We start at one vertex in the graph, then recursively visit neighbouring vertices. We must also make sure we don't visit the same vertex twice during this search; otherwise the search will never stop! If we, after this search is done, have visited all vertices (except the removed one), the graph is connected and the removed vertex is thus not an articulation point.
There is no need to store the graph in some special data structure. When we do
the search, we can parse the neighbouring vertices directly from the string corresponding to that router, like this:
Java:
boolean visited[50];
int removed_router;
void search(int current, String[] routers)
{
if (visited[current]) return;
if (current==removed_router) return;
visited[current]=true;
String[] links=routers[current].split(" ");
for(int i=0;i<links.length;i++)
search(Integer.parseInt(links[i]),routers);
}
C++:
bool visited[50];
int removed_router;
void search(int current, vector<string> &routers)
{
if (visited[current]) return;
if (current==removed_router) return;
visited[current]=true;
stringstream s(routers[current]);
int n;
while (s >> n)
search(n,routers);
}
RemoveDigits
Used as: DivisionI, Level 1:
Value  300 
Submission Rate  129 / 141 (91.49%) 
Success Rate  93 / 129 (72.09%) 
High Score  cruizza for 293.40 points 
Reference implementation: Yarin (practice room)
Implementation
There are several possible ways to solve this problem, and you can easily make a mistake, which challenge phase proved. One method, which was partly explained in the first example in this problem, is to collect the larger digits in the front of the new number. Since the final number will always have the same number of digits (nm) no matter which digits we remove, a number starting with a 9 will always be greater than an number starting with an 8, even if we have to remove many more digits to get the 9 in front. This idea gives the following algorithm:
Let x be the position of the largest digit (y) among the first m+1 digits
(in case of a tie, select the leftmost digit)
Remove x digits so we get y in the front.
After this we should consider maximizing the next digit, but
now we only have m  x removals left. This is a smaller instance of the same
problem, so we can simply call the method again with the new parameters!
A recursive function must always have a termination condition, and in this
case it is if m = n, in which case we should remove all remaining digits.
The whole code becomes like this:
C++:
string maxNumber(string n, int m) {
if (m==n.size()) return "";
char *p=max_element(&n[0],&n[m+1]);
return *p+maxNumber(string(p+1,&n[n.size()]),m(p&n[0]));
}
A completely different solution is to solve the easier problem
"Remove one digit so the remaining number is maximized" m times. This
can be done with two nested loops, the outer loop decreasing m until 0
and the inner loop testing removing all digits, and keep track of
which number is the greatest. The pseudocode could look like this:
loop m times
largest=0
for each position i in n
s=n
remove digit at position i in s
if s>largest
largest=s
end loop
n=largest
end loop
This solution can also be optimized: You don't actually have to try remove all digits in the inner loop and then compare with the best found so far. Instead it's enough to find where the nonincreasing sequence of digits ends, starting from the left. For instance, if we want to remove one digit from the number 9987776544338138327, we start at the beginning and step ahead until the next digit is greater than the previous digit  this happens after the two 3's. Removing the last digit in the nonincreasing sequence of digits will always create the biggest number. This is because such a removal will increase the digit at that position (the position where the 3 was will in the case be replaced with the 8), and it's not possible to increase a digit at a position more to left than this. Increasing a digit in a position to the right will always result in a smaller number.
SlidingGame
Used as: DivisionI, Level 3:
Value  1100 
Submission Rate  7 / 141 (17.00%) 
Success Rate  5 / 7 (41.18%) 
High Score  SnapDragon for 615.10 points 
Reference implementation: Yarin (practice room)
Implementation
Given a puzzle containing 8 pieces, calculate the fewest number of moves required to reach a goal configuration starting at a start configuration. This can be seen, again, as a graph problem where each vertex in the graph is a configuration of the bricks and an edge is a legal move between two configurations. While it is possible to build the actual graph explicitly as it contains "only" 24240 vertices (and each vertex has at most 8 edges) and then perform a shortestpath search (using breadthfirst search), this is unnecessary. Instead we can just directly perform the search on the configurations, like this:
int solve(start,goal)
add start to queue
include start in set of visited configurations
while queue is not empty
x=front element of queue
pop front element of queue
for each neighbour y to x
if y is not in set of visisted configurations
add y to queue
include y in set of visited configurations
end
end
if goal is not in set of visited configurations
return 1
return distance to goal
end
The distance is simply kept as an extra attribute in the set of visited
configurations. This set can be implemented using either
set/map (C++) or HashSet/HashMap (Java). Now, this is all very straightforward
and I'm sure most DivisionI competitors have done similar searches many times.
The "nasty" part of the problem is how to store the configurations. We must not
only be able to generate all neighbours from a configuration, but also
find configurations that are identical even though the actual symbols representing
the pieces may differ. Luckily, there is an elegant solution to all this: bitmasks.
Instead of representing a configuration as a set of coordinates for
the pieces, which makes finding legal moves a cumbersome checking procedure,
each piece can be represented as an integer using 16 bits. Each bit
correspond to one square in the frame, the first 4 bits being the upper row:
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
A piece occupying squares 1 and 5 would correspond to the integer
which has bits 1 and 5 set (that is, 2^{1} + 2^{5} = 34).
Moving a piece in either direction requires only a shift, for instance
moving left requires shifting one step to the left, moving down four steps
to the right etc. Before moving, we must also check that the piece
doesn't touch the edge, which is done with bitmasking. For instance,
we can't move the piece to the right if it already occupies one of the
squares 3, 7, 11 or 15, so we mask the piece integer with
2^{3} + 2^{7} + 2^{11} + 2^{15}. If
the answer is 0, the piece does not occupy any of these squares.
Finally, we must make sure the piece doesn't end up on top of any other
piece, which is checked by masking the new piece location with the positions
of all other pieces.
The configuration can thus be represented as an array of 8 integers.
A "bonus" with this is that you can simply sort this array of integers
to get a representative of this configuration, and thus avoid the problem
with finding identical configurations! That is, after sorting, all identical
configurations will contain the same elements in the array in the same order.