Match Editorials

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

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

  int inf = 0, sum = 0;
  for (int i=0; ireadings.length/10) 
    return 0.0;
  // return the average of non-infringing readings
  else 
    return (double)sum/(readings.length-inf);

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.

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++;
      }
    }
  }

  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;
  }

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.

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;

  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);
  }

  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;
  }