Algorithm Round 3 Saturday, September 15, 2007 Match summaryOnline Round 3 of the 2007 TopCoder Collegiate Challenge brought us something to think, something to code and a huge space for possible bugs. What else does a top coder need on a Saturday morning (or day, or night)? As a result, the cutoff was quite low  175 points  so a fast, correct solution on the easy or 3.5 challenges were enough to advance. The round was won by Petr with a really improbable score on the hard problem, followed by pashka, marek.cygan, kalinov and ACRush. The ProblemsLazyCatUsed as: Division One  Level One:
This problem can be solved with a greedy algorithm. Mice are running away from the cat, so each of them is available for the first a[i] seconds only. It's always better to catch the mouse that will be available for less time with the hat that need less time to rest. The code follows: public int maxMiceCount(int[] pos, int[] speed, int d, int[] rest) { int n = pos.length; int[] a = new int[n]; for (int i = 0; i < n; i++) { a[i] = 0; while (pos[i] <= d) { a[i]++; pos[i] += speed[i]; } } Arrays.sort(a); int m = rest.length; Arrays.sort(rest); int t = 0; int res = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (a[j] > t) { res++; a[j] = 1; t += rest[i]; break; } } } return res; }TristripeBacteria Used as: Division One  Level Two:
This problem is quite technical. Coders need to find the easiest way to determine if the figure can be formed by three stripes. It is important in such problems to make the code short and easy and to avoid big copypaste parts. One easy way to do this is to use back tracking algorithms. First find the leftmost topmost cell of the bacteria. This cell should be the end of a stripe, horizontal or vertical. The stripe should be as long as possible. We can choose one of the variants, mark cells covered by the stripe and start back tracking on the remaining cells. Then unmark the cells, choose another variant and check it in the same way. The code follows: int n; int m; boolean[][] a; boolean[][] b; int[][] c; public int howMany(String[] photo) { n = photo.length + 2; m = photo[0].length() + 2; a = new boolean[n][m]; b = new boolean[n][m]; c = new int[n][m]; for (int i = 0; i < photo.length; i++) { for (int j = 0; j < photo[i].length(); j++) { a[i + 1][j + 1] = photo[i].charAt(j) == '*'; } } int res = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (a[i][j]) { clear(b); dfs(i, j); if (bt(0)) { res++; } } } } return res; } private boolean bt(int q) { if (q > 3) return false; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (b[i][j] && c[i][j] == 0) { int ii = i; while (b[ii][j]) { c[ii][j]++; ii++; } if (bt(q + 1)) return true; ii = i; while (b[ii][j]) { c[ii][j]; ii++; } int jj = j; while (b[i][jj]) { c[i][jj]++; jj++; } if (bt(q + 1)) return true; jj = j; while (b[i][jj]) { c[i][jj]; jj++; } return false; } } } return true; } private void clear(boolean[][] a) { for (boolean[] b : a) { Arrays.fill(b, false); } } private void dfs(int i, int j) { if (!a[i][j]) return; a[i][j] = false; b[i][j] = true; dfs(i  1, j); dfs(i + 1, j); dfs(i, j  1); dfs(i, j + 1); }SimilarPairs Used as: Division One  Level Three:
Let's call the substrings we need to find the "interesting substrings." It's shorter then "strings that belong to at least one such pair." First we need to understand that all substrings of an interesting substring are interesting too. So, for each i there is a t[i], the longest interesting substring starting from ith character. All other interesting substrings starting from the ith character are prefixes of t[i]. How to calculate t[i]? Each interesting substring has a pair. Let's find it. We can check all pairs (i, j) and calculate r[i][j], the maximal length of matching substrings, starting from ith and jth characters. This can be done easily using n^3 time, but it's too much. We can make it faster using this simple idea: if we know the number of characters that differ in substrings [i..i+k] and [j..j+k], then we can calculate this number for substrings [i+1..i+k] and [j+1..j+k]. So we can use the value of r[i][j] to calculate the value of r[i+1][j+1] and make all calculations using n^2 time. Look at kalinov's solution for an implementation of this idea. Now finally we need to count the number of different interesting substrings. This is a problem too, because we have too many substrings, and we cannot just put them into the hash set. First solution (correct): All interesting substrings are prefixes of t[i]. Sort t[i] lexicographically, their common prefixes are now together and it is easy to skip them. Look at kalinov's solution for implementation. Second solution (actually incorrect but useful): We can calculate the hash function of all interesting substrings as longs, sort this values and find the number of different. This solution fails if there are two different interesting substrings with same hash, but it happens not very often. Look at Petr's solution for implementation. 
