Next, can a particular set of rankings result in strictly less than a quadratic number of iterations? Can you design an input that requires O(n) iterations? If so, describe the structure of this input. If not, argue why this is not possible. Finally, can you design an input that takes fewer than n iterations? Why or why not?
Aim for clarity and conciseness in your write up of this problem. You should have all the necessary tools to express your solutions. You do not need formal proofs or psuedocode, but you should be able to clearly articulate your ideas in plain English.
Show that it is possible to assign each hipster h a unique coffee shop c_h, such that when h arrives at c_h according to the itinery for h, all other hipsters h' have either stopped touring coffee shops themselves, or h' will not visit c_h after h arrives at c_h. Describe an algorithm to find this matching. Hint: The input is somewhat like the input to stable matching, but at least one piece is missing. Find a clever way to construct the missing piece(s), run stable matching, and show that the final result solves the hipster problem.
It may be necessary to break ties, i.e., two hipsters might choose to visit the same coffee shop on the same day. You may assume that the tie can be broken by having hipsters arrive at different times of the day such that if h and h' both want to visit c on the same day that there is some timestamp on their visits such that it is easy to determine who arrived at c first. Thus, for any given day, at any given coffee shop, there is a well defined ordering to the planned arrival time of the hipsters.