Traffic Light

Source: Codeforces 1744C

1. Read the problem and summarise the task requirements.
   • Try to keep your response to a couple of sentences.
   • Note the guarantee that g and the specified colour both appear in the string; what does this imply?

Let’s solve one test case at a time; they are independent of each other. We’ll also start with just a single n-second period, and deal with the repetition later.

2. Consider a direct execution of the stated task: for every second of the specified colour, scan forward until the next green light, and report the maximum wait time.
   • Is it correct?
   • Analyse the time complexity of this algorithm in terms of n, the cycle length.
   • Estimate the running time of an implementation of this algorithm, and evaluate its feasibility.
3. How can we make this algorithm faster?
   • There are at least three viable approaches:
     1. don’t scan forward as many times,
     2. jump forward to the next g, having worked that out beforehand.
     3. search forward in a way that’s faster than scanning one-by-one, or
   • Manager: achieve a consensus on a way forward.
4. Design an algorithm which finds the next g from each second of the specified colour, using one of the optimisations above.
   • Analyse the time complexity of this algorithm in terms of n, the cycle length.
   • Estimate the running time of an implementation of this algorithm, and evaluate its feasibility.
   • Presenter: find a group using a different optimisation, and defend the validity of your idea to their presenter.
5. Write a program which implements your algorithm.
   • Reflector: propose some challenging test cases and explain why they are challenging.
   • Recorder: lead the implementation of the solution, with contributions and oversight from the other group members.
   • Test and debug as required.
   • Remember, this won’t pass the original problem because we haven’t accounted for repetition beyond the first cycle.
6. Now, we need to address the repetition of the colours.
   • Instead of just scanning forward to the end of the string, we might need to wrap around to the start.
   • Reflector: propose some challenging test cases and explain why they are challenging.
   • Other group members:
     • What’s the furthest forward we might need to wrap?
     • How can you address this with minimal changes to the program you previously wrote?
     • Implement the changes.
   • Test and debug as required.
7. Finally, we can deal with the multiple test cases.
   • Does the running time estimate hold up?
   • Reflector: what memory (if any) has to be reset between test cases?
   • Other group members: write a wrapper that delegates the work arising from each test case.
8. Submit your program for judging!
   • Debug as required.