Maximizing your profit [Solution]

Problem was here: http://ruffnsluff.blogspot.com/2016/08/maximizing-your-profit.html


To repeat:
Suppose you had $K$ dollars and knew the price of gold over the next $n$ days. You want to invest all the $K$ dollars in buying gold once, and then sell all the gold at a later day (both among those $n$ days).

You want to maximize your profit.

Assume you get the prices as an array of length $n$.

Can you find an $O(n)$ time algorithm for this?

Solution

---

If you invest $K$ dollar at price $p_i$, you get $\dfrac{K}{p_i}$ units of gold. If you now sell at $p_j$, the profit you make of $\dfrac{K \times p_j}{p_i}- K$.

Thus you just need to maximize $\dfrac{p_j}{p_i}$.

This you can do by keeping track of the min $p_i$ seen so far, and the max possible $\dfrac{p_j}{p_i}$ as you increase $i$ (go from earlier days to later days). You can also avoid floating point compares if needed.

Application of AM >= GM solution

The problem was to show that

$$\left(1 + \frac{1}{n+1}\right)^{n+1} \gt \left(1 + \frac{1}{n}\right)^{n}$$

using the AM >= GM inequality.

Let $x_1 = x_2 = \dots = x_{n} = 1 + \frac{1}{n}$ and $x_{n+1} = 1$

Applying the AM >= GM to the $x_i$ we get that

$$\frac{x_1 + x_2 + \dots + x_{n+1}}{n+1} \ge \sqrt[n+1]{x_1x_2\dots x_{n+1}}$$

i.e

$$ \frac{n\left(1+\frac{1}{n}\right) + 1}{n+1} \ge \sqrt[n+1]{\left(1 + \frac{1}{n}\right)^{n}}$$

i.e

$$ \left(1+\frac{1}{n+1}\right)  \ge \left(1 + \frac{1}{n}\right)^{\frac{n}{n+1}}$$

Raising both sides to the $(n+1)^{th}$ power gives us the result.

Maximizing your profit

Suppose you had $K$ dollars and knew the price of gold over the next $n$ days. You want to invest all the $K$ dollars in buying gold once, and then sell all the gold at a later day (both among those $n$ days).

You want to maximize your profit.

Assume you get the prices as an array of length $n$.

Can you find an $O(n)$ time algorithm for this?

[Solution]

Appilcation of AM >= GM

Arithmetic mean greater than or equal to geometric means is a well known ineqaility.

Use that to show that

$$\left(1 + \frac{1}{n+1}\right)^{n+1} \gt \left(1 + \frac{1}{n}\right)^{n}$$


[Solution]

Generate a random red-black tree [Solution]

The problem was to generate a random structurally unique red-black tree on $n$ nodes.

Solution

---

Now if we knew exactly how many red-black trees of $n$ nodes have $L$ nodes in the left subtree, then we can generate them as follows.

Count the total number of trees with $n$ nodes. For each $L$ in $\{0,1,\dots,n\}$,  count the fraction $\alpha_L$ of them with $L$ left nodes in the left subtree.

Now generate a random number $L$ in $\{0,1,2,\dots, n\}$ with probability $\alpha_L$. This will be the number of children in the left subtree. The number of children in the right subtree is $n-1-L$. Recursively generate the subtrees now.

This works because the subtrees of a red-black tree are red-black trees themselves. On how to count, see this previous post on this blog on counting red-black trees (some modifications might be needed).

exp(x) inequality [Solution]

The problem was to show that

$$e^x \ge 1 + x + \frac{x^2}{2!} + \dots + \frac{x^n}{n!}$$

for all $x \ge 0$ and integer $n \ge 0$.

Solution

---

Let $f_{n}(x) = 1 + x + \frac{x^2}{2!} + \dots + \frac{x^n}{n!}$ with $f_{0}(x) = 1$

Now $e^x \ge f_{0}(x)$ for all $x \ge 0$

Now suppose $e^x \ge f_{n}(x)$ for all $x \ge 0$.

Let $h(x) = e^x - f_{n+1}(x)$

Now $h(0) = 0$.

We also have that the derivative of $h$, $h'(x) = e^x - f_n(x)$

By induction assumption $h'(x) \ge 0$ for all $x \ge 0$.

Thus $h$ is increasing and so $h(x) \ge h(0) = 0$ for all $x \ge 0$.

Thus by induction, we are done.

Generate a random red-black tree

Following up on two previous posts.

Given $n$, can you give an algorithm to generate a random red-black tree consisting of $n$ nodes? Each structurally unique tree should have an equal chance of being generated (we are not interested in the actual assignment of colors).

[Solution]

exp(x) inequality

Quick one.

Use induction to show that

$$e^x \ge 1 + x + \frac{x^2}{2!} + \dots + \frac{x^n}{n!}$$

for all $x \ge 0$.

$n$ is a natural number $\ge 0$.

[Solution]

Number of AVL trees [Solution]

The problem was to compute the number of AVL tree of $n$ nodes.

Solution

---

The solution is very similar to that of the corresponding problem for red-black trees.

Using dynamic programming, try to compute $T[n, h]$ the number of AVL trees on $n$ nodes with height $h$.

Now write a recursive formula based on the AVL tree properties, and you have an algorithm.

I will leave the details to you.

Harmonic numbers are not integers [Solution]

The problem was to show that

$$ H_n = \sum_{k=1}^{n} \frac{1}{k} = 1 + \frac{1}{2} + \dots + \frac{1}{n}$$

is never an integer for $ n \gt 1$.

Solution

---

There are multiple solutions. One of them uses Bertrand's postulate, which says that there is a prime between $n$ and $2n$ for any $n \gt 1$.

Now consider the largest prime $p$ in $1, 2, \dots, n$.

The denominator of $H_n$ is divisible by $p$. The numerator has terms divisible by $p$, plus the term $1 \times 2 \times \dots \times (p-1) \times (p+1) \times \dots \times n$

By Bertrand's postulate, we have that $2p \gt n$ (otherwise $p$ won't be the largest prime).

Thus the numerator is not divisible by $p$. Thus $H_n$ is not an integer.

Number of AVL trees

AVL trees were one of the first balanced tree structures to provide $O(\log n)$ operations and do so based on height differences between left and right subtree. Look at the wiki link for an exact definition.

Can you give an algorithm to compute the number of AVL trees having exactly $n$ nodes?

[Solution]

Harmonic numbers are not integers

A classic:

Show that

$$H_n = \sum_{k=1}^{n} \frac{1}{k}$$

is never an integer, for $n \gt 1$.

i.e.

$$ 1 + \frac{1}{2} + \dots + \frac{1}{n}$$

is never an integer for $n \gt 1$.

Number of Red Black Trees [Possible Solution]

The puzzle was to count the number of possible red-black trees on $n$ nodes.

Possible Solution

---

Red black trees have the following property:

For every node, the (max) height of the subtree at that node is no more than twice the min height. This condition is both necessary and sufficient.

This gives the max height to be at most $2 \lceil \log_2 n\rceil$

Each subtree is also a red-black tree.

This gives us a dynamic programming algorithm.

Let the number of red black trees of min height $h$ and max height $H$, with $n$ nodes be $T(n, h, H)$.

Now we can give a recursive formula by considering the possible number of nodes and the min and max heights of the left and right subtrees (which are red-black trees themselves), then summing the up.

This should give a polynomial time algorithm.

Note: I haven't tried it, but if you choose to, you should be able to verify it by checking with OEIS which has the sequence I believe.

2n choose n [Solution]

The problem was to show that the binomial coefficient $\binom{2n}{n}$ is divisible by $n+1$.

Solution

---

Let $$C = \dfrac{\binom{2n}{n}}{n+1}  = \dfrac{2n!}{n! (n+1)!}$$

$C$ is actually a well known number, it is called a Catalan Number and has numerous combinatorial interpretations. Picking any one such would prove that $C$ is an integer.

But since this is an easy puzzle we will give a short proof.

Now

$$(n+1)C = \dfrac{2n!}{n! n!} = \binom{2n}{n}$$

and

$$nC = \dfrac{2n!}{(n-1)! (n+1)!} = \binom{2n}{n+1}$$

Thus $C = (n+1)C - nC$ is the difference of two binomial coefficients, and is thus an integer.

We can also phrase this as a consquence of:

If $r$ is a rational and $a,b$ are two relatively prime integers such that both $ar$ and $br$ are integers, then $r$ is also an integer.

Trump power

This is a hand from an internal swiss teams tournament at Google.

You are South and end up in 2S after West opens a 15-17 NT.

IMPS None	North ♠ 87 ♥ T42 ♦ AQT73 ♣ 874
	South ♠ KQJT6 ♥ A7653 ♦ K ♣ Q6

W	N	E	S
1NT1	P	2C2	2S
P	P	P

2C need not guarantee a 4 card major (in case of an invitational hand). They were playing a form of crawling stayman which could be bid with a 4 card major and 5 card minor.

LHO leads the HK which you duck. LHO follows with the HQ (RHO follows too) and you win the A.

How will you play? [Please think about it before reading on]




Given that RHO has <5 points, they likely have a 4 card spade and were trying to get out low in a suit contract.

Now you can practically guarantee the contract thanks to the trump spots in the dummy!

After winning the heart Ace, play the DK overtaken by the A and DQ throwing a club. If RHO ruffs the second diamond (unlikely, as LHO would have opened 1NT with 6 diamonds) you discard a club, and can hope to enjoy hearts. So assume RHO follows to the second diamond.
 
Now play a heart! The idea being trying to ruff a heart for the 8th trick (4 spades, 1 heart, 2 diamonds and need one more).

The opponents might win the third heart and force you in clubs. You ruff and play the fourth heart and try to ruff it in dummy.  If opponents ruff the fourth heart and try to force you in clubs, you can try to ruff the fifth heart. If opponents ruff the fourth heart and try to draw trumps, you can enjoy the long heart trick.

If opponents overruff both the 8 and 7 (with the 9 and A), you make 5 spades in hand, a heart and 2 diamonds.

There are other lines that work too, given that RHO likely has 4 spades and 5 clubs, but the ruffing line is pretty nice and I believe it is percentage play even if RHO didn't bid 2C.

How many Red-Black trees?

Given $n$, how many red-black trees exist with $n$ nodes?

Can you give an algorithm to compute that value? Hopefully polynomial in $n$.

Note: I haven't tried solving this problem myself, so it is a little open ended and don't expect to see a solution!

[Possible Solution]

2n choose n

A quick one.

Show that the binomial coefficient $\binom{2n}{n}$  (i.e. $2n$ choose $n$) is divisible by $n+1$.

[Solution]

Keep winners, throw losers?

This is a hand from a team game on BBO, where people self alert their bids.

You are West and see the opponents get to 3NT.

IMPS N/S	North ♠ KJ4 ♥ KJ543 ♦ KJ85 ♣ 4
West ♠ 53 ♥ T7 ♦ A63 ♣ AK9862

W	N	E	S
		P	1NT1
2C2	X3	P	3NT4
P	P	P

1: 1NT = 13-15
2: 2C = single suited, 6+ cards.
3: X = Game forcing.
4: 3NT = 4-4 majors, maximum hand.

Note, these are self alerted bids and N/S had a misunderstanding about the 3NT bid.

You lead the AK and low club, partner following and declarer showing up with QJx (declarer throwing diamonds from dummy).

Now declarer proceeds to cash 4 spades (declarer has AQxx).

What will you discard on the two spades you cannot follow to? [Please think about it before reading on].



Declarer surely has the HA. If he has the HQ, there is nothing you can do.

So assume declarer has a hand like AQxx, Axxx, Qx QJx.

Now declarer needs to guess whether to go for the heart drop or take the finesse.

Now imagine what happens if you throw your diamond losers and hold on to your club winners.

Declarer will place you with the DA (the way you bid and defended points to that). So declarer will give you 6 clubs, 3+ diamonds (atleast A and the two you discarded), 2 spades and therefore 2 or fewer hearts!

So if you discard two diamonds, declarer will get it right.

In order to make declarer guess, you need to throw a diamond and a club, i.e. throw away a winner!

If you discard a club and a diamond, declarer might place you with xx, QTx, Ax, AKxxxx and take the finesse.

Is It a Red-Black Tree [Solution]

The problem was to give an algorithm to determine if a given binary tree can be coloured with red/black such that it satisfies the constraints of a red-black tree.


Solution

---

A Red black has this property:

For any node, the length of the shortest path (to a leaf node) is atleast half the length of the longest path (to a leaf node). In other words, for any sub-tree, the shortest height is at least half the height.

This condition is actually sufficient too, and can be proved via induction (I am feeling lazy and will leave that to you).

The usage of this condition gives us an $O(n)$ time algorithm to determine if a given binary tree is actually a red-black tree.

Equalize the buckets [Solution]

The problem was:

$(x,y)$ with $x \lt y$ is transformed to $(2x, y-x)$. This process is repeated. For what initial $x,y$ can we end up with equal numbers. $x,y$ are positive integers.

Solution

---

Notice that starting with $(x,y)$ is essentially starting with $(ax, ay)$ for any integer $a \ge 1$.

So assume that $x$ and $y$ have no common factor.

Now for the numbers to become eventually equal, $x+y$ must be even, as the sum of the two numbers never changes.

Thus after one step $(2x, y-x)$, both these numbers are even, and so we can divide out by $2$

Every time we divide out by $2$ the sum is halved.

Thus if $x+y = 2^M Q$, where $Q$ is odd greater than $1$, eventually we end up with an odd sum, and so cannot equalize.

Thus the condition is that if $x/y = p/q$ in lowest terms, then equalization occurs iff $p+q = 2^m$.

Don't be hasty

A quick one for the newer players.

In a teams event, you end up in 6H, after you overbid your hand.


LHO leads a low spade.

IMPS N/S	North ♠ T ♥ KQT982 ♦ K32 ♣ 543
	South ♠ KQJ72 ♥ A3 ♦ A54 ♣ AJ2

W	N	E	S
			2NT
P	3D	P	3H
P	4H	P	6H

RHO wins the spade A and plays back the spade nine.


Don't play the K (or Q/J)! LHO could have led a singleton. If you play the K (or Q/J), LHO will ruff and you will end up a trick short.

Play the 7 and ruff. Draw trumps (you have to hope they are 3-2, or J falls). Then you can cash your spade tricks in peace.

Is it a Red-Black tree?

Red-Black trees are commonly used self balancing binary trees. Another example of a self balancing binary trees is an AVL tree.

A common interview question is to determine if a given binary tree is an AVL tree, based on the height constraints an AVL tree has.

A red-black tree has colouring constraints (check the wiki page above), where each node is coloured either red or black and then there are some constraints based on the colours.

The puzzle here is to determine if a given binary tree of $n$ nodes can be coloured [i.e. each node coloured red or black] so as to satisfy the constraints of a red-black tree.

Can you give an algorithm which runs in $O(n)$ time?

[Solution]