Wednesday, September 26, 2007 Match summaryIn both divisions coders were faced by a quite balanced problem set. Almost all of the problems provided pretty good challenge opportunities. In Division 1 gozman took the lead after the coding phase and stayed on the top until the system testing. But his success rate (especially on the problems of the hard category) confirmed its relevance, and he fell from the muchdesired first place. Only 13 solutions of the hard problem passed the system tests, thus fortune rewarded good challengers and fast coders. ACRush won the match, gawry finished second, and third place went to Per. Spectators saw plenty of failed solutions in Division 2 as well. The number of failed solutions of the medium and hard problem was quite large; in some rooms, it was even possible to take the lead without a correct solution of the hard problem, as long as you had plenty of challenges. espr1t took first place without any challenges at all, thanks to a pretty high score on all of the problems. cytmike finished second with 3 successful challenges, with newcomer snguyen in third. The ProblemsWhiteCellsUsed as: Division Two  Level One:
All the rows of a chessboard divide into two categories: even and odd.
Within an even row, all cells located in even columns are white, while all
that are in odd columns are black. Within an odd row, all white cells are
located in odd columns, while blacks are in an even columns.
Thus, the cell is black if and only if its row and column numbers have the same parity.
struct WhiteCells { int countOccupied(vector <string> board) { int ret = 0; for (int i = 0; i < board.size(); i++) // j must have the same parity as i for (int j = i % 2; j < board[i].size(); j += 2) if (board[i][j] == 'F') ret++; return ret; } };ObtainingDigitK Used as: Division Two  Level Two: Used as: Division One  Level One:
This task asked coders to find the minimal possible number x that could be added to the given number a in such a way that their sum (a + x) contains at least one instance of a given digit k. Approach 1  Bruteforce Approach 2  Examining cases Most Division 1 coders used the first approach, thus avoiding a lot of pitfalls. Many Division 2 coders, however, ran into problems by using the second approach. ProgrammingDeviceUsed as: Division Two  Level Three:
The first thing to do here is to realize that we must send full packets only, because (in contrast to div 1 medium)
we need to minimize the number of packets, but not anything else. Also, we need to realize that there is no reason to
send any unimportant bytes (which don't belong to any of the given pieces) in the beginning of the packet, i.e. each
packet must begin with an important byte.
The second is to sort all the given pieces in ascending order of their offsets.
Once the mentoined sorting is done, we can easily iterate over pieces in the "from left to right" order
and greedily send as much data by one packet as possible. In order to fit under the 2 second running time
we need to use the following trick: determine the number of packets necessary to entirely cover the current piece,
and treat them all at once (which leads to O(n ^ 2) complexity, where n is the number of pieces) .
The desired number can be obtained by dividing the amount of unsent bytes of the current piece
by the maximal allowed size of the packet, rounding the result to the up.
struct ProgrammingDevice { int minPackets(vector <int> offset, vector <int> size, int maxData) { // pos  position of the first (leftmost) nonsent important byte long long pos, k; int ret = 0, n, i, j; n = offset.size(); // sort pieces for (i = 0; i < n; i++) for (j = i + 1; j < n; j++) if (offset[i] > offset[j]) { swap(offset[i], offset[j]); swap(size[i], size[j]); } i = 0; // begin from the leftmost piece // set the pos equal to the first important byte pos = offset[0]; // process until all important bytes are sent while (pos < offset[n  1] + size[n  1]) { // k  the number of packet neccessary tosend in order // to cover whole the current piece i k = (offset[i] + size[i]  pos + maxData  1) / maxData; ret += k; // always send a full packets pos += maxData * k; // find the leftmost piece which is not entirely sent yet for (; i < n; i++) if (pos < offset[i] + size[i]) break; // skip all contiguous unimportant bytes located to the left of the piece i if (i < n && pos < offset[i]) pos = offset[i]; } return ret; } };DeviceProgramming Used as: Division One  Level Two:
Both approaches to solving this one are based on the idea of dynamic programming and assume that pieces are previously sorted in ascending order of their offsets. The following symbols are used:
Approach 1 Approach 2 Java code of the very elegant solution by ivan_metelsky illustrates the second approach: public class DeviceProgramming { public long getSize(long maxPacketSize, long overhead, long size) { long maxInfo = maxPacketSize  overhead; long packetsNeeded = (size % maxInfo == 0 ? size / maxInfo : size / maxInfo + 1); return size + packetsNeeded * overhead; } public long minBytes(int[] offset, int[] size, int maxPacketSize, int overhead) { int N = offset.length; int[] st = new int[N], fn = new int[N]; for (int i=0; i < N; i++) { st[i] = offset[i]; // beginning of the piece fn[i] = offset[i] + size[i]  1; // end of the piece } // sort the pieces for (int i=0; i+1 < N; i++) for (int j=0; j+1 < N; j++) if (st[j] > st[j+1]) { int tmp = st[j]; st[j] = st[j+1]; st[j+1] = tmp; tmp = fn[j]; fn[j] = fn[j+1]; fn[j+1] = tmp; } long[] F = new long[N]; for (int i=0; i < N; i++) { // calculate the initial answer F[i] = getSize(maxPacketSize, overhead, fn[i]  st[0] + 1); for (int j=1; j <= i; j++) // try to move to state j F[i] = Math.min(F[i], F[j1] + getSize(maxPacketSize, overhead, fn[i]  st[j] + 1)); } return F[N1]; } }WSNParentsAssignment Used as: Division One  Level Three:
This is a max flow problem. There is a wireless sensor network (WSN) graph shown in figure 1 and its corresponding flowgraph in figure 2. Vertices of the WSNgraph are devices and a control center of the WSN. Edge from vertex i to vertex j exists if and only if the device corresponding to vertex i can transmit data directly to the device corresponding to vertex j. Edge from the vertex i to the vertex, corresponding to the control center, exists if and only if the device corresponding to vertex i can trasmit directly to the control center. Building a flowgraph is a much more sophisticated task. It requires accomplishing the following steps (assuming that the flowgraph is initially empty):
Once the minimal network's burden level is found, the parents vector should be built. This task can be solved by greedy algorithm combined with a bruteforce. Iterate over the device in ascending order of their indices and find the minimal possible index of its parent, which leads to the minimal network's burden level equal to the previously found minima, using a bruteforce. Once it is declared that device j is the parent of device i, edge from the "right half" of device i should be removed and the capacity of the edge from the "left half" of device j to the "right half" of device i should be decreased by 1. 
