Online Round 1C September 27, 2006 Match summaryThe score distribution in this round seems similar to the ones in rounds 1A and 1B. 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 ProblemsFriendlySequencesUsed as: Division One  Level One:
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:
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:
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'] = 2^{m}.
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; } 
