All starting points

This is an extension of a classic puzzle.

You have a circular road, with $n$ petrol bunks (or gas stations as called in America) located somewhere along the road. You are given the length of each segment of the road, which is between two petrol bunks. You are also given the amounts of petrol left in each bunk. You are also told that the total amount of petrol is just enough to complete exactly one lap of the circular road, using a car that starts with an empty tank. The car has infinite capacity and you fill whatever you can when you reach a petrol bunk.

Now given a car with an empty tank, you need to find out in $O(n)$ time, all the possible starting points which will allow you to complete the lap. [The classic puzzle was to prove that there is a such a starting point].

The petrol bunks are numbered $1$ to $n$, and you are given an array $p[1, \dots, n]$ of the amounts of petrol, and a distance array $d[1, \dots, n]$ of the distances between the petrol bunks ($d[i] = $ distance between $p[i]$ and $p[i+1]$). The output will be a list of numbers between $1$ and $n$, denoting the petrol bunks you can start at.

Assume that one unit of petrol covers exactly one unit of distance.

[Solution]

Four Numbers Game II

In an earlier post a question was left open. I will repeat the question here.

You start with $n$ integers $a_1, a_2, \dots, a_n$ and in one step you perform the following transformation

$$(a_1, a_2, \dots , a_n) \to (|a_1-a_2|, |a_2 - a_3|, \dots, |a_{n-1} - a_n|, |a_n - a_1|)$$

($|x| = $ absolute value of $x$)

You keep performing this operation till all the numbers become zero.

Find all $n \gt 1$ (with proof), such that no matter which integers you start with, the numbers eventually become zero.

Opening Lead problem

This is a hand from a recent regional in Lynwood, WA (near Seattle).

Playing a knockout game,  you hold JTx, Kxxx, xx, Jxxx, white vs red.

LHO is dealer and opens 1S. Partner overcalls 2H, RHO bids 3D. You bid 3H, LHO bids 4D, partner bids 4H, and opponents buy the contract in 5D (the auction is as I remember, it might have been different at the table).

What would you lead?



You probably led a heart? If so, hope you had led the HK!

These were the four hands (you are west)

IMPS N/S	North ♠ Axxxxx ♥ T ♦ Txxx ♣ AQ
West ♠ JTx ♥ Kxxx ♦ xx ♣ Jxxx		East ♠ KQ ♥ AQJxx ♦ xx ♣ KTxx
	South ♠ xx ♥ xxx ♦ AKQJx ♣ xxx

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

If you lead a low heart, declarer can make the contract by setting up the spades. Partner cannot attack clubs.

If you lead the HK, you can hold the lead and switch to a club, establishing your club trick before declarer can set up spades, and the contract goes down one.

A club lead would have worked too.

Leading the HK is "standard" with that hand, and I believe most advanced players would find it.

Span sums [Solution]

The problem was here.

In short, compute the total of the spans for each sub-array of a given array, the span of an array being the difference between the maximum and minimum element of the array.

Solution

---

Note that it is enough to figure out the sum the maximum elements of each array [and minimum, and then take the difference].

Suppose we want to find the max sum of sub-arrays of an array $A[1,\dots,n]$, and the maximum element of $A$ appears at $A[M]$. Assume the elements are distinct for now, but does not really matter.

Now $A[M]$ is the maximum of any subarray $A[i,\dots,j]$ where $i \le M \le j$ and thus contributes $A[M]\times M \times (n-M+1)$ to the total we seek.

Now we recursively compute the totals for $A[1,\dots,M-1]$ and $A[M+1,\dots,n]$ and add all those up.

This can be done in $O(n)$ time, if we compute the cartesian tree corresponding to the array (which can be done in $O(n)$ time).

The cartesian tree is basically a max-heap whose inorder traversal gives back the array in the order $A[1], A[2], \dots$. The whole tree corresponds to $A[1, \dots, n]$, while the left subtree of the root corresponds to $A[1, \dots, M-1]$ and the right sub-tree corresponds to $A[M+1, \dots, n]$.

In order to get past the distinctness assumption, we can work with $B[i] = (A[i], i)$ instead.

[See: http://ruffnsluff.blogspot.com/2015/05/max-area-in-histogram-solution.html for an explanation of Cartesian trees. There is a diagram too!]

Prime binomial sum [Solution]

The problem was to show that

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

is divisible by $p^2$ for a prime $p \ge 5$.

Solution

---

Now working in the field $F_p$  (where division makes sense) we have that

$$ \frac{\binom{p}{k}}{p} = \frac{(p-1)!}{k! (p-k)!}  = \frac{(p-1)(p-2)\dots(p-k+1)}{k!}$$

$$ = \frac{(-1)(-2)\dots(-(k-1))}{k!} = \frac{(-1)^{k-1}}{k}$$


Let $ T = {\lfloor 2p/3 \rfloor}, U = \lfloor \frac{T}{2} \rfloor$

Thus the sum we need to show divisible by $p$ (note that we divided by $p$ already) is

$$\sum_{k=1}^{T} \frac{(-1)^{k-1}}{k}$$


$$ =  \sum_{k=1}^{T} \frac{1}{k} - 2\sum_{k=1}^{U} \frac{1}{2k}$$

$$ = \sum_{k=U+1}^{T} \frac{1}{k}$$

Now $T + U + 1 = p$ so this sum becomes

$$ \frac{1}{T} + \frac{1}{U+1} + \frac{1}{T-1} + \frac{1}{U+2} + \dots $$

(by coming terms from the ends)

$$ = \frac{p}{T(U+1)} + \frac{p}{(T-1)(U+2)} + \dots $$

which is divisible by $p$.

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.

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]