Editorial for APIO '15 P2 - Jakarta Skyscrapers

Remember to use this editorial 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 $M^3$ ~M^3~ transitions, since each doge can either move left, right, or stay. The number of states is $M^{N+1}$ ~M^{N+1}~, since each doge can either have the news ( $N$ ~N~ possible positions) or it does not have the news (it must be in its starting building). The complexity of this solution is $\mathcal O(M^{N+4})$ ~\mathcal O(M^{N+4})~.

Subtask 2

Note that for doge $1$ ~1~ to find the news, there must be a sequence of doges $x_1, x_2, \dots, x_k$ ~x_1, x_2, \dots, x_k~ such that doge $x_i$ ~x_i~ got the news from doge $x_{i-1}$ ~x_{i-1}~, $x_1 = 0$ ~x_1 = 0~ as the first doge to get the news, and $x_k = 1$ ~x_k = 1~. 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 $(\text{position}, \text{power})$ ~(\text{position}, \text{power})~, and the number of vertices is at most $NM$ ~NM~. From each vertex, we can have two edges:

Move: Connect $(\text{position}, \text{power})$ ~(\text{position}, \text{power})~ to $(\text{position}+\text{power}, \text{power})$ and $(\text{position}-\text{power}, \text{power})$ .
Move and pass the news to another doge: Connect $(\text{position}, \text{power})$ ~(\text{position}, \text{power})~ to $(\text{position}+\text{power}, \text{new_power})$ and $(\text{position}-\text{power}, \text{new_power})$ .

From each vertex, there can be at most two edges of the first type and $M$ ~M~ edges of the second type. The total number of edges is $\mathcal O(N^2 M)$ ~\mathcal O(N^2 M)~. Therefore, the complexity of this solution is $\mathcal O(NM^2)$ ~\mathcal O(NM^2)~.

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 $(\text{doge})$ ~(\text{doge})~. In other words, connect $\text{doge}_1$ ~\text{doge}_1~ to $\text{doge}_2$ ~\text{doge}_2~ with an edge of weight $w$ ~w~, if $\text{doge}_2$ ~\text{doge}_2~ can be reached by $\text{doge}_1$ ~\text{doge}_1~ in $w$ ~w~ jumps. In the worst-case scenario, the graph is complete with $\mathcal O(M^2)$ ~\mathcal O(M^2)~ edges. By running Dijkstra's algorithm on this graph, we get an $\mathcal O(M^2 \log M)$ ~\mathcal O(M^2 \log M)~ solution.

Subtask 4

The problem with the solution of Subtask 2 is that if there are $X$ ~X~ doges with different powers in building $Y$ ~Y~, every jump that can reach $Y$ ~Y~ will need to connect with at least $X$ ~X~ 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 $1$ ~1~, and this dummy vertex will connect to every doge in the building with cost $0$ ~0~. In other words, if we write this new dummy vertex as $(\text{position})$ ~(\text{position})~,

Connect $(\text{position}, \text{power})$ ~(\text{position}, \text{power})~ to $(\text{position}+\text{power}, \text{power})$ and $(\text{position}-\text{power}, \text{power})$ with an edge of weight $1$ ~1~.
Connect $(\text{position}, \text{power})$ ~(\text{position}, \text{power})~ to $(\text{position}+\text{power})$ ~(\text{position}+\text{power})~ and $(\text{position}-\text{power})$ ~(\text{position}-\text{power})~ with an edge of weight $1$ ~1~.
Connect $(\text{position})$ ~(\text{position})~ to $(\text{position}, \text{power})$ ~(\text{position}, \text{power})~ for each doge with power $\text{power}$ ~\text{power}~ in $\text{position}$ ~\text{position}~ with an edge of weight $0$ ~0~.

Now, the number of vertices is still the same ( $NM$ ~NM~), but the number of edges is reduced to $N$ ~N~ edges from $(\text{position})$ ~(\text{position})~ vertices, and $2NM$ ~2NM~ edges from $(\text{position}, \text{power})$ ~(\text{position}, \text{power})~ vertices. The complexity is $\mathcal O(NM)$ ~\mathcal O(NM)~.

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 $(\text{position}, \text{power})$ ~(\text{position}, \text{power})~ vertices only for $\text{power} \le \sqrt N$ ~\text{power} \le \sqrt N~. From a $(\text{position})$ ~(\text{position})~ vertex, we connect to $(\text{position}, \text{power})$ ~(\text{position}, \text{power})~ vertex for doges with powers that are less than or equal to $\sqrt N$ ~\sqrt N~. If the power of the doge is more than $\sqrt N$ ~\sqrt N~, 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 $\mathcal O(M \sqrt N)$ ~\mathcal O(M \sqrt N)~.

The number of edges can be analyzed as follows:

There can only be two edges from a $(\text{position}, \text{power})$ ~(\text{position}, \text{power})~ vertex connecting it to another $(\text{position}, \text{power})$ ~(\text{position}, \text{power})~ vertex. The total number of these edges is at most $2N \sqrt N$ ~2N \sqrt N~.
There can be one edge from each $(\text{position}, \text{power})$ ~(\text{position}, \text{power})~ vertex connecting it to a $(\text{position})$ ~(\text{position})~ vertex. The total number of these edges is at most $N \sqrt N$ ~N \sqrt N~.
The number of edges from a $(\text{position})$ ~(\text{position})~ vertex to a $(\text{position}, \text{power})$ ~(\text{position}, \text{power})~ vertex is at most $\sqrt N$ ~\sqrt N~ for each position, since there are only $\sqrt N$ ~\sqrt N~ different values of power it can connect to. The total number of these edges is at most $N \sqrt N$ ~N \sqrt N~.
The number of edges from a $(\text{position})$ ~(\text{position})~ vertex to another $(\text{position})$ ~(\text{position})~ vertex is bounded by the number of jumps for each doge. Each doge with power greater than $\sqrt N$ ~\sqrt N~ can only jump at most $\sqrt N$ ~\sqrt N~ times. The total number of these edges is at most $M \sqrt N$ ~M \sqrt N~.

Therefore, the number of edges is $\mathcal O((M+N) \sqrt N)$ ~\mathcal O((M+N) \sqrt N)~.

Running Dijkstra's algorithm in this graph gives an $\mathcal O((M+N) \sqrt N \log(M+N))$ ~\mathcal O((M+N) \sqrt N \log(M+N))~ solution.

Comments

There are no comments at the moment.