hackercupai/hackercup huggingface dataset:
Models wearing the same style are indistinguishable aside from whether or not they have already changed at least once (as each model's first change is free). We can therefore represent the set of models before/after each round by a pair of numbers per style \(s\): the number of models \(W_s\) currently wearing that style, and the number of those models \(U_s\) who have not yet changed at all. Note that we only need these entries per style currently being worn by at least one model.

We'll process one round at a time, following a greedy approach based on the set of models before the round to determine the new set of models after the round (as well as the number of new changes which must be performed by Dorothy). Let \(R_s\) be the number of models required to wear style s in the current round. The greedy approach is then based on the following list of priorities:

1. *As few models as possible should change at all.* For each style \(s\), \(\min(W_s, R_s)\) models might as well remain unchanged in style \(s\), as it cannot be better for them to change out of it and others to change into it. This means that \(C_s = W_s - \min(W_s, R_s)\) models will change out of style \(s\).
2. When choosing exactly which models should change, *those who have never changed should be prioritized*. Such models can be changed for free, and it cannot be better to change different models in the current round instead and save the previously-unchanged models for later. This means that \(\min(C_s, U_s)\) previously-unchanged models will change out of style \(s\) (by themselves), while \(C_s - \min(C_s, U_s)\) other models will change out of style \(s\) (with Dorothy's help).

These ideas are sufficient to describe an optimal approach, and can be used to efficiently simulate the sequence of events. Assuming we use hash tables (keyed by style) to represent the above values, each round may be processed in \(O(M)\) time, given that there will be at most \(M\) distinct styles before it and at most \(M\) after it. The overall time complexity is therefore \(O(NM)\).

[See David Harmeyer (SecondThread)'s solution video here.](https://youtu.be/3iT1vv_Tdpo)