JOIN
 Match Editorial
SRM 407
Thursday, June 26, 2008

## Match summary

This round match attracted 1374 coders, 584 Div1 and 790 Div2. In Div1 most of the coders successfully submitted easy and medium in first 30 minutes and spent all the remaining time for solving the hard. jbernadas got the first place with the fastest submission for the hard. He was VERY closely followed by wywcgs who made 7 successful challenges on the easy. The third place went to ACRush .

Div2 competition ended up with iburmistrov, tt_dkhoa and sunny87 on the top three places.

# The Problems

SpiralWalking
Used as: Division Two - Level One:
 Value 250 Submission Rate 383 / 790 (48.48%) Success Rate 328 / 383 (85.64%) High Score tripshock for 219.46 points (10 mins 54 secs) Average Score 133.31 (for 328 correct submissions)

The solution was just an implementation of the algorithm described in the statement: walk forward until you hit the boundary of the level or already visited cell (in such case turn right). Summarize prices for all the cells except those where you made turns.

CorporationSalary
Used as: Division Two - Level Two:
 Value 500 Submission Rate 339 / 790 (42.91%) Success Rate 159 / 339 (46.90%) High Score tt_dkhoa for 469.50 points (7 mins 20 secs) Average Score 342.58 (for 159 correct submissions)
Used as: Division One - Level One:
 Value 250 Submission Rate 578 / 584 (98.97%) Success Rate 438 / 578 (75.78%) High Score ACRush for 247.62 points (2 mins 47 secs) Average Score 216.76 (for 438 correct submissions)

The only question which appeared was: in which order do we have to count salaries of the employees to be sure that we already know the salary for all direct subordinates of the current employee? The constraints told that given relations graph would have no cycles. It's known that each directed graph having no cycles can be sorted topologically. So the solution becomes really simple: sort the given graph topologically (using depth-first search) and then simply count the salary for each employee and sum these values.

Due to small limitations for the number of employees there was other approach which became quite popular in division 2: on each step find the employee for whom the salaries of all his direct subordinates are known and count his salary, repeat this until all the salaries are known.

CheapestRoute
Used as: Division Two - Level Three:
 Value 1000 Submission Rate 38 / 790 (4.81%) Success Rate 4 / 38 (10.53%) High Score iburmistrov for 569.18 points (30 mins 0 secs) Average Score 472.72 (for 4 correct submissions)

As cost of teleport usage depends on number of teleports used before, number of a current cell isn't enough to define current position. So we will use a pair (a,b), where a is a cell number and b is a number of teleports already used, to define our position in the corridor. The weight of a move can be defined by a pair (a,b), where a is a cost of this move and b is time needed for this move. As we are looking for the cheapest route with as small number of moves as possible for such cost, the comparison for two moves will be defined as: (a,b) < (c,d) <=> (a<c) or ( (a=c) and (b<d) ). Now we can introduce the graph with vertices numbered as (a,b) (meaning of a and b is described above), representing our position in the corridor, and edges with weights given using pairs (also introduced above), representing walking and using teleports. Our goal is to find a path from vertex (0, 0) to vertex (n-1, i) (where i can take any value) with the minimum weight. This problem can be solved using any shortest-path algorithm. You can see the implementation of this idea here.

PointsGame
Used as: Division One - Level Two:
 Value 500 Submission Rate 422 / 584 (72.26%) Success Rate 299 / 422 (70.85%) High Score ACRush for 483.51 points (5 mins 16 secs) Average Score 318.73 (for 299 correct submissions)

From the fact that the number of points is not greater than 12 and that each point can be in 3 states (not colored, colored by first player, colored by second player) we can see that the number of game positions won't be greater than 312 = 531,441 so we can compute the best score which can be achieved for each position. For the position where all points are already colored we can easily compute its score. Let's look at the position where it's first (second) player's turn: if we color one of the uncolored points then we will receive the score equal to the score of new position, so using the fact that both players play optimally, we check all possibilities for the next cell to be colored and select the one which will give us maximum (minimum) points. You can see the recursive implementation of this idea here.

TransformMatrix
Used as: Division One - Level Three:
 Value 1000 Submission Rate 60 / 584 (10.27%) Success Rate 12 / 60 (20.00%) High Score jbernadas for 703.04 points (20 mins 21 secs) Average Score 491.99 (for 12 correct submissions)

First you have to notice that you will never swap two cells if they have same digits in them. So each swap is moving '1' from one cell to another. If A[i][j] = B[i][j] then '1' will be put into this cell cij/2 times and will be removed from this cell cij/2 times. If A[i][j]='0' and B[i][j]='1' then '1' will be put into this cell (cij-1)/2+1 times and removed (cij-1)/2 times. If A[i][j]='1' and B[i][j]='0' then '1' will be put into this cell (cij-1)/2 times and removed (cij-1)/2+1 times. Using this fact we can break the limitation for cell usage into two parts: the limitation for times '1' can be put into this cell and the limitation for times '1' can be removed from this cell.

Now let's build a network. For i-th cell we will add 3 vertexes: vi1, vi2, vi3. All ones, represented by flow, coming to cell i will come to vertex vi1, and all ones leaving cell i will go through vertex vi3. If i-th cell contains '1' at the beginning, we add the edge from source to vi2 with unit capacity and zero cost. If i-th cell has to contain '1' after the transformation we add the edge from vi2 to sink with unit capacity and zero cost. We also add edge from vi1 to vi2 with capacity equal to the limit for times '1' can be put into cell i and zero cost and the edge from vi2 to vi3 with capacity equal to the limit for times '1' can be removed from cell i and zero cost. If cells i and j are adjacent we will also add edge from vi3 to vj1 of infinite capacity and unit cost. Now let's find the minimum cost flow in our network. If the value of flow is less than number of ones, then matrix A can't be transformed into B, otherwise the cost of the found flow is the answer. You can see the implementation of this idea here.

Many coders solved the problem presenting each cell using not 3, but 2 vertexes. They removed vertices vi3 (removing the limitation for times '1' can be removed from cell i). This can be done because '1' can't be removed from cell more times than it was put there, so the limitation for times '1' can be put in the cell is enough. You can see the implementation of this idea here.

By Gluk
TopCoder Member