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 .
The ProblemsSpiralWalkingUsed as: Division Two  Level One:
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. CorporationSalaryUsed as: Division Two  Level Two: Used as: Division One  Level One:
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 depthfirst search)
and then simply count the salary for each employee and sum these values. Used as: Division Two  Level Three:
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 (n1, i) (where i can take any value) with the minimum weight. This problem can be solved using any shortestpath algorithm. You can see the implementation of this idea here. PointsGameUsed as: Division One  Level Two:
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^{12} = 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. TransformMatrixUsed as: Division One  Level Three:
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.

