Qualification Round 3 Wednesday, February 13, 2008 (rescheduled from Tuesday, February 12, 2008) Match summary1051 coders fiercely competed for their last chance to advance to round 1 in the final qualification match of the 2008 TCO. The match was won by LemonTree with fast submissions on all three problems and no help from the challenge phase. Second place went to gusakov who was aided by two challenges, and halyavin rounded out the top 3. Special recognition goes to division 2 coder stephanie, who finished 5th place in a difficult field of competitors. The problem difficulties seemed to lie somewhere in between the first and second qualification rounds, with a fast easy being enough to advance to round 1. However, some competitors were caught offguard with a medium that required some algorithmic knowledge, while over 120 people solved the hard problem, which required more brains than fast fingers. The ProblemsSquareConstructionUsed as: Division One  Level One:
This problem can be solved with a simple simulation. That is, we just iterate through positions as described in the problem statement, making sure that we correctly "wrap around" the edges of the square if necessary. While Java, C#, and VB users can simply concatenate numbers together to form a string for a return element, C++ uses must either make use of the sprintf() function or stringstreams. A C++ solution to this problem follows: int grid[11][11]; vector <string> SquareConstruction::construct(int N, int a, int b, int c, int d) { int y = 0, x = 0; int idx = 1; memset(grid, 1, sizeof(grid)); grid[y][x] = idx++; //simulate the process while (true) { y = (y + a) % N; x = (x + b) % N; if (grid[y][x] == 1) grid[y][x] = idx++; else { y = (y + c) % N; x = (x + d) % N; if (grid[y][x] == 1) grid[y][x] = idx++; else break; } } //format the result vector<string> ret; for (int i = 0; i < N; i++) { stringstream s; for (int j = 0; j < N; j++) { s << grid[i][j]; if(j + 1 < N) s << ' '; } ret.push_back(s.str()); } return ret; }CableDonation Used as: Division One  Level Two:
The crucial observation that allows us to solve this problem is found by realizing that after all the extra cable is removed, we're left with the minimum amount of cable that keeps our rooms connected.
Those familiar with graph theory will recognize this as the classic minimum spanning tree (aka MST) problem. That is, given a graph, we wish to find the set of edges with minimum weight such that every
vertex can reach every other vertex through some path. It's trivial to prove that such a subgraph will not contain any cycles (assuming all edge weights are positive); thus the resulting subgraph will be a tree that connects
each pair of vertices via some path (such a tree is known as a spanning tree). Our answer is then the sum of the edge weights in the input graph minus the sum of the weights of the MST. 1) while there are two vertices that are not connected by some path, do 2) find an edge of minimum weight that connects two vertices that are not connected by some path 3) add this edge to the minimum spanning tree 4) endWhile this algorithm can be implemented to have a much better time complexity, there is a very simple to implement and understand O(N^4) way to implement this algorithm, which works as follows: Define C[i][j] be 1 if vertex i is connected (directly or indirectly) to vertex j in the subgraph generated so far, and 0 otherwise. All C[i][j] are initialized to be 0. 1) while there are two vertices such that C[i][j]=0, do 2) find an edge of minimum weight that connects two vertices (call them i and j) such that C[i][j]=0 3) add this edge to the minimum spanning tree 4) let C[i][j]=C[j][i]=1 5) Use FloydWarshall's algorithm to update the C[i][j]'s, so that each pair of vertices a,b that are indirectly connected have C[a][b]=1 6) endNote that any MST will have exactly n1 edges, so if the outerwhile loop of our algorithm terminates in less than n1 iterations, then there is no MST, and we should return 1. In the above algorithm, FloydWarshall's algorithm is a simple algorithm that computes the allpairs shortest paths of a graph, and can be read about here. Note that we also could have used a simple depthfirst search to update the C[i][j]'s. A complete C++ implementation of this approach follows: int graph[51][51]; bool C[51][51]; const int BIG=1000000; int CableDonation::cable(vector <string> g) { int n = g.size(), sum = 0; //initialize the graph to not contain any edges for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) graph[i][j]=BIG; for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) { //if an edge is present, update our graph if (g[i][j] == '0') continue; if (islower(g[i][j])) graph[i][j] = g[i][j]  'a' + 1; if (isupper(g[i][j])) graph[i][j] = g[i][j]  'A' + 27; sum += graph[i][j]; } int mst = 0; int added = 0; //keep adding edges if possible. while (true) { int a = 1, b = 1, small = BIG; //find the edge of minimum weight that connects two "unconnected" vertices for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if(i != j && C[i][j] == 0) if (graph[i][j] < small) { small = graph[i][j]; a = i; b = j; } if (small == BIG) break; added++; mst += small; //these vertices are now connected C[a][b] = C[b][a] = 1; //use floydwarshall to update the C[i][j]'s for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) C[i][j] = C[i][k] & C[k][j]; } if (added != n  1) return 1; else return sum  mst; }Note that it is possible to implement Kruskal's algorithm in O(E log V) time. There is another algorithm called Prim's algorithm (which is very similar to Dijkstra's algorithm) that can also be implemented in O(E log V) time. EvenOnes Used as: Division One  Level Three:
This problem involved very little coding, as the main challenge to overcome was figuring out the mathematical logic behind it. The first thing we may wonder is why the input always consists of an odd number of rows and columns.
One important property that this restriction gives us is that if we, say, perform a move on a particular row, then the parity of the ones and zeros in that row is always changed, and the same holds for performing a move on a particular column.
When we talk about the parity of ones or zeros, we mean the property that the number of ones or zeros in a row or column is even or odd. From this property, we have two important observations:
First, we can perform moves on every bad row. If Br is even, then after performing our moves on the bad rows, the parity of ones in all the columns remains constant. Now we complete our task by performing moves on every bad column, and the total number of moves required is Br + Bc. However, if Br is odd, then the partity of ones in all the columns will change after performing the moves on the bad rows. Thus, all the good columns become bad columns, and viceversa. Therefore we must perform moves on all the originally good columns, and the total number of moves required is Br + Gc. The other possible solution is to perform moves on every good row. If Gr is even, then after performing our moves on the good rows, the parity of ones in all the columns remains constant similar to the above. We again complete the task by performing moves on every bad column, and the total number of moves required is Gr + Bc. However, if Gr is odd, then the partity of ones in all the columns will change after performing the moves on the good rows, so all the good columns become bad columns, and viceversa. Therefore we must perform moves on all the good columns, and the total number of moves required is Gr + Gc. Of course, there may be situations where after performing the required operations on the chosen rows and columns, that the resulting grid could still have some row or column with an odd number of ones. However, it can be shown that this situation can never happen, so we will never return 1. The proof of this fact is left as an exercise to the reader (hint: consider a casebycase analysis and a proof by contradiction). A sample C++ solution to this problem follows: int EvenOnes::minOperations(vector <string> mat) { int badrow = 0, badcol = 0; int n = mat.size(); int m = mat[0].size(); //get number of bad rows for (int i = 0; i < n; i++) { int ones = 0; for (int j = 0; j < m; j++) if (mat[i][j]=='1') ones++; if (ones % 2 == 1) badrow++; } //get number of bad cols for (int i = 0; i < m; i++) { int ones = 0; for (int j = 0; j < n; j++) if (mat[j][i] == '1') ones++; if (ones % 2 == 1) badcol++; } int a = 0, b = 0; //choose bad rows a = badrow; if (badrow % 2 == 1) a += m  badcol; else a += badcol; //choose good rows b = n  badrow; if ((n  badrow) % 2 == 1) b += m  badcol; else b += badcol; return min(a, b); } 
