Antennas
Contest: SWERC 2021-2022 - Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Tags: data structures, dfs and similar, graphs, graphs, implementation, implementation, shortest paths, shortest paths

There are $$$n$$$ equidistant antennas on a line, numbered from $$$1$$$ to $$$n$$$. Each antenna has a power rating, the power of the $$$i$$$-th antenna is $$$p_i$$$.

The $$$i$$$-th and the $$$j$$$-th antenna can communicate directly if and only if their distance is at most the minimum of their powers, i.e., $$$|i-j| \leq \min(p_i, p_j)$$$. Sending a message directly between two such antennas takes $$$1$$$ second.

What is the minimum amount of time necessary to send a message from antenna $$$a$$$ to antenna $$$b$$$, possibly using other antennas as relays?

Input format:
Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1\le t\le 100\,000$$$) — the number of test cases. The descriptions of the $$$t$$$ test cases follow.

The first line of each test case contains three integers $$$n$$$, $$$a$$$, $$$b$$$ ($$$1 \leq a, b \leq n \leq 200\,000$$$) — the number of antennas, and the origin and target antenna.

The second line contains $$$n$$$ integers $$$p_1, p_2, \dots, p_n$$$ ($$$1 \leq p_i \leq n$$$) — the powers of the antennas.

The sum of the values of $$$n$$$ over all test cases does not exceed $$$200\,000$$$.

Output format:
For each test case, print the number of seconds needed to trasmit a message from $$$a$$$ to $$$b$$$. It can be shown that under the problem constraints, it is always possible to send such a message.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Note:
In the first test case, we must send a message from antenna $$$2$$$ to antenna $$$9$$$. A sequence of communications requiring $$$4$$$ seconds, which is the minimum possible amount of time, is the following:

- In $$$1$$$ second we send the message from antenna $$$2$$$ to antenna $$$1$$$. This is possible since $$$|2-1|\le \min(1, 4) = \min(p_2, p_1)$$$.
- In $$$1$$$ second we send the message from antenna $$$1$$$ to antenna $$$5$$$. This is possible since $$$|1-5|\le \min(4, 5) = \min(p_1, p_5)$$$.
- In $$$1$$$ second we send the message from antenna $$$5$$$ to antenna $$$10$$$. This is possible since $$$|5-10|\le \min(5, 5) = \min(p_5, p_{10})$$$.
- In $$$1$$$ second we send the message from antenna $$$10$$$ to antenna $$$9$$$. This is possible since $$$|10-9|\le \min(5, 1) = \min(p_{10}, p_9)$$$.

Example input:
3
10 2 9
4 1 1 1 5 1 1 1 1 5
1 1 1
1
3 1 3
3 3 1

Example output:
4
0
2

Editorial:
Let's model the problem as an undirected graph, where the vertex $$$i$$$ corresponds to the antenna $$$i$$$ and vertices $$$i$$$ and $$$j$$$ are connected with an edge if and only if the corresponding antennas are able to communicate directly, that is $$$|i - j| \leq \min(p_i, \, p_j)$$$. In this formulation, the answer to the question posed in the problem statement is simply the shortest distance between $$$a$$$ and $$$b$$$.
To compute the shortest distance, we would like to be able to construct the graph and run a breadth-first search. Unfortunately, we cannot afford to do that, as the number of edges can be in the order of $$$n^2$$$. We need a more efficient approach. We examine two options.
Improving the BFS
The inefficiency of a breadth-first search on a dense graph lies in the fact that the majority of the traversed edges lead to a vertex that has already been visited. Ideally, for every vertex, we would like to process only one of the incoming edges. Should we achieve this property, the running time would be linear in the number of vertices, not in the number of edges.
Let's decompose each edge into two directed edges, one in each direction. As soon as we traverse the first edge incoming to a particular vertex, we remove all other edges incoming to this vertex. This idea leads to the desired property of only processing each vertex once, nevertheless on its own it doesn't affect the time complexity as we still generate the full graph.
Let's consider for a brief moment how can we generate the graph in the first place. A naïve approach is to consider, for a fixed $$$i$$$, all $$$1 \leq j \leq n$$$ and check whether $$$i$$$ and $$$j$$$ can communicate with each other. However, we can observe that we do not need to test all $$$j$$$'s up to $$$n$$$ — it is sufficient to only iterate up to $$$\min(n, \, i + p_i)$$$, because $$$|i - j| = j - i \leq p_i$$$ must hold. Similarly, a tighter lower bound for the iteration is $$$\max(1, \, i - p_i)$$$ instead of $$$i$$$.
We can do even better than that. Define $$$l_j := j - p_j$$$. For $$$j \in(i, \, i + p_i]$$$ to be able to communicate with $$$i$$$, we just need $$$l_j \leq i$$$. Similarly, for $$$j \in [i - p_i, \, i)$$$ we need $$$r_j := j + p_j \geq i$$$. To summarise, we need to find all $$$j \in [i - p_i, \, i)$$$ such that $$$r_j \geq i$$$ and all $$$j \in (i, \, i + p_i]$$$ such that $$$l_j \leq i$$$. We can do this by storing the values $$$r_j$$$ and $$$l_j$$$ in two segment trees that return the minimum and maximum on a queried interval, respectively, together with the index where this minimum or maximum is achieved, and querying the appropriate interval as long as the inequality $$$r_j \ge i$$$ or $$$l_j \le i$$$ holds. Now, recall the previous idea — removing all edges incoming to a vertex once we find its distance from $$$a$$$. In this implementation, we can achieve this in $$$\mathcal O(\log n)$$$ time by simply setting the corresponding $$$l_j$$$ to $$$\infty$$$ and $$$r_j$$$ to $$$-\infty$$$.
Using these techniques, we can process a vertex in $$$\mathcal O(d\log n)$$$, where $$$d$$$ is the out-degree of the vertex when we are processing it. Since, for each vertex, we only process at most a single incoming edge, the total running time is $$$\mathcal O(n\log n)$$$.
Iterating on a restricted problem
Let us consider a restricted version of the problem. In this version, antenna $$$i$$$ is allowed to send a message to $$$j$$$ if $$$|i - j| \leq \min(p_i, \, p_j)$$$ and $$$i < j$$$. In other words, a message can only be sent to an antenna with a strictly larger index, and never in the opposite direction. This problem can be solved by a single sweep, as follows.
Maintain a segment tree $$$S$$$ of size $$$n$$$, that returns the minimum on an interval, and supports single element update. We process the antennas in order of increasing index. When processing an antenna $$$i$$$, we do the following operations:
• Set $$$S[i] = \mathrm{dist}[i]$$$ where $$$\mathrm{dist}[i]$$$ is the length of the shortest known path from $$$a$$$ to $$$i$$$. Initially $$$\mathrm{dist}[a] = 0$$$, and all other values are initialised to $$$\infty$$$.
• For all antennas $$$j$$$ such that $$$j + p_j - 1 = i$$$ (i.e. $$$j$$$ is able to reach $$$i - 1$$$ but not $$$i$$$), set $$$S[j] = \infty$$$.
• Set $$$\mathrm{dist}[i] = 1 + S.\mathrm{min}(i-p_i, \, i)$$$.
The purpose of removing an antenna by setting $$$S[j] = \infty$$$ is evident — as the antennas are processed in order of increasing indices, we know that none of the antennas to be processed can communicate with $$$j$$$. The complexity of this algorithm is $$$\mathcal O(n \log n)$$$. Note that it is trivial to modify this algorithm for a version of the problem where all communication goes to antennas with a lower index instead.
How does this help to solve our original problem? We can alternate between the two versions — the one that only allows communication towards antennas with larger indices (i.e. to the right), and the one with smaller ones (i.e. to the left). This process is repeated while the array $$$\mathrm{dist}$$$ is changing. Once a fixed state is reached, we have a correct solution.
We argue that only $$$\mathcal O(\log n)$$$ iterations of this outer loop will be performed, in other words there exists a shortest path that "changes direction" at most $$$\mathcal O(\log n)$$$ times. The basic idea of the proof is that when two successive direction changes are performed, the distances between antennas at least doubled, otherwise there would exist a path of a shorter or equal length with fewer direction changes. The details of the proof are left as an exercise to the reader.
All things considered, this yields an $$$\mathcal O(n\log^2 n)$$$ algorithm, which is sufficient given a careful implementation.