Editorial for DMPG '18 G1 - Musical Chairs
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:
For the first subtask, simulation can pass in time.
Time Complexity:
For the last two subtasks, keep a stack of students. Initially the stack is empty. Loop through the chairs. If a student is at a chair, add this student to the stack and remove the student from this chair. If the current chair is empty and the stack is not empty, remove the topmost student and the chair is no longer empty. Continue doing this until there are no more empty chairs (it is possible that you must loop back to the start and keep going for a while). The final student in the stack is the last student left standing.
Time Complexity:
Comments