Internet Problem Solving Contest

IPSC 2017

Solution to Problem Q – Queue skipping

The easy subproblem is easily solved by brute force: just simulate the process described in the problem statement. And if you used a reasonably fast programming language and had a bit of patience, you could actually use the same code to solve the hard subproblem as well – the test cases aren’t that large, a well-implemented solution that runs in O(ne) time should solve the hard subproblem within a few minutes.

But where’s the fun in that? We want a more clever solution!

In order to solve the hard subproblem in an efficient way, realize that there are only two possibilities for the answer:

  1. If there are some people who never skipped to the front, these are now the people at the end of the queue. In particular, the last person in the queue is the one with the largest number among the people who never skipped the queue.

  2. If everybody skipped to the front at least once, the person at the end of the queue is the one who did so least recently.

Once we make this observation, we can easily solve the problem in linear time – more precisely, in O(n + e) steps.

A small bonus challenge: can you compute not just the last person but the entire final state of the queue in O(n + e) time?