Editorial for WC '15 Finals S5 - Supply Chain
Submitting an official solution before solving the problem yourself is a bannable offence.
One major step in solving this problem is the reduction to solving it for a line of pastures (starting with pasture ) rather than a cycle, which is much more manageable. Let's consider having two lines of
pastures each. The first line will consist of pastures
(made by removing bridge
), while the second will consist of pastures
(made by removing bridge
). If we compute the number of bananas delivered in each line and add these two values together, it may exceed the number of bananas delivered in the original cycle – but by how much? The only bananas which will be counted twice will be all of those delivered by trucks which are light enough to drive around the entire cycle in either direction – namely, the trucks whose weights are no larger than the minimum weight
supported by any bridge
. Therefore, if we can maintain this minimum value (which is easy) and be able to query the sum of the
values of trucks whose
values are no larger than it (which will be doable), we can go ahead and solve the problem for both of these lines independently, and then combine their answers!
Now that we're dealing with a line (let's say the first line, consisting of pastures to
in order), let
be the maximum truck weight that would be capable of reaching each pasture
. We have
, while
for
. Note that
is a non-increasing sequence. The number of bananas delivered to pasture
is then the sum of the
values of trucks whose
values are no larger than
. Handling each day independently, we can compute the
array in
time, and then compute the total number of bananas delivered on it efficiently in various ways. For example, we can consider each truck
in turn, use binary search to find the last pasture
that truck
can reach (i.e., the largest
such that
), and add
to our result. After computing the results for both lines, we must remember to subtract the double-counted bananas, which can be done by summing the bananas delivered by light-enough trucks in
time. This yields a solution with a running time of
. Similar
and
solutions are possible.
In order to optimize this approach, we'll need to be able to update the answer from day to day without re-computing it from scratch, which will require a couple of data structures to maintain and update useful information about the trucks and pastures.
Firstly, for the trucks, it seems useful to be able to query the sum of the values of trucks whose
values are no larger than some given value (for example, this is exactly what's required to compute the number of double-counted bananas each day). Fortunately, there exists a simple data structure which does exactly that – a binary indexed tree (also known as a Fenwick tree). We'll initialize the tree with each truck
by adding
to index
, and each time a truck
's weight changes from
to
, we'll subtract
from index
and add
to index
. We'll be querying this tree for the sum of the
values of trucks whose
values are no larger than some weight
– let's call this sum
. Each update and query on this tree will take
time, where
is the maximum possible truck weight (
).
Secondly, for the pastures in a line, we'll want a data structure to represent their corresponding array. Let's consider only the set of
"interesting" indices
at which
changes (decreases), plus a sentinel value of
. We then have an increasing list
such that each interval of indices
has a uniform
value, which means that each pasture in that interval will receive the same number of bananas (namely,
of them). To allow this list to be updated as necessary, we'll want to store it as a set (a balanced binary search tree) of pairs
, rather than maintaining the actual arrays
and
. This set is initialized in
by iterating over the pastures in order and inserting each one which is preceded by a bridge with a new minimum weight limit. Each time a bridge
's weight limit is reduced to
, this set can be updated in amortized
by potentially adding a point
, and deleting existing points
where
and
.
Now that both of these data structures are in place, let's consider how to use them to update each line's answer after each event. When a truck 's weight changes from
to
, we should determine how many pastures
are reachable by trucks with weight
and how many pastures
are reachable by trucks with weight
, and increase the answer by
. Each of these values can be looked up in our set in
time using binary search, or even in
time if we maintain an accompanying set of points searchable by
value (in other words a set of pairs
in addition to the set of pairs
). When a bridge's supported weight decreases and we insert and/or delete points from our set, some intervals of pastures with equal
values (that is, the intervals between adjacent indices in the set) will change, and we can update the answer accordingly. For example, if an interval of
pastures all have their
values reduced from
to
, we should decrease the answer by
. An amortized constant number of pasture intervals will change as a result of each such event, meaning that it can be handled in amortized
time. The total time complexity of this algorithm is
, where
is again the maximum possible truck weight.
Comments