Coupon collecting problem
This problem is on codejam.
You've become addicted to the latest craze in collectible card games, PokeCraft: The Gathering. You've mastered the rules! You've crafted balanced, offensive, and defensive decks! You argue the merits of various cards on Internet forums! You compete in tournaments! And now, as they just announced their huge new set of cards coming in the year 2010, you've decided you'd like to collect every last one of them! Fortunately, the one remaining sane part of your brain is wondering: how much will this cost?
There are kinds of card in the coming set. The cards are going to be sold in “booster packs”, each of which contains cards of different kinds. There are many possible combinations for a booster pack where no card is repeated. When you pay for one pack, you will get any of the possible combinations with equal probability. You buy packs one by one, until you own all the kinds. What is the expected (average) number of booster packs you will need to buy?
This problem is on codejam.
Goro has 4 arms. Goro is very strong. You don't mess with Goro. Goro needs to sort an array of different integers. Algorithms are not Goro's strength; strength is Goro's strength. Goro's plan is to use the fingers on two of his hands to hold down several elements of the array and hit the table with his third and fourth fists as hard as possible. This will make the unsecured elements of the array fly up into the air, get shuffled randomly, and fall back down into the empty array locations.
Goro wants to sort the array as quickly as possible. How many hits will it take Goro to sort the given array, on average, if he acts intelligently when choosing which elements of the array to hold down before each hit of the table? Goro has an infinite number of fingers on the two hands he uses to hold down the array.
More precisely, before each hit, Goro may choose any subset of the elements of the array to freeze in place. He may choose differently depending on the outcomes of previous hits. Each hit permutes the unfrozen elements uniformly at random. Each permutation is equally likely.
This problem was given in the first round of a coding contest organized by Criteo, where I worked in 2010-2011. I helped write a solution that is given below.
Let be an array of non-negative integers, indexed from to . We assume that the sum of its elements is a multiple of
where is a positive integer. We would like to balance the array in a minimum number of iterations, where each iteration transforms the array using a number of allowed transfers described below. Balancing the array means transforming it into the uniform target array . To describe the allowed transfers, let denote the state of the array at the beginning of iteration . During iteration , each postive cell can transfer one unit to its left neighbor (left transfer), or transfer one unit to its right neighbor (right transfer). A left transfer is described by the operations
Note that a left transfer is not possible for the left-most cell (similarly, a right transfer is not possible for the right-most cell). Also note that all transfers occur simultaneously, meaning that in the example array we cannot make a right transfer from to then a right transfer from to in a single iteration, obtaining . This transformation will require two iterations.
Example: In the following example we start from array . Balancing this array requires a minimum of iterations. Here is one example of an optimal sequence of transformations
We would like to find the minimum number of iterations required to balance any given array .