5D making 5

This hand reminds me of Belladonna's famous 6D hand (see this: http://ruffnsluff.blogspot.com/2015/01/6d-making-6-hand-played-by-belladonna.html).

Playing a casual game [lunch bridge in Google Kirkland], you are South, and end up in 5D with west preempting in spades (showing exactly 6).

The bidding: partner (North) opens 1C, East passes, you bid 1D, 2S by West, and you end up in 5D (3NT is better).

West leads the HJ.

This is what you see.

IMPS None	North ♠ A32 ♥ Q32 ♦ K42 ♣ AT82
	South ♠ 4 ♥ K654 ♦ AQJ53 ♣ K93

W	N	E	S
	1C	P	1D
2S	....

You play low from dummy and RHO plays low too, and you win the K in hand.

How will you play? [For simiplicity, assume 3-2 diamonds if you want].


You have 9 tricks (3NT would have been great!), and need two more. So a simple squeeze or a simple endplay will not work (you get back one trick). In fact, you might need to combine both!

Assuming trumps are 3-2, there are a couple of possible lines.

1) Play RHO to have QJx of clubs.

2) Play RHO to have a single club honour and 4+ clubs.

If you go for line 1), you can eliminate spades while drawing trumps, and play AK clubs and a club, setting up your 4th club. RHO is in, and now has to give you the 11 trick by playing a heart.

If you go for line 2), you can eliminate spades while drawing trumps, but have to watch for RHO's discard. If RHO discards a heart (presumably from 3-4-2-4) you can now play a heart to the Q. If RHO now returns a club honour you can setup your clubs. If RHO returns a low club, you can win in dummy and lead another heart, setting up the heart in had, and endplaying RHO again.

If RHO discards a club, you can try to endplay RHO in clubs (AK and club), forcing RHO to give you a heart trick with the Q, and an entry to dummy for the good clubs.

Line 2 seems better.

You squeeze RHO, then endplay RHO while setting up a suit and generate two tricks in the process, similar to the hand played by Belladonna.

Interestingly, if RHO had 5 hearts, the winning defense is to win the HA at trick one, and give partner a ruff!

Span sums

A span of an integer array is the difference of the maximum and the minimum elements.

For example, span of $[3,4,8,1,-1]$ is $8 - (-1) = 9$. The span of a single element array is $0$.

Given an array $A$ of $n$ integers, can you find the sum of spans of all the subarrays of $A$? (subarray is a contiguous subset). For example $[4,8,1]$ is a sub-array of $[3,4,8,1,-1]$ and $[4,8,1, 5]$ etc.

Try for an algorithm which runs in $O(n)$ time.

[Solution]

Prime binomial sum

I believe this is a problem from an International Mathematical Olympiad. [Don't know the year].

$p \ge 5$ is a prime number.

Show that

$$ \sum_{k=1}^{\lfloor 2p/3 \rfloor} \binom{p}{k}$$ is divisible by $p^2$.


[Solution]

Spots and Entries

This is a hand from a casual game in Google Seattle and an instructive hand about using spots and unblocking for entry management.

Assume IMPS.

You are South and hold AJ92, AQ87, K6, KQT.

Your RHO opens 1S, you double, LHO passes, and you eventually end up in 3NT.

LHO leads a low club, and you see:

IMPS None	North ♠ T873 ♥ 2 ♦ A5432 ♣ 543
	South ♠ AJ92 ♥ AQ87 ♦ K6 ♣ KQT

RHO wins the CA and returns a high club spot.

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






Assuming RHO has the HK (which you need to, and is quite likely), you can guarantee the contract, thanks to the spade spots!

With ample entries to dummy, you would have 3 spade tricks, 2 hearts, 2 diamonds and 2 club tricks.

The spade spots and the DA can help you achieve that.

Consider what happens when you win the second club trick and lead the spade jack from hand.

Suppose RHO wins the SJ and returns a club. Now you play a diamond to the A, and play the ST. If RHO covers the ST, you win, and you have a spade entry to dummy to take the heart finesse, and 3 spade tricks. If RHO ducks the ST, you drop the 9 from hand, and then play the S8. If RHO does not cover, you take the heart finesse. If RHO covers, you win and have a spade entry.

If RHO ducks the SJ, you play the S9 to the ST. If RHO ducks this, you have enough entries. If RHO wins the ST, you can win the club return, play a diamond to the A, and play the S8, and be in a situation similar to the previous paragraph.

Sort binary tree array [Solution]

The problem was to sort an almost complete binary search tree, which is represented as an array: the children of $a[i]$ are $a[2i]$ and $a[2i+1]$.

The catch was to sort in $O(n)$ time and using $O(1)$ space.

[Detailed problem statement is here]

Solution

---

The solution depends on the following

1) If $a[1], a[2], \dots, a[2^k-1]$ is already sorted, then we can sort $a[1], a[2], \dots, a[2^{k+1}-1]$ by interleaving $$\{a[1], a[2], \dots, a[2^k-1]\}\quad \{a[2^k], a[2^k+1], \dots, a[2^{k+1}-1]\}$$ as

$$ a[2^k], a[1], a[2^k+1], a[2], \dots, a[2^{k+1} -2], a[2^k-1], a[2^{k+1}-1]$$

Now this interleaving can be done on linear time and constant space, using the solution in the blog post here: http://ruffnsluff.blogspot.com/2015/01/solution-to-rearrange-array-algorithm.html


So starting with $k=1$ and so on, we can do this in time  $n + n/2 + n/4 + \dots$ = $O(n)$ and $O(1)$ space.


[Sorry for the terse solution, I suggest you try it out with a few examples].

Find the unique root [Solution]

The problem was:

It can be shown that the below equation has a unique root in the interval $(0,2)$.

Can you find it?

$$ \sqrt{2 + \sqrt{2 - \sqrt{2 + x}}} = x $$

Solution

---

This can be solved neatly using trigonometry!

Set $x = 2\cos \theta$ for some $\theta \in \left[0, \dfrac{\pi}{2}\right]$

Now $$\sqrt{2+x} = \sqrt{2 + 2\cos \theta} = 2 \cos \frac{\theta}{2}$$ using the double angle formula $1 + \cos 2y = 2 \cos^2 y$.

Then use $1 - \cos 2y = 2 \sin^2 y$ and $ \cos y = \sin (\pi/2 - y)$, and you can find out what $\theta$ is.