Hasty West, Lucky South.

This is a hand from bridge at Google Kirkland. I will just post the four hands and what happened (there might be interesting aspects to this hand, which I will leave you to discover on your own!)

Assume the scoring is IMPS.

IMPS E/W	North ♠ QJx ♥ Axx ♦ xx ♣ T98xx
West ♠ T98xx ♥ x ♦ Qxx ♣ AKQJ		East ♠ x ♥ KT98x ♦ T98xx ♣ xx
	South ♠ AKxx ♥ QJxx ♦ AKJ ♣ xx

W	N	E	S
1S	P	P	3NT
all	pass

West was dealer and opened 1S. After two passes South ventured a 3NT in the balancing seat and got to play there.

West quickly started off with the AKQ of clubs, on which both East and South discarded a heart (east encouraging).

At this point West shifted to a heart.

South ducked the heart to East's K and won the diamond continuation.

This was the position:

IMPS E/W	North ♠ QJx ♥ Ax ♦ x ♣ T9
West ♠ T98xx ♥ - ♦ Qx ♣ J		East ♠ x ♥ T98 ♦ 98xx ♣ -
	South ♠ AKxx ♥ QJ ♦ KJ ♣ -

South had lost 4 tricks and needed the rest.

Look what happened.

South cashed 4 spades throwing a club from dummy, and now the hand was

IMPS E/W	North ♠ - ♥ Ax ♦ x ♣ T
West ♠ T ♥ - ♦ Qx ♣ J		East ♠ x ♥ T ♦ 98 ♣ -
	South ♠ - ♥ QJ ♦ KJ ♣ -

When South played the HQ (low from dummy), west could throw a spade, but was squeezed on the heart J to the A!

South ended up making 9 tricks!

West was too hasty and didn't give the hand its due consideration. They should have paused after trick one and as the play went, after trick three.

Anyway. What would you lead? What would you do at trick two?

[btw, if you need to know who had the S7 and/or S6, I believe it was with West]

Max area in histogram [Solution]

The problem:

Given an array $A$ of integers, $A[1], A[2], \dots, A[n]$, find a contiguous sub-array $A[i], \dots, A[j]$ such that $(j-i+1) \times \min\{A[i], \dots, A[j]\}$ is maximum.

Solution

---

This is a classic ACM programming contest problem.

A bunch of solutions can be found here: http://www.informatik.uni-ulm.de/acm/Locals/2003/html/judge.html

Look at Problem H.

But, the reason for this blog post was to present a different solution to this, using Cartesian Trees.

A cartesian tree for an array $A$, is a binary tree such that it is a heap formed from the elements of $A$, and the in-order traversal of the tree gives back the array in order: $A[1], A[2], \dots, A[n]$. See the diagram below (swiped from the wiki page).

 

These trees can be constructed in $O(n)$ time (see the wiki page for more details).

To solve the problem, we use divide and conquer.

First we construct a cartesian tree which gives a min-heap.

Now notice that, if $A[m]$ is the minimum element of $A$, then the optimum solution is either $n \times A[m]$, or the optimum solutions from $A[1], \dots A[m-1]$ and $A[m+1], \dots, A[n]$.

The cartesian tree of $A$ gives us $m$, and the cartesian trees for $A[1], \dots, A[m-1]$ (the left subtree) and $A[m+1], \dots, A[n]$ (the right sub-tree)!

Thus if we annotate each node $N$ of the cartesian tree with the number of nodes in that sub-tree $N_c$, we just need to compute max of $N.values \times N_c$ over all the nodes! $N.value$ is the element value from $A$.

This is an $O(n)$ time solution.

For another application of Cartesian trees, try solving this puzzle on this blog: Construct BST.

log sequence limit [Solution]

The problem was:

$x_1 \gt 0$ and $x_{n+1} = \log (1 + x_n)$.

Find $\lim_{n \to \infty} nx_n$.

Note: $x_n$ is monotonically decreasing and bounded below by $0$, and $x_n \to L = 0$ (solution of $L = \log(1+L)$).

Solution

---

Did you know there was something like a l'Hopital rule for sequences?

It is called the Stolz–Cesàro theorem. That can be used here, and easily gives us the limit (in fact by using the fact that $x_n \to 0$ and applying the normal l'Hopital rule twice!)

We will not use that though.

Consider the sequence $$ y_n = \dfrac{1}{x_{n+1}} = \dfrac{1}{\log(1+x_n)}$$


Now $\log (1 + x_n) = x_n - x_n^2/2 + O(x_n^3)$

Thus $$y_n = \frac{1}{x_n - x_n^2/2 + O(x_n^3)} = \frac{1}{x_n(1 - x_n/2 + O(x_n^2))}$$

$$ = \frac{1}{x_n} - \frac{1}{2} + O(x_n)$$

(Using $\dfrac{1}{1-t} = 1 + t + t^2 + \dots$).

Thus $c_n = y_n - y_{n-1} \to \dfrac{1}{2}$ (we can apply Stolz Cesaro here if we want).

Now if $a_n \to L$, then $S_n = \dfrac{a_1 + a_2 + \dots + a_n}{n} \to L$.

Thus applying the above to $c_n$, we get $\dfrac{y_n}{n} \to \dfrac{1}{2}$.

Thus $$n x_n \to 2$$

Max area in histogram

This is from some ACM programming contest, and has a bunch of good solutions, so don't search the web too quickly.

The problem is as follows:

You are given a histogram, and want to find the maximum area rectangle that can be drawn within that histogram.

Basically, given an array $A[1], A[2], \dots, A[n]$ of say integers, find a contiguous sub-array $A[i], \dots, A[j]$ such that $(j-i+1)\times \min \{A[i], \dots, A[j]\}$ is maximum.

An $O(n \log n)$ solution is acceptable, but $O(n)$ solutions exist.

[Solution]

log sequence limit

Consider the sequence defined as follows, with $x_1 \gt 0$.

$$x_{n+1} = \log (1 + x_n)$$

One can show that $x_n \to 0$ as $n \to \infty$ (try it).

What can you say about the sequence $y_n = nx_n$ as $n \to \infty$? Does the limit exist? If so, what is it?

Note: The $\log$ is the natural logarithm to base $e$.

[Solution]

Hopeless contract

Here is a hand from lunch bridge at Google Seattle (assume IMPs scoring, basically).

You are South, open 2S and get raised to 4S by partner.

LHO leads a low heart (singleton or 3+). This is what you see:

Lunch Bridge E/W	North ♠ Kxxx ♥ AKQTx ♦ xx ♣ xx
	South ♠ QJTxxx ♥ Jxx ♦ xx ♣ KQ

You have 4 top losers. Is there anything you can try?

[Please think about it before reading on]






Seems like you need a defensive error.



One possibility is to play the SJ.

If you play the SJ, LHO with Ax of spades, might choose to play you for a hand like JT9xxx, xx, Axx, xx and hope for two spade tricks by playing low and partner winning the SQ.

If LHO ducks the SJ and has 3+ hearts, you can now throw a diamond on the hearts!

At the table, LHO did have Ax of spades and three hearts. Unfortunately, the declarer did not try this deceptive move, so we won't know if it would have worked at that time.

Did you think of something different? Is so, please comment!

Finding a non-substring [Solution]

The puzzle is here.

In brief, find shortest string which is not a substring of given string.

Solution

---

This will be short too.

Construct the suffix tree of given string, using say a NULL marker for non-existent branches. We can do the marking since the alphabet $\Sigma$ is known.

Now, we can find the smallest depth location where there are no branches. That location gives us a shortest string which is not a substring of the given string.

Suffix trees can be constructed and traversed in $O(n)$ time ($|\Sigma|$ is considered $O(1)$).

Variant on Lights out [Solution]

The puzzle description is: here.

In brief: An $N\times N$ grid of lights, touching a light toggles all lights in the same row and column as that light. Give a formula for number of initial states of lights which can be all turned off.

Solution

---

There are two cases, when $N$ is even and $N$ is odd.

When $N$ is even, you can toggle a single light by touching all the lights in the same row and same column as that light.

Thus, any initial grid can be turned all off by targeting only the lights that are on.

So for even $N$ the formula is $2^{N^2}$ (any grid, basically).

The harder case is when $N$ is odd. There are in fact initial combinations which cannot be turned off (for e.g, the example posted in the problem blog post).

There is a nice invariant of the operation which we can use.

Suppose you treat an on light as $1$ and off as $0$.

Consider the sum over $\mathbb{F}_2$ (i.e. modulo $2$) of the numbers for each row (say $R_i$ for row $i$) and each column (say $C_j$ for column $j$). The possible values of $R_i$ and $C_j$ are $1$ and $0$ (remember: modulo $2$ or $\mathbb{F}_2$).

Then, the touching a light operation, toggles all the $R_i$ and $C_j$ at once: i.e. if $R_i$ was $1$ it becomes $0$ and vice-versa, try it out.

Thus for an initial grid to be able to be turned off, we need $R_i = C_j$ for all $i, j$, as the final grid has $R_i = C_j = 0$.

This is also a sufficient condition, and we can prove it as follows:

Proof:

Assume the grid has $R_i = C_j$ initially.

Suppose $N = 2k+1$. Then consider the $2k \times 2k$ grid formed by the topmost $2k$ rows and the leftmost $2k$ columns.

By our observation about even $N$, we can turn that grid off completely just by touching lights within that grid.

This will result in the last row and last column to have some lights on/off depending on the lights that were touched in the $2k\times 2k$ portion.

But since we started out with $R_i = C_j$ and the light touching operation does not change that, the last row and last column must all be ones, or all be zeroes. In which case the whole $(2k+1)\times (2k+1)$ grid can be turned off: if the last row and column are all ones, we just touch the bottom right light.

$\blacksquare$.

This also allows us to count: Fill in the $2k \times 2k$ grid arbitrarily. The rest of the number are forced.

Thus for odd $N = 2k+1$, the formula we are looking for is $2^{4k^2} = 2^{(N-1)^2}$.