Qualification Problem Set 1 January 1112, 2005 Summary 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 ProblemsFairnessUsed as: Division One  Level One:
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). LandMinesUsed as: Division One  Level Two:
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. 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<0x>=layout.length)return; if(y<0y>=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(x1,y); if(!r2)dfs(x+1,y); if(!c1)dfs(x,y1); if(!c2)dfs(x,y+1); } 
