← All solutions

Despite its relatively straightforward statement, this was a somewhat nasty problem with several special cases. Let us start with key cost. Whenever there are keys of both type on the same ring, one of the key types has to be “evacuated”. Typically, we want to evacuate the key that is the least frequent on the ring (in case both are equally frequent we will try both possibilities; this happens for at most 13 rings). However, if this results in no free rings for the evacuated keys we have to reserve some ring for the evacuated keys (again we can try all possibilities). Another special case, illustrated by the sample data, is that if there is only one ring and both types of keys then the problem is impossible.

Once the key conflicts have been resolved, we can compute the ring costs by standard dynamic programming.