Editorial for SCC25 Contest 1 P2 - Haunted Hallway
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.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Subtask 1 [30%]
This subtask was intended for brute force solutions that checked every pair of ghosts.
Time Complexity: \(O(N^{2})\)
Subtask 2 [70%]
Let ghost \(i\) have a velocity that is slower than any ghost in front of it. The main observation is that this ghost creates a "split", ensuring that the ghosts from \(i + 1\) to \(N\) never merge with the ghosts from \(1\) to \(i\).
It follows that sweeping from \(N\) to \(1\) and propogating the minimum velocity seen so far suffices.
Time Complexity: \(O(N)\)
Comments