International Olympiad in Informatics 2011 Day 2 Solution

22–29 July 2011, Pattaya City, Thailand Task: Elephants

Task: Elephants
Proposed by: Mihai Pătraşcu

1 Subtask 1
In subtask 1, there are only two elephants. Thus we can easily determine the number of required
cameras in constant time. Namely, we only need one camera if the elephants are at most distance
L apart; otherwise, we need two cameras.

2 Subtasks 2 and 3
If elephants are at positions x0 , x1 , . . . , xN −1 , such that xi ≤ xi+1 for all 0 ≤ i < N − 1, we can
compute the minimum number of cameras required using a greedy algorithm. We start with an
empty set of cameras. While the current set of cameras do not cover all elephants, we choose
an elephant which is not already covered with the minimum position xj , and place a camera to
cover elephants at positions in [xj , xj + L]. We can implement this procedure to run in time
O(N ) by iterating through the list of sorted positions once.
Each time an elephant moves in the show, we can update the sorted list of positions in O(N )
time. Hence, we have an O(N M ) solution to this problem, which is sufficient to fully solve
subtask 2, and an adequate optimization is required to fully solve subtask 3. However, a faster
algorithm is required for subtasks 4 and 5.

3 Subtasks 4 and 5
3.1 Bucketing elephants
To find the number of cameras, instead of iterating through all elephants, we shall build a data
structure that allows us to “jump” over lots of elephants.
We maintain k buckets B0 , B1 , . . . , Bk−1 of elephants such that buckets with lower indices
store elephants with lower positions, i.e., for any 0 ≤ b < k − 1, for all xi ∈ Bb and xj ∈ Bb+1 ,
xi ≤ xj . Also, elephants in each bucket are sorted according to their positions.
The goal is to make sure that to find the number of required cameras, one needs to visit each
bucket once. For simplicity, we will always place cameras so that the left-most position covered
by a camera is the position of some elephant.
Consider bucket b with p elephants. Denote the list of indices of elephants in Bb as e0 , e1 , . . .,
ep−1 (that is, xei ≤ xei+1 ). Given an elephant ei , we would like to answer the following two
questions quickly:

1
International Olympiad in Informatics 2011 Day 2 Solution
22–29 July 2011, Pattaya City, Thailand Task: Elephants

• Q1: If we would like to cover all elephants starting from ei (i.e., elephants in the set
{ei , ei+1 , . . . , ep−1 }), how many cameras are needed?
• Q2: What is the highest position that these set of cameras cover?
For elephant e, denote the answer for Q1 for as J(e) and the answer to Q2 as T (e).
If we have these answers for every elephant in every bucket, we can find the number of
cameras in time O(k log N ) as follows.
We start by placing the camera at the first elephant in bucket B0 , so that the position of
this elephant is the left-most position covered by this camera. Now consider placing a camera at
elephant e in bucket Bi in the same fashion. We know that to cover all elephants in Bi , we have
to use J(e) cameras and these cameras cover positions up to T (e). We find the first elephant e0
not covered by these cameras in the next bucket Bi+1 by binary searching for the elephant in
Bi+1 whose position is minimum but greater than T (e). Then, we start placing the camera at
elephant e0 in bucket Bi+1 .
We repeat this step until we reach the last bucket. Since each step runs in O(log N ) time
(from binary search), we spend O(k log N ) time as required.
We can precompute the answers for Q1 and Q2 for elephants in Bi in O(|Bi |) time by iterating
over each elephant ej from ep−1 to e0 and keeping a pointer to the first elephant outside the
range xej + L. For implementation details, please see the appendix.
It is crucial to note that we can process each bucket independent of all other buckets.

3.2 Updating the data structure

When an elephant e moves, we will have to update two buckets: the current bucket Bi and the
new bucket Bj . This can be done in time proportional to the current size of the bucket. To find
the current bucket of e we can store a pointer from e, but it takes O(k) to find the new bucket
anyway. Therefore, the running time for the update is O(k + |Bi | + |Bj |).
Note that the time depends heavily on the size of each bucket. Initially, we would have about
N/k elephants in each bucket, but the number may grow as elephants can move. To keep the
size of each bucket bounded above by O(N/k), we will rebuild the whole data structure for every
dN/ke updates. The rebuilding takes time O(N ).

3.3 Choosing the right parameter

We need to handle M updates and answer one question after each of these updates. The total
running time is
O(M · k log N ) + O(M · (k + N/k)) + O(M · (N/(N/k))),
where the first term denotes the total query time, the second term denotes the total updating
time, and the last √
term denotes the total rebuilding time.
√
Choosing k = N gives the running time of O(M N log N ), which is sufficient to obtain
full marks for this problem. However, an inefficient implementation may not be able to solve
subtask 5. For example, using the set data structure in the C++ Standard Template Library
can introduce an extra factor of log n to the running time of rebuilding the data structure. This
can be avoided by using simple arrays.

2
International Olympiad in Informatics 2011 Day 2 Solution
22–29 July 2011, Pattaya City, Thailand Task: Elephants

A Processing each bucket

To simplify the presentation, we add a dummy elephant ep at position xep−1 + L + 1. Also, we
let yj = xej be the position of the j-th left-most elephant in bucket Bi .
We consider each elephant j from the right-most elephant ep−1 to the left-most one. We also
maintain an index t that points to the left-most elephant et whose position yt > yj + L. Initially,
j = p − 1 and t = p.
For each elephant ej , we will compute J(ej ) and last(ej ), the left-most elephant in the
right-most camera in the set of cameras covering {ej , ej+1 , . . . , ep }.
For the dummy node, we let J(ep ) = 0 and last(ep ) = ep . For elephant ej , we check if we
need to move t, i.e., if the position of et−1 is greater than yj + L; if that’s the case we find the
smallest t such that yt > yj + L. We let J(ej ) = J(et ) + 1 and last(ej ) = last(et ).
Finally, for each elephant ej such that last(ej ) points to the dummy elephant ep , we change
last(ej ) to ej .
We can complete the process using only one pass over all elephants in the bucket Bi and
note that the pointer t moves over each elephant only once. Thus, the running time is O(|Bi |)
as claimed.
To answer question Q2 for each elephant ej , we report ylast(ej ) + L.