## Editorial for APIO '15 P2 - Jakarta Skyscrapers

**only**when stuck, and

**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.

**Submitting an official solution before solving the problem yourself is a bannable offence.**

#### Subtask 1

Due to the small constraint of this subtask, it is possible to do a breadth-first search, with the current positions of the doges as the state. From a state, there can be at most transitions, since each doge can either move left, right, or stay. The number of states is , since each doge can either have the news ( possible positions) or it does not have the news (it must be in its starting building). The complexity of this solution is .

#### Subtask 2

Note that for doge to find the news, there must be a sequence of doges such that doge got the news from doge , as the first doge to get the news, and . By using this observation, we can reduce the state to only keep track of one doge.

Now, we can optimize the BFS to only keep track of the position of the current doge, and the power of the current doge. The state becomes , and the number of vertices is at most . From each vertex, we can have two edges:

- Move: Connect to and .
- Move and pass the news to another doge: Connect to and .

From each vertex, there can be at most two edges of the first type and edges of the second type. The total number of edges is . Therefore, the complexity of this solution is .

#### Subtask 3

We can optimize this further by transforming the problem to a weighted graph. If we consider a series of jumps from one doge to another as one single edge, we can reduce the state to just . In other words, connect to with an edge of weight , if can be reached by in jumps. In the worst-case scenario, the graph is complete with edges. By running Dijkstra's algorithm on this graph, we get an solution.

#### Subtask 4

The problem with the solution of Subtask 2 is that if there are doges with different powers in building , every jump that can reach will need to connect with at least vertices. To reduce this number, we introduce a dummy entry vertex for each building. Every jump that can reach this vertex will connect to this dummy vertex with cost , and this dummy vertex will connect to every doge in the building with cost . In other words, if we write this new dummy vertex as ,

- Connect to and with an edge of weight .
- Connect to and with an edge of weight .
- Connect to for each doge with power in with an edge of weight .

Now, the number of vertices is still the same (), but the number of edges is reduced to edges from vertices, and edges from vertices. The complexity is .

#### Subtask 5

We still need to cut the number of vertices for this subtask. To do this, we combine the idea from subtask 3 and subtask 4:

Create vertices only for . From a vertex, we connect to vertex for doges with powers that are less than or equal to . If the power of the doge is more than , loop through the possible positions that this doge can jump to, either directly or indirectly, and connect to the entry vertex of those buildings. Now, the number of vertices is at most .

The number of edges can be analyzed as follows:

- There can only be two edges from a vertex connecting it to another vertex. The total number of these edges is at most .
- There can be one edge from each vertex connecting it to a vertex. The total number of these edges is at most .
- The number of edges from a vertex to a vertex is at most for each position, since there are only different values of power it can connect to. The total number of these edges is at most .
- The number of edges from a vertex to another vertex is bounded by the number of jumps for each doge. Each doge with power greater than can only jump at most times. The total number of these edges is at most .

Therefore, the number of edges is .

Running Dijkstra's algorithm in this graph gives an solution.

## Comments