Monday, October 23, 2006 Match summaryTCHS SRM 17 proved to be quite difficult, making for a very exciting challenge phase as half of the medium submissions alone were successfully challenged. Looking to the top of the field, Zuza won his third TCHS match thanks to the fastest time on the easy problem and deceptively difficult medium problem, regaining his red color. Finishing second with the help of a challenge was ahyangyi, who now sports a shiny red color for the first time in his TCHS career. Rounding out the top 5 were fatit who won 25 challenge points, Achtung-Achtung who although failing the medium problem was helped by 75 points in challenges as well as the high score on the hard problem, and msg555 who also gained 75 points in challenges. The ProblemsBisquareSumsUsed as: Division One - Level One:
This problem was rather straightforward, as most failures were caused by trivial implementation errors. The first thing to notice is that the constraints
on this problem are low enough that we can iterate through all possible integers between low and high, and test each one to see if it can be represented as a bisquare.
However, there is an easier way to solve this problem. We can simply iterate through all pairs of integers x and y between low and high, and check if low ≤ x2 + y2 ≤ high.
However, we must be careful not to count the same bisquare twice. To account for this, we can flag each bisquare in a boolean array, making sure to count each bisquare only once.
This simple algorithm can be implemented in Java as follows: int getSums(int low, int high) { int ret = 0; boolean vis[] = new boolean[high + 1]; for(int i = 0; i * i <= high; i++) { for(int j = i; j * j + i * i <= high; j++) { int res = i * i + j * j; if (res >= low && !vis[res]) { vis[res] = true; ret++; } } } return ret; } }ScrabFortune Used as: Division One - Level Two:
This problem looks quite simple at first, but a quick glance at example 3 tells us otherwise. That being said, there are two main ways to solve this problem: the dynamic programming
approach and the greedy approach. Most coders opted to take the dynamic programming route, so we'll investigate this solution first. F(idx, revealed) = best(F(idx + 1, revealed + rev[idx]) + pool[idx], F(idx + 1, revealed)) if idx < pool.length F(idx, revealed) = "" if idx == pool.length and revealed >= threshold F(idx, revealed) = "IMPOSSIBLE" if idx == pool.length and revealed < threshold Here, we can define our best function in pseudocode as follows: String best(String a, String b) { if (a == "IMPOSSIBLE") return b; else if (b == "IMPOSSIBLE") return a; else if (a.length != b.length) return (a.length < b.length) ? a : b; else return (a < b) ? a : b; }For a full implementation of this algorithm, take a look at msg555's solution, which cleverly reduces the letter pool down to using bitmasks. While coming up with the aforementioned algorithm may not be much trouble for seasoned coders who are familiar with dynamic programming, coming up with the correct greedy algorithm gave many coders a difficult time. First, we can't just greedily take the most used letter on the board repeatedly, as per example 3 this may not yield an alphabetically smallest solution. The correct algorithm uses a two-pronged greedy approach. First, we find the length of the shortest (but not necessarily smallest alphabetically) solution by repeatedly taking the most frequently appearing letter. Then we can iterate through each unique letter in pool in alphabetical order, and for each one ask the question: "If I use this letter in combination with my (initially empty) partial solution, can I still arrive at a shortest solution?". This question can be answered by using a modified version of the algorithm above. First, we use all letters in our partial solution, as well as the letter that we're investigating. Then, for the rest of the problem, we choose the most frequently appearing letter until we arrive at a solution. This algorithm correctly finds the shortest solution possible, such that you must use the letters in your partial solution in conjunction with the letter you're investigating. Thus, iterating through each letter of pool in alphabetical order, and adding that letter to our result if using the letter yields a shortest solution will always arrive at the alphabetically first solution among all shortest solutions. Here's an implementation of this algorithm in Java: char[] pool; int[] reveal; //Given a sequence of letters that have already been used, compute the length of the shortest possible solution. int solve(String sofar, int left, int threshold) { int ret = sofar.length(); while (left > threshold) { int best = 0, position = 0; //Find the most frequently appearing letter that hasn't yet been used. for (int i = 0; i < pool.length; i++) if (sofar.indexOf(pool[i]) == -1 && reveal[i] > best) { best = reveal[i]; position = i; } if (best == 0) { return -1; } left -= reveal[position]; sofar += pool[position]; ret++; } return ret; } String getMin(String _pool, String[] board, int threshold) { pool = _pool.toCharArray(); Arrays.sort(pool); reveal = new int[pool.length]; int left=0; //Count how many times each letter in pool appears in board. for (int i = 0; i < board.length; i++) { left += board[i].length(); for (int j = 0; j < board[i].length(); j++) { for (int k = 0; k < pool.length; k++) { if (board[i].charAt(j) == pool[k]) { reveal[k]++; } } } } //Compute the shortest possible solution. int shortest = solve("", left, threshold); if (shortest == -1) { return "IMPOSSIBLE"; } String ret = ""; for (int i = 0; i < pool.length; i++) { if (ret.indexOf(pool[i]) == -1) { //If using this letter yields any shortest solution, use it. int res = solve(ret + pool[i], left - reveal[i], threshold); if (res !=- 1 && res == shortest) { ret += pool[i]; left -= reveal[i]; } } } return ret; }MinePut Used as: Division One - Level Three:
As with the medium, coders took two different approaches for solving this problem. The first solution uses backtracking. In other words, we recursively try to put a mine in each spot, making sure that the resulting board is valid after each move, and figure out the maximum number of mines that we can place this way. Pseudocode for this algorithm looks something like this: recurse(int row, int column, int minesPlaced) { if (col == numCols) { col = 0; row++; } //We'ved iterated through the entire board, so return. if (row == numRows) { ret = max(ret, minesPlaced); return; } //See if we can place a mine in this cell. if (freeSquare(row, column) && canPlaceMine(row, column) ) { //Try placing the mine to see what happens. placeMine(row, column); recurse(row, column + 1, minesPlaced + 1); //Undo this change so that we can look at other possibilities later - ie "backtrack". unPlaceMine(row, column); } //We should also try not placing a mine here in case this is the optimal choice. recurse(row, column + 1, minePlaced); }Note that we need to be careful while checking to see if we can place a mine in a square, as well as updating the board to ensure that we don't timeout. To determine if we can place a mine in a certain cell, we only need to make sure that the neighbors of that cell will allow for at least one mine to be placed adjacent to them. Then when we place the mine, we can decrease the number of mines that may be placed around each of the cell's neighbors. Pseudocode for canPlaceMine and placeMine follows (unPlaceMine is similar to placeMine): bool canPlaceMine(int row, int col) { for (each cell c adjacent to (row,col)) if (maxMines[c] == 0) return false; return true; } placeMine(int row, int col) { for (each cell c adjacent to (row,col)) maxMines[c]--; }For a complete implementation of this algorithm, take a look at nima.ahmadi's solution. The second approach taken during the challenge was to simply generate all subsets of the board using bitmasks. That is, we generate each possible subset of cells of board, and check each one to verify that it is valid. To make it feasible to use a single bitmask for all rows, there's a trick that we can use that transforms a single integer into (row,column) form and vice-versa. Since there are numCols columns in each row, then the jth column of the ith row can be uniquely represented as B = i * numCols + j. Thus, to get an integer in this canonical form to its corresponding (row,column) representation, we have row = B / numCols and col = B % numCols. Using some of our pseudocode above, the algorithm looks something like this: int solve() { int N = totalCells(board); int bestAnswer = 0; for (int i = 1; i < (1 << N); i++) { bool valid = true; int nMines = 0; for (int j = 0; j < N; j++) { if (i & (1 << j) ) { nMines++; int row = N / numCols; int column = N % numCols; //Make sure that there is actually a mine. if (board[row][column] != '.') { valid = false; break; } //If there is any mine we cannot place, then the board is invalid. if (canPlaceMine(row, column) == false) { valid = false; break; } else placeMine(row, column); } } if (valid) bestAnswer = max(ret, nMines); } return bestAnswer; }You can see a complete implementation of this algorithm by looking at Burunduk3's solution. |
|