Array puzzle solution

The problem was solved by Hadi Moshayedi.

The hard nut is, of course, initializing in constant time an array of size n. We can try to keep track of a set of indexes that are initialized. This reduces the problem to implementing a set of integers that supports make_empty, insert, and contains operations in constant time.

• array_init: allocate an array of size n, make an empty set
• array_set: set the element in the array and insert the index in the set of indexes
• array_get: if the index is not in the set return the default value, otherwise read from the array

It remains now to see how to implement such a set. A hash-table is not good because it is randomized (and many implementations offer only amortized constant time). A bitmap does insert and contains in constant time, but we can't make an empty set quickly. A list of integers can do insert and make_empty in constant time, but we can't determine quickly if an integer is in the list. Can we get the best of both? Yes, with two tricks:

1. If we represent the list as an array plus a counter then we can index it quickly. So we might be able to do the contains operation in constant time if we know where to look.
2. In a bitmap we don't have to store only bits: We can store the information we need for the previous observation. And here's the crux: If we do so we do not need to initialize it!

I'll leave it here. If you still have trouble writing the code, let me know.

PS: Rustan said he vaguely remembers reading this in Knuth, but he wasn't sure.

Edit: Cosmin pointed me to a more clear explanation. (I didn't read it: It's a bit long.)