Monday, June 5, 2006 Match summary Much more than just another typical match, this marked the first in a new series of challenges for high school students. Congratulations to everyone who joined in this historic match! In a close race, Burunduk1 from the Russian Federation won the match, thanks to fast submissions (that took him to the third place after Coding Phase) and to two successful challenges that gave him the points he needed to overtake the other top scorers. He was followed closely by Zuza from Croatia, who scored the fastest 1,000point submission, with Weiqi from China close behind. But there were many more than the top three coders in this match. Welcome to all the new members that have joined in to compete in the high school competitions. In this first round, almost 100 coders from 24 countries participated, with about 40% of them newcomers who joined in to compete in the TCHS. Now, how did you feel the match? Did you like it? Do you still hear your overclocked heart beating at the rhythm of your keystrokes? Did you stay awake for three more hours discussing or debugging your solutions? There's a lot to learn and explore while you wait for the next challenge:
Now, let us discuss the match problems: The ProblemsSpeedRadarUsed as: Level One:
The task for this problem is easily defined as:
int inf = 0, sum = 0; for (int i=0; i Almost all possible errors (like checking for "<" instead of "≤" in the speed limits, or the opposite with respect to the 10% of noninfringing readings) were shown in at least one example. Coders that failed this solution might want to test all given examples before submitting their solutions. Frequently, a problem is not completely understood until you read and interpret completely the examples; and many errors can be caught by testing them. If you're new to TopCoder, you might want to try competing with one of the existing plugins: some of them write the class and method headers and will test the given examples by themselves, saving valuable coding time and, more importantly, catching some errors before your submission. SymbolFrequencyUsed as: Level Two:
In this problem we must compute a variance of values occurring in a text with respect to some expected values, as defined in several possible tables. Then, the least of these values must be returned. Let us split the problem in three simpler tasks to show the solution. First, reading the text counting the number of occurrences of each letter: int total = 0, cnt[] = new int[26]; for (int i=0; i<text.length; i++) { for (int j=0; j<text[i].length(); j++) { char c = text[i].charAt(j); if (c≥'a' && c≤'z') { cnt[c'a']++; total++; } } }We are using total and cnt in the following code. Now, for each of the 26 lowercase letters, each table defines a percentage that determine the expected count in the text. The tables given are limited to 16 letters, and the rest must be assumed to have 0% of expected occurrence. The second part in this solution will be parsing the given tables to an appropriate representation. If we do this for each of the tables, and compute the deviation of the text with respect to it, we must just return the minimum computed value. The following code implements this part of the problem (the function deviation is defined below): double bestdev = 1.0; for (int i=0; i<frequencies.length; i++) { // create a table to store expected percentages, int expected[] = new int[cnt.length]; // parse the values given in the table, for (int j=0; j<frequencies[i].length()/3; j++) { int letter = frequencies[i].charAt(j*3)A; int exp = (frequencies[i].charAt(j*3+1)'0')*10+frequencies[i].charAt(j*3+2)'0'; // ... and store each percentage in the table expected[letter] = exp; } // with the parsed table, compute its deviation with respect to the text double dev = deviation(expected, cnt, total); if (bestdev<0  bestdev>dev) bestdev = dev; } The only missing code is the actual computation of deviation values. This can be done easily just implementing the definition given in the statement: double deviation(int[] exp, int[] act, int total) { // exp represents the expected percentages; act are the actual // occurrences and total the number of letters in the text double dev = 0.0; for (int i=0; i<exp.length; i++) { double x=act[i]exp[i]/100.0*total; dev += x*x; } return dev; }And we are done. The variable bestdev is the value to return in the main function. A concern that might (or will) arise when computing a solution with floatingpoint arithmetic is whether the precision is enough to represent all handled values, and if errors can propagate through computations and end up as a big precision error in the returned value. Though this is not the case as this solution handles only small values, it should be a point to consider in future matches. The reader is encourage to follow this article to get an idea of where and why floating point arithmetic can fail in a challenge. TroytownKeeperUsed as: Level Three:
This problem features one of the favorite subjects of algorithm challenge problems: labyrinths! Everyone who has ever tried a programming challenge has come across asciirepresented labyrinths with variety of tasks to solve. The majority, and this is not an exception, include as one task to 'walk' within the rooms or empty spaces. This can't be done by just looking at the values of the cells and their neighbors, but actually traveling across the maze is needed. This problem required to count the number of 'visible' walls that need to be painted  ie., calculating which empty spaces (floor cells) are 'reachable' and then counting the number of walls neighboring those cells. This is a perfect example to introduce search techniques like DepthFirst Search (DFS) and BreadthFirst Search (BFS). We will use the former in this solution, though either of them is equally suited for this problem. The following function will be called from a starting position, and call itself on every neighboring cell. During the recursive calls the cells visited will be marked, for several reasons: to avoid infinite recursion, to remember later which cells are reachable and to compute the number of walls. We are also using the trick of adding a 'border' to the given map, to guarantee that: a) we can reach all reachable parts of the maze from a single starting point (any border cell), and b) exterior walls (border cases) require no special attention, as they now have an empty cell as a neighbor. Declaring: int rows, cols; boolean[][] data, visited;as instance variables in our class, we can define the function the search function: void dfs(int x, int y) { if (x < 0  y < 0  x ≥ rows  y ≥ cols  data[x][y]  visited[x][y]) return; visited[x][y] = true; dfs(x + 1, y); dfs(x  1, y); dfs(x, y  1); dfs(x, y + 1); }which, if called from (0,0) from instance, will mark each reachable cell in visited matrix. Now the rest of the solution is just to prepare the input (add the border), invoke the DFS, and count the number of 'visible' walls: public int limeLiters(String[] maze) { rows = maze.length + 2; cols = maze[0].length() + 2; data = new boolean[rows][cols]; visited = new boolean[rows][cols]; // construct a new maze with an added empty border for (int i = 0; i < rows  2; i++) for (int j = 0; j < cols  2; j++) data[i + 1][j + 1] = (maze[i].charAt(j) == '#'); dfs(0, 0); // will mark reachable floor spaces // now if two neighboring cells have different visited[][] value, one // if a wall block and the other a reachable floor: count as a wall to paint int ans = 0; for (int i = 0; i < rows; i++) for (int j = 0; j < cols  1; j++) if (visited[i][j] ^ visited[i][j + 1]) ans++; for (int i = 0; i < rows  1; i++) for (int j = 0; j < cols; j++) if (visited[i][j] ^ visited[i + 1][j]) ans++; return ans; } 
