← All solutions

Solved by 135 teams.

First solved after 17 minutes.

Shortest judge solution: 890 bytes.

For any pot that is to host at least one cat, the plant in that pot must be in the intersection of the sets liked by those cats. Additionally, if a cat likes a plant, that plant cannot be placed earlier than that cat’s target pot. Thus, we can compute a lower bound on the pot number for any given plant.

We can identify a few conditions in which there is clearly no solution:

1. Consider a given pot. If there is no plant which is both in the intersection mentioned above and whose lower bound allows it to be placed in that pot, then the pot cannot be filled.
2. Consider any prefix of the pots. If there are not enough plants whose lower bound allows them to be placed in this prefix, then these pots cannot all be filled.

It can be shown that these conditions are also sufficient: the pots can be filled by working from left to right, and there will always be a plant that can be placed in the current pot. To provide a yes/no answer, it is not necessary to actually conduct this process. It is sufficient to test the two conditions.

Running time depends on the data structures used to compute the set intersections. A reasonably efficient implementation (such as sorted lists) gives O(n + m + K log K) where K is the sum over all k.