886C - Petya and Catacombs

  1. Note that if a number appears twice, then we know a new room must added. Similarly, if t appears k times, then at least k-1 new rooms are introduced
  2. If a number appears only once, we just assign to whatever room it is in. Note that we don’t have to find it!!!
  3. So the answer is sum of max(0, # of t - 1) for all t that appears.

886D - Restoration of string

  1. Assume the set is valid already, how do we get the final string, and is it possible to detect the invalid case during the construction?
  2. We model the each independent substring as a graph, e.g., if the string is abc, then we model as a-> b -> c
  3. Note that if a letter branches it is invalid too!, i.e., consider the set {ab, ac}
  4. so we just build a simple cycle-list, and start from a->z try hooking up all the cycles