JOIN
 Match Editorials
TCHS07 Championship Round
Saturday, May 19, 2007

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