JOIN
 Match Editorials
TCHS SRM 1
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,000-point 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:

• Use the Forums to learn from other coders, discuss solutions, and ask for advice. There are always active members willing to help, and you can learn a lot quickly.
• There are several Educational Articles that will help you learn techniques and concepts that you can apply in the next challenge and in your educational or professional life.
• The advice you will hear most often, of course, is: practice! You can log in to the Arena practice rooms anytime.

Now, let us discuss the match problems:

# The Problems

Used as: Level One:
 Value 250 Submission Rate 91 / 95 (95.79%) Success Rate 84 / 91 (92.31%) High Score sluga for 246.65 points (3 mins 19 secs) Average Score 220.99 (for 84 correct submissions)

The task for this problem is easily defined as:

• if more than 10% of the readings are infringements (less than minLimit or greater than maxLimit), return 0.0.
• otherwise, return the average of readings within the limits
Then we can iterate over the readings, counting the number of infringements and summing up the non-infringing speeds (to calculate the average). The following Java code implements this idea:
```  int inf = 0, sum = 0;
return 0.0;
// return the average of non-infringing readings
else
```

Almost all possible errors (like checking for "<" instead of "≤" in the speed limits, or the opposite with respect to the 10% of non-infringing 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.

SymbolFrequency
Used as: Level Two:
 Value 500 Submission Rate 66 / 95 (69.47%) Success Rate 60 / 66 (90.91%) High Score Burunduk1 for 447.54 points (9 mins 57 secs) Average Score 325.12 (for 60 correct submissions)

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 floating-point 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.

TroytownKeeper
Used as: Level Three:
 Value 1000 Submission Rate 49 / 95 (51.58%) Success Rate 37 / 49 (75.51%) High Score Zuza for 961.17 points (5 mins 45 secs) Average Score 676.22 (for 37 correct submissions)

This problem features one of the favorite subjects of algorithm challenge problems: labyrinths! Everyone who has ever tried a programming challenge has come across ascii-represented 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 Depth-First Search (DFS) and Breadth-First 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;
}
```

By ged
TopCoder Member