|
Match Editorial |
Qualification Round 3
Wednesday, February 13, 2008
(rescheduled from Tuesday, February 12, 2008)
Match summary
1051 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 off-guard with a medium that required some algorithmic knowledge, while over 120 people solved the hard problem, which required more brains than fast fingers.
The Problems
SquareConstruction
Used as: Division One - Level One:
Value 250 Submission Rate 958 / 1040 (92.12%) Success Rate 917 / 958 (95.72%) High Score hysramp for 247.28 points (2 mins 59 secs) Average Score 194.24 (for 917 correct submissions)
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:
Value 500 Submission Rate 533 / 1040 (51.25%) Success Rate 339 / 533 (63.60%) High Score hysramp for 476.46 points (6 mins 22 secs) Average Score 312.19 (for 339 correct submissions)
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.
The simplest algorithm to grasp to solve this problem is Kruskal's algorithm, which works as follows:
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 Floyd-Warshall'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 n-1 edges, so if the outer-while loop of our algorithm terminates in less than n-1 iterations, then there is no MST, and we should return -1. In the above algorithm, Floyd-Warshall's algorithm is a simple algorithm that computes the all-pairs shortest paths of a graph, and can be read about here. Note that we also could have used a simple depth-first 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 floyd-warshall 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:
Value 1000 Submission Rate 175 / 1040 (16.83%) Success Rate 122 / 175 (69.71%) High Score nevenastan for 940.57 points (7 mins 13 secs) Average Score 650.07 (for 122 correct submissions)
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:
- If we perform a move on row i, the parity of ones in row i is changed, and the parity of ones and zeros in every column is changed.
- If we perform a move on column j, the parity of ones in column j is changed, and the parity of ones and zeros in every row is changed.
- If we perform an even number of moves on the set of rows, then the parity of ones and zeros in every column remains unchanged, otherwise it is changed.
- If we perform an even number of moves on the set of columns, then the parity of ones and zeros in every row remains unchanged, otherwise it is changed.
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 vice-versa. 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 vice-versa. 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 case-by-case 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);
}
