Match Editorial

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 not-so-nice to some of his roommates, delivering three successful challenges (and one failed).

The Problems

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 Division-II, 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.

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.

Value	1000
Submission Rate	46 / 239 (19.25%)
Success Rate	23 / 46 (50.00%)
High Score	mr_nice_guy for 820.56 points

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 cut-vertices) in a graph is a well-known 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);
}

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 (|n|-m) 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 non-increasing 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 non-increasing 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.

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 shortest-path search (using breadth-first 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 Division-I 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¹ + 2⁵ = 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³ + 2⁷ + 2¹¹ + 2¹⁵. 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.