Editorial for DMOPC '22 Contest 2 P6 - Yogyakarta Elevators

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.

Author: Dormi

Any contiguous subsequence of floors that contains a floor with zero elevators is not reachable. Thus, we will only consider contiguous subsequences in which every floor contains at least one elevator.

Define E as the set of elevators which stop within a contiguous subsequence of floors [l, r]. Notice that [l, r] is reachable if and only if starting from every elevator in E, it is possible to reach all other elevators in E. In other words, if we consider each floor as a set of edges between all pairs of elevators that stop at it, [l, r] is reachable if and only if E is a connected graph with edges within [l, r].

Rephrasing the question, each floor represents a set of elevators (V_i) and edges between elevators (E_i), and we want to find the largest contiguous subsequence [l, r] such that G = \left(\bigcup\limits_{i=l}^r V_i, \bigcup\limits_{i=l}^r E_i\right) contains exactly one connected component.


  • Notice that because we only care about connectivity, instead of needing \mathcal{O}(M^2) edges for each floor, we can use \mathcal{O}(M) edges, connecting each elevator on the floor to the leftmost elevator on that floor.
  • Notice that starting at each floor l, the connected components in G for all r \in [l, n] only changes at most 2M-1 times, M times for each introduced elevator, and M-1 times for each edge that connects two distinct components. Thus, for each floor l, there are at most 2M-1 important r floors where the number of connected components changes. In particular, we only care about the first time each elevator appears and the first M-1 edges which connect distinct components.
  • Let S_i be the first edges which connect distinct components in [i, n]. Notice that \forall i \in [1, N-1], S_i \subseteq V_i \cup S_{i+1}.


Line sweep from N to 1, at each floor l maintaining:

  • The earliest appearance of each elevator, in order of appearance. This can be done by adding the elevators which appear on floor l at the front of the list and then removing duplicates, taking \mathcal{O}(M) time.
  • The first M-1 edges which connect distinct components. As V_l, S_{l+1} each contains at most M edges, we can just create a new DSU and add all of the edges in order, noting the edges which connect distinct components, taking \mathcal{O}(M*\alpha(M)) time.

Then at each floor, add the important edges and elevators to a DSU in order. If at any point G contains only one connected component, the r floors after the current update and before the next update creates a reachable contiguous subsequence with l and thus should be considered in the final answer. In total, this takes \mathcal{O}(M*\alpha(M)) time.

Note: Special care should be taken for floors with zero elevators so that we don't consider contiguous subsequences which include them.

Time Complexity: \mathcal{O}(NM*\alpha(M))


There are no comments at the moment.