Interesting end position [Bothell sectional swiss teams hand]

This is a hand from a recent swiss teams event in Bothell, near Seattle.

You are South and dealer, holding 85, AK954, KQJ82, A

You open 1H, LHO overcalls 2C, partner bids 2H, pass, 3D from you, pass, 3H by partner and you buy the contract in 4H.

LHO leads the CK and you see:

IMPS Both	North ♠ AJ942 ♥ 732 ♦ 96 ♣ 854
	South ♠ 85 ♥ AK954 ♦ KQJ82 ♣ A

W	N	E	S
			1H
2C	2H	P	3D
P	3H	P	4H
P	P	P

You win the CA, and play the DK. LHO wins the DA and plays back a club, which you ruff (RHO following to both clubs).

Now when you play HAK, LHO follows with the 6 and Q, and RHO with the 8 and T. When you play the DQ, LHO shows out, throwing a club.

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




At the table, I decided to play RHO to hold the third trump, and if that is the case, you can guarantee the contract!

[Note that there is 50% chance that RHO holds the third trump, using a vacant spaces argument. If you consider some restricted choice argument about LHO throwing HJ from QJ6, the chances are even more. LHO might have even ruffed your DQ...]

After getting the news of the 5-1 diamond split, and assuming RHO has the third trump, you can make it as follows:

Ruff a low diamond in dummy, and play a club from dummy.

If RHO started with 2 clubs, (3=3=5=2 hand), then, on the third club from dummy RHO is caught in a strange squeeze. If he throws a diamond, your diamonds are good. If he ruffs with the HJ, you can throw a loser. Thus he is forced to throw a spade, and come down to 2 spades.

Once RHO throws a spade, you ruff the club in hand (and are now left with 2 spades, a trump and 2 diamonds), and play spade to the A, and a spade back.

If RHO wins the second spade, he can cash his trump, but has to lead into your diamond tenace (thanks to the D8!).

If LHO wins the second spade, then he can only return a spade or a club, in which case you make your last trump en-passant, and can cash the DJ for the tenth trick.

RHO following to the third club is similar.

At the table RHO did in fact have a 3=3=5=2 hand, and was subject to the squeeze, and the defense chose to let RHO win the second spade to lead into the diamond tenace.

Did we win IMPS on this hand? Unfortunately no, as our teammate at the other table led the DA, resolving any issues for declarer, resulting in a push.

If you want to try playing around with the full hand, you can use this handviewer link.

Sort an almost complete binary search tree array.

Almost complete binary trees can be represented compactly using arrays, where the children of $a[i]$ are $a[2i]$ and $a[2i+1]$, with the root being $a[1]$ (assume index of the array starts at 1 for this problem).

Given an almost complete binary search represented in such a manner: i.e. given the array $A$ representing the tree, can you give an $O(n)$ time and $O(1)$ space algorithm (WORD RAM model) which will sort the array?


For example if the tree is [image swiped from someone's webpage in cmu]

the corresponding array would be

$$ [10, 6, 18, 4, 8, 15, 21] $$

and your algorithm needs to sort it so that it becomes

$$ [4, 6, 8, 10, 15, 18, 21] $$

 [I have labelled this hard, because the solution I have uses a result which is hard. Hint: You can find that result on this blog]

[Solution]

Find the unique root

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]

Matchpoint greed?

This is a hand from yesterday's Matchpoint game at Mercercrest bridge club, in Mercer Island near Seattle.

You are South and end up in 4S, after showing 6 hearts and 5 spades, and North showing a diamond suit.

[In the actual hand, East was declarer, made South here for convenience]

West leads a trump. You see:

MPS Both	North ♠ KT9 ♥ - ♦ KT97642 ♣ KT5
	South ♠ QJ543 ♥ A87543 ♦ A5 ♣ -

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

[Bidding given is as it happened at the table]

East wins the SA (low from dummy), and returns a trump (win in dummy with the T), West following.

Now what?

At the table, South played a diamond to the A (both opponents following with low cards), and a diamond toward the K, with West playing the DJ.

If this was IMPS, you have a clear play to duck this trick!

You are short of entries to dummy. If diamonds break 3-1 (singleton with East), and you play the K, East might be able to ruff and dummy's diamonds will be dead. There will be no way to establish (the Q is still out) and cash the diamonds.

If you duck, the diamonds are already setup, with the SK as an entry.

Coming back to matchpoints.

If you duck, you guarantee 11 tricks.

If you go up with the K and diamonds are 2-2, you make 12, risking going down if diamonds are 3-1.

At the table, South got greedy and went up with the K. Unfortunately for her, this got ruffed, and she ended up down 2, when she threw a heart on the club return.

Looking at the traveller, she would have made a near top if she made 11 tricks. Getting greedy, she got a near bottom.

I think she got greedy, but perhaps you disagree. How would you have played?

Sorting with reversals II [Solution]

The problem was:

You have an size $n$ array of zeroes, ones and twos. The only write operation is to reverse a sub-array (paying cost equal to the length of the the sub-array). Can we sort the array in $O(n \log n)$ cost?

Solution

---

One solution is to use divide and conquer.

Suppose you divided the array into two approximately equal halves, and sorted each sub-array separately.

Then you will see an array like


$$0 \dots 0 1 \dots 12 \dots 2\vert 0 \dots 0 1 \dots 1 2 \dots 2$$

Now, we can sort a chunk of 2s and 0s by doing a cyclic shift of the chunk $2 \dots 2 0 \dots 0$, so that it looks like $ 0 \dots 0 2 \dots 2$.

We can do a cyclic shift of an array using only three reversals. Say you want to cyclic shift $a_1, \dots a_m$ to look like $a_k, a_{k+1}, \dots, a_m, a_1, a_2, \dots a_{k-1}$. This we can achieve by first reversing $a_1, \dots a_{k-1}$ and $a_k \dots a_m$, so the array now looks like $a_{k-1}, \dots a_1, a_m, \dots a_{k+1}, a_k$ and then reversing the whole array.

Each reverse costs $O(n)$, and with a constant number of these, give the two sorted halves, we can sort the whole array.

Thus the cost satisfies the recurrence

$$ C(n) = 2 C(n/2) + O(n)$$

which gives us $C(n) = O(n \log n)$.

Consecutive product sum [Solution]

The task was to find (without pen and paper)

$$\sum_{k=r}^{n} k(k-1)\dots(k-r)$$

Solution

---

Let $S_k = k(k-1) \dots (k-r)$.

One way to solve this is to notice that

$$(k+1)k(k-1)\dots(k-r) - k(k-1)(k-2)\dots(k-r)(k-r+1)$$

$$= (k+1-(k-r+1))k(k-1)\dots(k-r) = r k(k-1)\dots(k-r)$$

i.e

$$P_k - P_{k-1} = rS_k$$

where $P_k = (k+1)k(k-1) \dots (k-r)$

Thus we get a sum where most of the terms cancel each other out (called a telescopic sum) and the answer is simply $P_n - P_{r-1}$ which is

$$\frac{(n+1)n(n-1)\dots(n-r)}{r}$$

There are other solutions, like writing in terms of binomial coefficients etc, not sure we can do those without pen and paper though.

Sorting with reversals II

In a previous post, we were asked to sort an array (of size $n$) consisting only of the elements 0,1 and 2. The catch being: the only write operation on the array that was allowed was to reverse a sub-array $A[i, i+1, \dots, j]$.

The task was to use $O(n)$ reversals.

This problem is similar. We still have an array of zeroes, ones and twos, and we can only write by doing reversals.

The difference is that the reversal has a cost associated with it.

Reversing the sub-array $A[i, i+1, \dots, j]$ has cost $j-i+1$ associated with it (similar to what you would normally pay when doing an actual reverse).

Can you now sort the array with $O(n \log n)$ cost?

[Solution]

Consecutive product sum

Can you solve this without pen and paper?

Suppose $r \gt 0$ is a fixed positive integer.

Can you give a formula (in terms of $n$ and $r$) for


$$ \sum_{k=r}^{n} \left( \prod_{j=0}^{r} (k-j) \right)$$

i.e.

$$\sum_{k=r}^{n} k(k-1)(k-2)\dots(k-r)$$


[Solution]

All is not lost

This hand came up while playing a local game at Mercercrest bridge club in Mercer Island, near Seattle (one heart spot modified for the narrative). The club participates in the common game, night version.

You are West holding AQ5, QJ, KT654, J83. E/W vul with E dealer.

After two passes, you open 1D (likely 4+), double by LHO, 1H by partner, 2S by RHO which gets passed out.

You lead the HQ and you see:

MPS E/W	North ♠ K832 ♥ A843 ♦ 73 ♣ Q62
West ♠ AQ5 ♥ QJ ♦ KT654 ♣ J83

W	N	E	S
		P	P
1D	X	1H	2S
P	P	P

Not everyone will double with that hand.

Declarer goes up with the HA (partner encouraging) and plays a club to the A, partner showing an odd number.

Now declarer plays the S9. You choose to duck, as dummy and partner both follow with a low card.

Now declarer plays another spade, on which you go up with the SA, partner following.

To beat 2S, you need to be able to get 2 heart tricks, 2 diamonds and 2 spades. Thus you assume partner is 2-4-4-3 with the DA and DK and a fourth round of hearts can promote your SQ.

You play the HJ, it wins and you now quickly play a low diamond, and partner wins the DA. Partner now plays the HK, declarer following with the T.

At this point you realize your mistake. Instead of a low diamond, you should have played the DK first. Then a diamond to the DA, HK, followed by another heart by partner, and you get your SQ.
[A defensive version of the cross-ruff principle for declarer: cash you side suit tricks before you start your crossruff, otherwise the opponents(s) will throw the cards in the side suits and you won' get your winners there.]

As you played it, declarer (with a 4-3-2-4 hand) can throw his losing diamond on the fourth heart.

But all is not lost!

Partner seems to have started with HK9xx in which case you have a chance!

You are left with two clubs (declarer had played one round earlier). You throw one of them on the HK. Now when partner plays the H9 (the top heart at that moment), if declarer throws his last diamond, you can throw your last club! Partner can now give you a club ruff, for down one.

Even if you make a mistake, it might not be the end. There still might be opportunities lurking. The same is true not just for a single hand, but for the whole match. Don't let one mistake mess up the other hands for you, which will happen if you dwell upon your mistakes. You should definitely look at your mistakes (how else will you improve?), but only after the match. It is easier said than done, though.

[Beating 2S gives you just an average+ (while playing and making 3D is a near top), so, I guess the real moral of the story is to bid 3 over 2 in matchpoints, even with only an eight card fit...]

Sorting with reversals [Solution]

The problem was to sort an array consisting of only 0,1,2 only using $O(n)$ reversals of subarrays.

When I posted this problem, I had one solution in mind (which I will not reveal just now, but try to reuse for the next problem), without realizing that swapping $A[i]$ and $A[j]$ can be done using two reversals: reverse $A[i, \dots, j]$ and then reverse $A[i+1, \dots, j-1]$!

So any sorting algorithm which uses $O(n)$ swaps should do.

For example, using the Dutch National Flag (DNF) algorithm, we can achieve sorting in $O(n)$ reversals.

Collins made a nice observation that if we use the DNF algorithm, we don't even need to do the second reverse when trying to swap $A[i], A[j]$. See the comments on the question.