JOIN
 Match Editorial
2006 TopCoder Collegiate Challenge
Online Round 1-C

September 27, 2006

## Match summary

The score distribution in this round seems similar to the ones in rounds 1-A and 1-B. The problems were balanced, with the exception of the hard problem, which was solved by only three people. The top spot was taken by reid, second went krijgertje and rounding out the top three was Krzysan, who regained his red status. Congratulations to them and to all the advancers!

# The Problems

FriendlySequences
Used as: Division One - Level One:
 Value 250 Submission Rate 274 / 300 (91.33%) Success Rate 236 / 274 (86.13%) High Score Krzysan for 248.44 points (2 mins 15 secs) Average Score 208.06 (for 236 correct submissions)

This proved to be a simple problem -- many people solved it, and some did so in impressively short times. A naive approach is to fix the start and end indices of a contignuous subsequence. We can then test if the numbers in the sequence are friendly. We can do this by testing if each number in the subsequence is friendly with the first number in it.

```
public int count(int[] a) {
int nr = 0;
for (int i = 0; i < a.length;i++) {
for (int j = i + 1; j < a.length; j++) {
if (isFriendly(i, j, a)) nr++;
else break;
}
}
return nr;
}

boolean isFriendly(int start, int end, int[] a) {
for (int i = start + 1; i <= end; i++)
if (!friendly(a[start], a[i]) return false;
return true;
}
```

To test if two numbers are friendly, we need to find the set of digits in each number. Here is one way of doing this:
```    int[] digits(int x) {
int[] ret = new int[10];
if (x == 0) ret[0] = 1;
else {
while (x != 0) {
ret[x % 10] = 1;
x /= 10;
}
}
return ret;
}
```
ret[i] will be 1 if x contains the digit i, and 0 otherwise.

Testing the friendlyness of two numbers is easy now:
```    boolean friendly(int x, int y) {
int[] a = digits(x);
int[] b = digits(y);
return Arrays.equals(a, b);
}
```

QueenCovering
Used as: Division One - Level Two:
 Value 500 Submission Rate 123 / 300 (41.00%) Success Rate 102 / 123 (82.93%) High Score Krzysan for 434.66 points (11 mins 22 secs) Average Score 286.70 (for 102 correct submissions)

To solve this problem we can simply try every possible valid queen placement on the board, and check if the configuration covers all the cells on the board. One way of doing this is the following:

```    boolean ok() {
for (int i = 0; i < 8; i++) {
if (row[i]) continue;
for (int j = 0; j < 8; j++) {
if (b[i].charAt(j) == '.') {
if (column[j] || firstDiagonal[i - j + 7] || secondDiagonal[i + j]) return false;
}
}
}
return true;
}

void back(int curRow, String curSol) {
if (curRow == 8) {
if (!ok()) return;
if (curSol.length() < sol.length() ||
(curSol.length() == sol.length() && curSol.compareTo(sol) < 0))
sol = curSol;
return;
}
for (int i = 0; i < 8; i++) {
if (!column[i] && !firstDiagonal[curRow - i + 7]
&& !secondDiagonal[curRow + i] && b[curRow].charAt(i) != '#') {

row[curRow] = true; column[i] = true;  firstDiagonal[curRow - i + 7] = true;
secondDiagonal[curRow + i] = true;

back(curRow + 1, curSol + (char)('1' + row) + (char)('A' + i));

row[curRow] = false; column[i] = false; firstDiagonal[curRow - i + 7] = false;
secondDiagonal[curRow + i] = false;
}
}
back(curRow + 1, curSol);
}
```
The boolean arrays row, column, firstDiagonal and secondDiagonal keep information about which rows, columns and diagonals have a queen placed on them. This makes the process of finding a configuration where the queens don't attack one another easier, and also make the last verification step more efficient.

SnowStorm
Used as: Division One - Level Three:
 Value 1050 Submission Rate 9 / 300 (3.00%) Success Rate 3 / 9 (33.33%) High Score reid for 524.49 points (37 mins 34 secs) Average Score 470.65 (for 3 correct submissions)

This problem is a bit harder than the usual div 1 1000. The problem asks the solver to find the number of different connected subgraphs of a given graph G, with the set V of vertices, and the set E of edges, so that the subgraphs contains all vertices in V. The fact that n is smaller than 16 suggests that an exponential solution is possible. One approach would be to try finding num[V'], where V' is a subset of V and num[V'] is the number of connected subgraphs of G that have as vertices the nodes in V'. Also let e[V'] be the number of subgraphs of G, with the vertex set V'. e[V'] is easy to find because if we have m edges between the vertices of V' in the original graph, then for each edge we have two possibilities, adding it or not adding it to a subgraph, so e[V'] = 2m.

Now suppose we want to find num[V'], and we know e[V'] and also num[V"] and e[V"] for every subset V" of V'. Having this data, it's easier for us to compute the number of disconnected subgraphs of G with the vertex set V'. Let v be the vertex with the largest index in V'. Now for a subgraph G' of G that contains the vertices V' to be disconnected we have to have v in one connected component, and the other vertices in different components, so we have to split V' in two sets of nodes V1 and V2. We also need a connected subgraph with the nodes V1 and another subgraph with the nodes V2. This way we can find that the number of disconnected subgraphs with the vertice set V' is equal to the sum of num[V1] * e[V2] for every possible way of splitting V' in sets V1 and V2 so that V1 contains the node v.

To find the connected graphs we just need to substract the previous number from e[V']. So we have the recurrence formula num[V'] = e[V'] - sum num[V1] * e[V2]. This solution has the complexity O(3n + n * 2n) because we can iterate through the sets and subsets in the problem by going through numbers 0 to 3n - 1. The digits that are not 0 in the current number correspond to the vertices of V', and digits 1 and 2 correspond to vertices in V1 and V2, respectively.

One way of implementing the above would be this:

```    void doit(int x, int b1, int b2, int l) {
if (x == n) {
if (l == 2)
num[b1 | b2] = (10000 + num[b1 | b2] - (e2[b1] * num[b2])) % 1000;
} else {
doit(x + 1, b1, b2, l);
doit(x + 1, b1 | (1 << x), b2, 1);
doit(x + 1, b1, b2 | (1 << x), 2);
}
}
public int countWays(String[] paths) {
n = paths.length;
num = new int[1 << n];
e2 = new int[1 << n];
for (int i = 0; i < (1 << n); i++) {
for (int j = n - 1; j  >= 0; j--) {
if ((i & (1 << j))!= 0) {
if (i == (1 << j)) {
num[i] = 1;
e2[i] = 1;
} else {
num[i] = num[i & ~(1 << j)];
for (int j1 = j - 1; j1 >= 0; j1--) {
if ((i & (1 << j1))!= 0) {
if (paths[j].charAt(j1) == 'Y') {
num[i] = (2 * num[i]) % 10000;
}
}
}
e2[i] = num[i];
}
break;
}
}
}
doit(0, 0, 0, -1);
return num[(1 << n) - 1] % 10000;
}
```

By Cosmin.ro
TopCoder Member