Match Editorial

Rooms 1 and 6 probably had the easiest hard problem, as 99 people got it right. As a result, it had the highest cutoff of any room, and only a few people made it in with only the easy problem. Topping off the list of advancers was tomek, with a comfortable lead over second place Wernie. Andrew_Lazarev rounded out the top 3 and denpoz ended up doing best amongst the newcomers, taking a respectable 26^th place.

The Problems

Value	250
Submission Rate	146 / 175 (83.43%)
Success Rate	106 / 146 (72.60%)
High Score	weimashizhu for 245.86 points (2 mins 57 secs)
Average Score	193.76 (for 106 correct submissions)

Most of the time, the easiest why to solve any sorting problem is to write a comparator method and then use the built in sort function that your language of choice provides. In this case, we want to break ties in the sort by putting the word that appears earlier in the input first. This is known as a stable sort, and you need to be sure that you use it, or else you could end up with tied elements in the wrong order. In Java, the default sort methods are all stable, while in C++, you have to use stable_sort. Writing the comparator is fairly simple. You just calculate the averages for each word with a couple of loops, and then return -1, 0 or 1, depending on which of the averages is greater (or 0 if they are equal).

Value	1000
Submission Rate	116 / 175 (66.29%)
Success Rate	95 / 116 (81.90%)
High Score	tomek for 913.62 points (7 mins 7 secs)
Average Score	631.54 (for 95 correct submissions)

This problem can be solved using either a depth or breadth first search. Depth first search (DFS) is usually easier to code, so we'll go with that one. The basic idea of any DFS algorithm is to branch out from some start state, and keep visiting new states until you can't find any unvisited states to visit, and then backtrack. In this case, the state is simply a location on the board. From a particular state, you can visit any of the 4 adjacent spaces, so long as the metal detector doesn't beep in that direction. It should be noted that you are allowed to go to a previously visited location even if the metal detector beeps in that direction. However, this doesn't really matter because there is no reason to ever visit a spot more than once as knowing where some of the mines are doesn't help you deduce anything about other potential mines.

Also, you really don't have to worry very much about efficiency in this problem, so its ok if your code to check for beeping is rather inefficient. The code below is very inefficient, as it does a lot of work over and over again to check for beeps. An improved version could precalculate whether the metal detector beeps from each location, in each direction in O(N^2). Then, the DFS would also be O(N^2). Yet, the version below is O(N^3), which is still plenty fast when N is only 50.

boolean[][] visited;
String[] layout;
int ret = 0;
public int numClear(String[] layout){
    this.layout = layout;
    visited = new boolean[layout.length][layout[0].length()];
    dfs(0,0);
    return ret;
}
void dfs(int x, int y){
    if(x<0||x>=layout.length)return;
    if(y<0||y>=layout[0].length())return;
    if(visited[x][y])return;
    //If we get here, x,y is an unvisited, valid state
    ret++;
    visited[x][y] = true;
    boolean r1 = false, r2 = false;
    boolean c1 = false, c2 = false;
    //r1, r2, c1, and c2 each represent a beep in a certain direction
    for(int i = 0; i<layout.length; i++){
        if(layout[i].charAt(y) == 'M' && i < x)r1 = true;
        if(layout[i].charAt(y) == 'M' && i > x)r2 = true;
    }
    for(int i = 0; i<layout[0].length(); i++){
        if(layout[x].charAt(i) == 'M' && i < y)c1 = true;
        if(layout[x].charAt(i) == 'M' && i > y)c2 = true;
    }
    //now recurse in each of the valid directions
    if(!r1)dfs(x-1,y);
    if(!r2)dfs(x+1,y);
    if(!c1)dfs(x,y-1);
    if(!c2)dfs(x,y+1);
}