Match summary

The problem set for the Championship Round consisted of one easy "implement the algorithm" problem, one not very tricky greedy problem and one quite hard problem, which was too hard for most of the competitors. Only three people got it right: tomekkulczynski (first), Burunduk2 (second) and Zuza (fourth). Due to an amazing challenge phase, sluga came third despite a failing hard problem.

As the result, Burunduk2 took home the individual title, while V. Gimnazija became the top team of the contest. Unfortunately for the best performer in the Championship Round, tomekkulczynski, he returned home with no hardware. Since he is the only coder who qualified onsite for both TCHS and TopCoder Open tournaments, hopefully he'll be able to step up big in Vegas!

The Problems

SimpleTextProcessor

Used as: Division One - Level One:

Value 250

Submission Rate 31 / 31 (100.00%)

Success Rate 30 / 31 (96.77%)

High Score Zuza for 248.00 points (2 mins 33 secs)

Average Score 228.52 (for 30 correct submissions)

The only thing you need to do in this problem is to correctly perform the actions described in the statement. First split the words from the input into two halfs and determine the lengths of the longest words in each of the halfs (A and B). Then put the first half into an array of Strings, padding each of the words with spaces until its length is less than A. After that, add a '*' to each of the elements and perform similar actions in the reverse order - add the necessary number of spaces and append the correspondent element of words.

Java implementation of this algorithm follows:

        String[] ans = new String[words.length];
        System.arraycopy(words, 0, ans, 0, N);
	int A = 0;
        for (int i = 0; i < words.length / 2; i++)
		A = Math.max(words[i].length(), A);
	int B = 0;
        for (int i = words.length / 2; i < words.length(); i++)
		B = Math.max(words[i].length(), B);
        for (int i = 0; i < words.length; i++) {
            for (int j = 0; j < A - words[i].length(); j++)
                ans[i] += " ";
            ans[i] += '*';
            for (int j = 0; j < B - words[N + i].length(); j++)
                ans[i] += ' ';
            ans[i] += words[N + i];
        }
        return ans;

ZeroesAndOnesGrid

Used as: Division One - Level Two:

Value 500

Submission Rate 30 / 31 (96.77%)

Success Rate 28 / 30 (93.33%)

High Score Burunduk3 for 497.64 points (1 mins 57 secs)

Average Score 452.33 (for 28 correct submissions)

The key observations for this problem were the following:

The order of the moves is irrelevant, because the final value of the each cell depends only on the number of times it was inverted.
You never need to choose the same cell more than once. If some solution contains the same cell chosen twice, change the order of moves such that the selections of this cell go one after another. Since selecting the same cell twice in a row doesn't change the grid at all, you can safely eliminate the duplicated moves from the solution.
The resulting value of the bottom right cell (row = R - 1, column = C - 1) can be changed only by choosing cell (R - 1, C - 1).

Let's look closer at the last observation. Since we want all cells to contain 0 after all moves, and there is no benefit to choosing the same cell more than once, we can easily determine whether we ever need to choose the bottom right cell or not: we play it if and only if its value was 1 at the beginning of the game. If we must play it, let's make this move first, inverting the values of all cells in the grid and not playing this cell anymore.

Now, when the value of the bottom right cell is set to 0, let's look at the cell with address (R - 1, C - 2). As you can see, this cell can be inverted by only two possible moves - by choosing either (R - 1, C - 2) or (R - 1, C - 1). Since we can not touch the (R - 1, C - 1) cell anymore, the decision whether to play (R - 1, C - 2) cell depends only on the value of this cell (again, we play it only if the value is equal to 1).

Hope you already see the solution, which is all about the following idea. Iterate through the cells row by row, column by column, starting from the last cell and going to the cells with smaller indices. At each step, check the value of the cell and play the cell only if its value is equal to 1. The number of moves during these iterations will be the answer for the problem.

The Java solution, written by marian during the testing process, follows:


public class ZeroesAndOnesGrid {
  public int[][] values;

  public void Invert(int si, int sj) {
    for (int i = 0; i <= si; ++i) 
      for (int j = 0; j <= sj; ++j)
        values[i][j] = 1 - values[i][j];
  }

  public int minMovesCount(String[] table) {
    values = new int[table.length][table[0].length()];
    for (int i = 0; i < values.length; ++i)
      for (int j = 0; j < values[0].length; ++j)
        values[i][j] = (int)(table[i].charAt(j) - '0');
    
    int res = 0;
    for (int i = values.length - 1; i >= 0; --i)
      for (int j = values[0].length - 1; j >= 0; --j) 
        if (values[i][j] == 1) {
          Invert(i,j);
          res++;
        }
    return res;
  }
}

RoadsReorganization

Used as: Division One - Level Three:

Value 1000

Submission Rate 23 / 31 (74.19%)

Success Rate 3 / 23 (13.04%)

High Score Burunduk2 for 565.81 points (22 mins 40 secs)

Average Score 455.57 (for 3 correct submissions)

Imagine we've built a loop which satisfies all conditions from the statement. If you look closer at the intersection of this loop with the initial tree, you see the intersection is a set of disjoint paths (here, the intersection is the set of all roads such that they are present both in the tree and the loop). Let the intersection contain X roads and the kingdom contain N cities. Then, the initial tree contains N - 1 roads, out of which ((N - 1) - X) must be destroyed, and the final loop contains N roads, out of which (N - X) roads must be built. Therefore, the answer is ((N - X) + ((N - 1) - X)) = 2 * (N - X) - 1, and the only task left is to find the maximal number X such that the final loop will contain X roads from the initial tree.

To find this number X we will iterate over the initial tree. Let us be at vertex k and let the previous visited vertex be m. We need to find the maximal number of edges we can select in the subtree that is reachable from vertex k without visiting vertex m. To find this number we do the following things:

If vertex k is a leaf (so only vertex m is adjacent to it), return 0 - we can not select any more edges here.
If vertex k is connected to 2 vertices (vertex m and some other vertex p), select the edge from k to p, recursively find the value for p and return this value incremented by 1.
Now the answer depends on whether we selected the edge from m to k on the previous step or not. If we did select it, then you can select only one more edge from vertex k. If we did not, you can select two more edges. In either case, iterate through all possible selections and return the maximal possible answer you can achieve.

See Zuza's solution for a nice implementation of a very similar approach.

By Olexiy
TopCoder Member