← All solutions

Shortest judge solution: 1814 bytes. Shortest team solution (during contest): 2254 bytes.

This problem had a long, scary and convoluted statement hiding a simple implementation. In fact, it gave you exactly the algorithm you need to implement!

We need to simulate the processor’s decisions. The limits are low enough that we can actually afford to do this step-by-step, although we could optimize by fast-forwarding if a string of compute instructions are getting executed and no new tasks start.

Let us look at the individual steps to implement. Identifying running tasks is simple. The tricky part is determining what is blocked, and checking the current priorities of tasks. There are two approaches to that. We assume we keep the information on which task holds which resource locked.

The first one, which is harder to analyse but easier to code, is to repeatedly try to iterate on the rule for blocking and priority inheritance, until no new actions to perform are found. So, in each execution step, we would perform a loop until nothing changes. In the loop, for each pair of tasks, we check if the lower-current-priority one blocks the higher-current-priority one, and if yes, increase the first task’s priority to be equal to the second task’s. It’s hard to figure out why that would actually reach a fixed point eventually, but the problem statement tells us there exists a unique solution, so one might hope it will.

The second approach is to go from highest-priority tasks first. If the highest base priority task T isn’t blocked, it will be granted the processor — no task can have a priority higher than the highest base priority, and we are guaranteed there will be no ties in the priority resolution. If T is blocked, then we identify all the tasks that block T, and raise their current priority to the highest base priority. Note that T will never become unblocked (the first condition does not depend on priorities, and the priority of the highest-priority task will never change), so these priority changes are permanent. So, we can iteratively analyse each of these tasks, until we finally get to a task that is not blocked — and that task will get the processor (note that we’re relying on the guarantee there will be no ties). This obviously runs in O(t²) time for each determination without any optimization, so it will be fast enough.

Once we know which task to run, we execute one instruction, possibly increment the clock according to rules in step 3, and go back to the beginning.

We consider the fate of this task — which only got solved by Shanghai Jiao Tong University a quarter of an hour before the scoreboard freeze — a reminder to always try to read and understand the statement of all problems early in the contest!