Kostub has agreed to post his solution to the business card problem, so I will be breaking order (What? There was one?) and posting a solution to the Pens and Caps problem.
The problem:
You have $n$ pens, and $n$ caps for the pens. For every pen, there is exactly one cap that fits. The rest are either loose or tight.
Someone has taken the caps out and jumbled them up. Can you fit the caps on their respective pens, in expected $O(n \log n)$ time?
Solution
You basically do a quicksort!
Choose a cap at random. Now split the pens based on that cap. Smaller pens on one side (cap is loose), larger on the other (cap is tight) and the one that exactly fits is kept aside.
Now you recurse. Any expected time analysis for random pivot based quicksort will work here too.
The problem:
You have $n$ pens, and $n$ caps for the pens. For every pen, there is exactly one cap that fits. The rest are either loose or tight.
Someone has taken the caps out and jumbled them up. Can you fit the caps on their respective pens, in expected $O(n \log n)$ time?
Solution
You basically do a quicksort!
Choose a cap at random. Now split the pens based on that cap. Smaller pens on one side (cap is loose), larger on the other (cap is tight) and the one that exactly fits is kept aside.
Now you recurse. Any expected time analysis for random pivot based quicksort will work here too.
No comments:
Post a Comment