Ghost Encounters

Source: AIO 2020

1. Read the problem and summarise the task requirements.
   • Try to keep your response to a couple of sentences.

Let’s analyse each ghost separately.

2. Given K, X_i and T_i, what starting time leads to an encounter with ghost i?

3. We’d now like to count the ghosts encountered by starting at various times. What data structure should you use?
   • Remember that the starting time can be of either sign and can be large in absolute value.

4. What is the time complexity of the algorithm? Using the constraints on the last page, estimate the running time.

5. Implement the algorithm in code.
   • Reflector:
     • What potential pitfalls can you think of?
     • Write some tests to check for these pitfalls.
   • Other group members:
     • Write a program which solves the problem.
   • Run your tests and debug if necessary.
6. Submit your program for judging!
   • Debug as required.