Let us first describe how to compute the optimal strategy of Leonardo in ~\mathcal O(N \log N)~ time.

• Use an array of size ~N~ and scan the requests in ~C~ backwards: for each request, it is possible to compute how far in the future the same color will be requested.
• Process the requests in ~C~ forward: for each request, we can determine if the color is in the scaffold and which of the colors to remove; the latter can be established in time ~\mathcal O(\log N)~ by keeping a priority queue of colors where the priority is determined by the time of the next request.

For encoding the advice, the trivial solution would be to use ~N \log K~ bits, i.e. ~\log K~ for every color fault (i.e., every time the requested color is missing from the scaffold): this way we might specify exactly which color (within the ~K~ colors available on the scaffold) should be removed.

Here is an alternative encoding that uses only ~N+K~ bits and it is optimal in the worst case.

• Divide the colors currently in the scaffold between "active" and "passive": an "active" color is one that will be requested before it is removed from the scaffold according to the optimal strategy of Leonardo; a "passive" one will not.
• Using ~N+K~ bits it is possible to keep track of which colors are active:
  • The initial active colors can be specified using ~K~ bits overall.
  • Moreover, with each request we can provide a bit saying if the currently requested color is active.
• Note that removing any passive color is always ok. Of course, if you remove it arbitrarily you will not produce the optimal solution you started from, but an equivalent one with the same number of colors removed.