Generate a random heap.

Very recently I posted a puzzle on generating a random binary tree.

This time, the puzzle is to generate a uniformly random binary heap.

Specifically, generate a heap implemented as a binary tree of $n$ nodes, where each node takes exactly one of the values in $\{1,2, \dots, n\}$, and satisfies the max-heap property: each node value is larger than the values of its children (number of children could be zero, one or two).

The tree does not have to be full/almost complete (so a linked list of $n$ nodes is a valid heap for our purposes).

The left and right children are distinct, so the heap with 3 at the top, and left child 1, right child 2, is different from the heap with 3 at the top, left child 2 and right child 1.

Assume you have a random number oracle which gives you a random number in the range $\{1,2, \dots, K\}$, with probability $\frac{1}{K}$, $K$ is input and could be as large as you want it to be.

A) Give an algorithm that makes $O(n)$ calls to the random number generator.

B) Give an algorithm that makes $O(1)$ calls.

[Solution]

Integration problem

Computing tricky integrals was something which folks preparing for IIT JEE used to do.

Here is one such.

$$ \int \frac{1+x^2}{(1-x^2)\sqrt{1+x^4}} dx$$

[Solution]

Generate a random binary tree [Solution]

The puzzle was to generate a random binary tree on n nodes, each structurally distinct tree being equally likely, given a uniform random number generator which can generate a number from 1,2,...,K with probability 1/K, given input of K.

The easier version was to use O(n) calls to the random number generator.

The harder version was to use O(1) calls to the random number generator.

Solution

---

A structurally unique tree can be encoded by its preorder traversal, which includes the null nodes, and that encoding is reversible.

Using a '1' for a node, and '0' for a null node, we get a string of n 1s and n+1 0s.

For example, just a single node tree encodes are 100. (1 for root, and 0, 0 for the left and right null children), while a tree with a root and its right child encodes as 10100.

An important property of this encoding: Every proper prefix of the encoding has at least as many 1s as 0s, and any string with n 1s and n+1 0s that has that prefix property, is the encoding of a tree.

Now if you look at the reverse of the encoding (e.g: 001 for a single node tree), it is nothing but a semi-balanced string which we encountered in an earlier blog post!

Now we can generate a tree as follows:

Generate a random string of n+1 0s and n 1s. Find the unique semi-balanced string which is a circular shift of that string.  Reverse it. Decode to get the tree which gives that preorder.

Thus the problem boils down to picking n numbers out of 2n+1 numbers (the positions of the 1s).

If we use reservoir sampling, this will take O(n) random number calls.

We can also encode the sets to a number from 1 to $\binom{2n+1}{n}$, pick a random number using _one_ random number call (remember it can take arbitrary integers as input), and decode. I will leave the decoding to you.

A perfect square problem [solution]

The puzzle was to find all positive integers $n$ (with proof) for which $$n^4 + n^3 + n^2 +n + 1$$ is a perfect square.

Solution

---

One liner!

For $n \gt 3$, we have that

$$ (2n^2+n)^2 \lt 4(n^4 + n^3 + n^2 +n + 1) \lt (2n^2 + n + 1)^2$$

So verify for $n=1,2,3$ and we get the answer to be $n=3$.

What is the danger?

This puzzle is for the newer players (not completely new, though).

Playing Rubber Bridge, you are South and end up in 5S. West leads the club 2 and you see:

Rubber N/S	North ♠ QJT92 ♥ A2 ♦ QJ ♣ QJ43
	South ♠ K8754 ♥ K3 ♦ A3 ♣ AK65

You play low from dummy and East follows with the club 7.

What is the danger, and how will you deal with it? How will you play?

Solution (updated March 24th 2015)

---

Looks like West has led a singleton club.

The danger is when East has the singleton Ace of trumps.

In that case, if you play trumps immediately (after winning the first trick), East will win, give partner a ruff, and West will safely play back a heart. Leaving you to rely on the diamond finesse.


You cannot prevent the club ruff if it is there, but you can remove the safe heart exit from West, by playing two rounds of hearts before touching trumps. Now if West ruffs, he will be forced to return a diamond giving you the free finesse, or a heart for a ruff-n-sluff!

Generate a random binary tree

You want to generate a random binary tree on n nodes, such that each structurally different tree has the same chance of being generated as any other.

Suppose you have access to a random number generator oracle which generates an integer in $\{1,2,\dots, K\}$ (with probability $\dfrac{1}{K}$), given $K$ as an input ($K$ could be as large as you want).

Can you give an algorithm which generates an n node binary tree using $O(n)$ calls to the random number generator?

Can you do it using $O(1)$ calls?

[Solution]

A perfect square problem

Find all positive integers $n$ (with proof), for which $$n^4 + n^3 + n^2 + n + 1$$ is a perfect square.

[Solution]

Balanced Bit String [Solution]

The puzzle is here.

Problem: Given an array of n bits, can you tell if it is balanced (number of occurrences of 01 = number of occurrences of 10) in sub-linear time?

Solution

---

The algorithm depends on the following property:

A bit array is balanced if and only if the first and last bits are equal!

Can be proved using induction. Constant time algorithm!

One divides another [Solution]

The puzzle is here.

Gist: Are there two 7 digits numbers, each comprising of the digits 1,2,3,4,5,6,7 such that one divides the other?

Solution

---

Each number must leave a remainder 1 when divided by 9, as the sum of digits is 1 + 2 + ... + 7 = 1 modulo 9.

Now the larger number cannot be more than seven times the smaller number (largest possible digit is 7 and both are seven digit numbers).

Thus if the smaller leave a remainder 1, then the larger cannot.

Thus there aren't such two numbers.

A hand from Howard Schenken's book

This a hand from Howard Schenken's autobiography, "The Education of a Bridge Player" and is a good example of making the right assumptions.

You partner, North is dealer. After two passes to you, you open 1H and end up in 4H (opponents silent).

LHO leads a trump, you see

Rubber None	North ♠ 9 ♥ JT52 ♦ J97432 ♣ AQ
	South ♠ AJ8 ♥ KQ963 ♦ K5 ♣ T86

W	N	E	S
	Pass	Pass	1H
Pass	4H	Pass	Pass
Pass

RHO wins the HA and continues a trump (to which LHO will follow).

How will you play?

Solution (posted 12 March 2015)

---

RHO has shown up with the HA, and likely has a spade honor (because LHO didn't lead one). RHO also passed initially. So if RHO has the DA, then the club finesse is working.

So you make the assumption: Assume RHO has the CK.

In this case, you need to set up your diamonds (which are likely 3-2, based on the play to first two tricks: no one shifted to a singleton).

The book recommend line is winning trick 2 in dummy and playing the DJ! If RHO covers, you duck. Now RHO cannot attack clubs.

The key play is to lose the second diamond to LHO, not the first, which allows you to setup the diamonds before the clubs are attacked and CK is cashed.

Another line of play which works, and which reminds us of the Belladonna coup: win trick 2 in hand and lead a low diamond away from the K!

Balanced bit string

Another quickie.

A string of bits is called balanced if the number of times "01" appears is same as the number of times "10" appears in the string.

For example, in "0010010", 01 appears twice ("0010010") and 10 appears twice ("0010010"), so it is balanced.

So, the question is, given a bit string of n bits (as an array of bits), can you give a sub-linear time algorithm to determine if the bit string is balanced?

[Solution]

One divides other

Have been sick these past few days. So a quick one for now.

Are there two seven digit numbers, each with the digits 1,2,3,4,5,6,7 used exactly once such that one divides the other?

For example with two digits 1,2, the possibilities are 12 (twelve) and 21 (twenty one).

Try solving this mentally without using any pen/paper etc.

[Solution]