Match Editorial

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

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.

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)

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.

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.

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 3¹² = 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.

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 c_ij/2 times and will be removed from this cell c_ij/2 times. If A[i][j]='0' and B[i][j]='1' then '1' will be put into this cell (c_ij-1)/2+1 times and removed (c_ij-1)/2 times. If A[i][j]='1' and B[i][j]='0' then '1' will be put into this cell (c_ij-1)/2 times and removed (c_ij-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: v_i1, v_i2, v_i3. All ones, represented by flow, coming to cell i will come to vertex v_i1, and all ones leaving cell i will go through vertex v_i3. If i-th cell contains '1' at the beginning, we add the edge from source to v_i2 with unit capacity and zero cost. If i-th cell has to contain '1' after the transformation we add the edge from v_i2 to sink with unit capacity and zero cost. We also add edge from v_i1 to v_i2 with capacity equal to the limit for times '1' can be put into cell i and zero cost and the edge from v_i2 to v_i3 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 v_i3 to v_j1 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 v_i3 (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.