Finding a non-substring

Suppose you are given a fixed size alphabet $\Sigma$ and a string $S$ of length $n$ over it.

The task is to find a shortest length string (formed using letters in $\Sigma$) which is *not* a substring of $S$.

Any shorter string will be a substring of $S$.

For example, if $\Sigma = \{0, 1\}$ and $S = 01100$, then a shortest length string will be of length $3$ (for e.g: $000$ will do).

Can you do it in $O(n)$ time?

[Solution]

Variant on Lights Out

This is similar to the Lights Out game, and is actually based on a problem from an old Bay Area Maths Olympiad I had seen.

You have an $N \times N$ grid of lights, each light is either on or off (different lights could be in different states).

When you touch a light, all the lights in the same row and same column as that light toggle, i.e. if they were on, they turn off and vice-versa.

For example, say the grid was

$$\begin{bmatrix} \blacksquare & \blacksquare & \Box\\\Box & \Box & \Box\\ \Box & \blacksquare & \Box \end{bmatrix}$$

Now if you touch the light in the top left corner, it becomes

$$\begin{bmatrix} \Box & \Box & \blacksquare \\ \blacksquare & \Box & \Box \\ \blacksquare & \blacksquare & \Box \end{bmatrix}$$



The goal of the lights out puzzle is usually to turn all the lights off by some sequence of touches, given a starting grid.

This problem is slightly different.

Given an $N$, you need to give a formula for exactly how many grids can be converted to all off by some sequence of touches. The already all off grid should also be counted.

[Note: Rotations of the same grid etc are considered to be different, so there are a total of $2^{N^2}$ grids.]

[Solution]

A good slam.

This is a hand I had posted to bridgebase forums a long time back, as a play problem for intermediate players.

You are South, playing IMPS/Rubber and reach 6H.

How will you play on a club lead?

IMPS None	North ♠ AKJT3 ♥ AQJ ♦ AJ2 ♣ A5
	South ♠ 62 ♥ K6542 ♦ KT843 ♣ 3

[I will post the suggested line in a few days. Please feel free to comment.]

Suggested line (Posted July 23rd 2015, sorry, had forgotten about this)

---

When I posted this problem to bridge base forums, I had included the information that you win the CA, play AQ of trumps, RHO showing out. I missed that when posting on the blog.

In that scenario, the suggested line was to run the DJ. Now I am not so sure if this is a good problem for intermediate players.

Integer part of $(1 + \sqrt{2})^n$ [Solution]

The algorithm puzzle was to find the integer part of $(1 + \sqrt{2})^n$ using only integer arithmetic, in number of operations which is polynomial in $\log n$

[Note: the puzzle post mistakenly said time, instead of number of operations. Fixed now]

Solution

---

By the binomial theorem, notice that

$$ (1 + \sqrt{2})^n = a_n + b_n \sqrt{2}$$

where $a_n$ and $b_n$ are both integers.

Now

$$(a_n + b_n \sqrt{2})(1 + \sqrt{2}) = (a_n + 2b_n) + (a_n +b_n)\sqrt{2}$$

Thus we get the recurrence relations:

$$ a_{n+1} = a_n + 2b_n $$
$$ b_{n+1} = a_n + b_n $$

This can be written in matrix form as

$$\begin{bmatrix}1&2\\1&1\end{bmatrix}\begin{bmatrix} a_n\\b_n \end{bmatrix} = \begin{bmatrix}a_{n+1}\\b_{n+1} \end{bmatrix}$$

i.e.
$$A \begin{bmatrix}a_n\\b_n \end{bmatrix} = \begin{bmatrix}a_{n+1}\\b_{n+1} \end{bmatrix}$$

Giving us

$$ A^n \begin{bmatrix}a_1\\b_1 \end{bmatrix} = \begin{bmatrix}a_{n+1}\\b_{n+1} \end{bmatrix}$$

$A^n$ can be computed in $O(\log n)$ integer operations.

Once we have $(a_n, b_n)$ we can compute the integer part of $a_n + b_n \sqrt{2}$ by computing the integer part of $b_n \sqrt{2}$ using binary search for integer $x$ such that $x^2 \lt 2b_n^2 \lt (x+1)^2$ (or other algorithms) and adding that to $a_n$.

We could also solve this problem by a more straight-forward divide and conquer + memoization algorithm, like we did for Fibonacci earlier, by writing $(a_{2n}, b_{2n})$ in terms of $(a_n, b_n)$ etc.

Ramaiah entrance test question [Solution]

The problem was to show that  the sequence of numbers

$$49, 4489, 444889, \dots $$

where each number is formed by inserting 48 in the middle of the previous number:

$$49 \to 4\underline{48}9 \to 44\underline{48}89 \to \dots$$

has only perfect squares!

Solution

---

Any number is of the form $n$ 4s followed by $n-1$ 8s followed by 9.

This can be rewritten as the sum of

$4444\dots44$ (a $2n$ digit number) 

$44\dots4$  (an $n$ digit number)

1

This is basically

$$\frac{4(10^{2n}-1)}{9} + \frac{4(10^{n}-1)}{9}  + 1 $$

$$= \left(\frac{2\times10^n + 1}{3}\right)^2$$

Integer part of $(1 + \sqrt{2})^n$

Give an algorithm to compute the integer part of

$$(1+ \sqrt{2})^n $$

in number of operations which is polynomial in $\log n$.

Note: I had a mistake earlier by using time, instead of number of operations. Even though we use only polynomial in $\log n$ integer operations, the running time will be $\Omega(n)$, as we are dealing with $\theta(n)$ bit integers.

[Solution]

A question from Ramaiah entrance test

Ramaiah's classes were (are) popular coaching classes for IIT JEE exam preparation in Hyderabad. They themselves had an entrance exam!

These Ramaiah entrance tests contained some very nice problems.

This was a question I first saw on a Ramaiah entrance test when my brother appeared for it (1990). The question is actually much older than that, probably the 1800s.

Anyway, here goes:

Consider the sequence of numbers

$$49, 4489, 444889, \dots $$

Each number is formed by inserting 48 in the middle of the previous number.

$$49 \to 4\underline{48}9 \to 44\underline{48}89 \to \dots$$

Show that all these numbers are perfect squares!

[Solution]

Another textbook hand.

This hand is based on one that occurred in a pairs game at a recent Sectional in Everett, WA.

Assume you are playing teams, though.

You are South and reach 6H, and get a club lead.

IMPS None	North ♠ AQT432 ♥ 72 ♦ A2 ♣ KQ2
	South ♠ 5 ♥ AKJT986 ♦ 43 ♣ A43

How will you play?


Suggested line (added April 16 2015)

---

If trumps are 2-2, you will have an easy 12 tricks.

If you have a trump loser, then you need to do something about the diamond loser.

Spades are a potential source of that trick.

Since you might need entries to dummy, you win trick one in hand.

If spades are 4-2, you need 3 entries in the non-spade suits to setup and cash the extra spade tricks (the SA is an entry for a ruff).

If spades are 5-1, you need 4 non-spade entries. Not sure what to do about a 6-0 spade break.

So the suggested line is:

Win CA in hand. Play spade to A and ruff a spade in hand with one of J,T,9,8. Preserve the 6!

If spades are 4-2, you can now just play trumps from the top.

If spades are 5-1, and LHO hasn't ruffed, you now play the HJ from hand! The opponents cannot duck this (if trumps are 3-1) and now the H7 is the extra entry you need to dummy!

Generate a random heap [Solution]

The puzzle was here.

Solution

---

I will be brief.

For O(n) random number calls, the idea is to grow the heap top down.

n has to be the topmost element. Now n-1 could be any of its two children. Pick a spot for that, randomly.

Now there are 3 new spots available for n-2. Pick one of those three randomly.

This leads to 4 new spots for n-3 and so on.

At the end, you have a random heap.

For an O(1) random number calls algorithm, try proving that there are exactly n! (i.e. factorial of n) heaps, and provide a way to encode/decode a heap given a random number from 1 to n!.

Integration problem [Solution]

The puzzle was to compute

$$ \int \frac{1+x^2}{(1-x^2)\sqrt{1+x^4}} dx$$

Solution

---

As usual, a clever substitution needs to be sought.

In this case, you divide the numerator and denominator by $x^2$ and then make the substitution $t = x - \frac{1}{x}$.

This results in

$$ -\int \frac{dt}{t\sqrt{t^2+1}}$$

which is a standard integral.

Rabbit plays A diamond

[Like the previous Rabbit stories, this is based on the Menagerie characters. This was also posted on bridgewinners.]

---

Karapet was hoping he would cut the Rabbit, but as usual, the Rabbit with his darn luck got paired with the Hog.

"Again? Anyway, how bad can it be? At least it is Secretary Bird and not Papa. It can't be worse than yesterday when...".

Karapet's thoughts were interrupted by the Hog loudly ordering some jam sandwiches.

The Rabbit was the dealer and dealt himself ♠AK ♥KQT9876 ♦A32 ♣A.

He opened 1♥, Secretary Bird, who was on his left passed. Hog surprised everyone by passing, and Karapet doubled.

Just then the waiter arrived with the sandwiches and the Hog offered him some. Saying "No thanks", the Rabbit passed (the sandwich no bid, if I may).

The Bird bid 2♣ , Hog passed (again!), and Karapet bid 2♦.

The Rabbit now thought, "With my diamond honour over Karapet's, my hand has improved. I was going to invite, but I think I should bid game now". His nose quivering with excitement, the Rabbit bid 4♥ with shaking hands.

The Bird, Hog and Karapet passed. The Rabbit passed out of habit. "No double this time Rabbit", chuckled Hog.

The Bird led the ♦T.

The Hog placed the dummy down awkwardly, as he took the Rabbit's cards for a look see. "Wonderfully bid Rabbit. Now you just have to make it", said Hog, while scraping the last globs of jam on the plate with his finger.

These were the cards

Rubber None	Hog ♠ 5432 ♥ 32 ♦ 5432 ♣ 432
	Rabbit ♠ AK ♥ KQT9876 ♦ A76 ♣ A

W	N	E	S
			1H
P	P	X	P*
2C	P	2D	4H
P	P	P

Rabbit immediately called for a low ♦ and Karapet overtook the ♦T with the ♦K.

Now the Rabbit began to think. "What was it? Count your losers? Lose two diamonds and the ♥A. Maybe I should duck the diamond? Or was the rule to win it?".

Then inspiration struck him, "Aces are meant to take Kings!". The decision was easy. He needed to win it and then drive out the ♥A.

So he reached for the ♦A and plunked it on the table. To his dismay, he noticed a card lying beneath the ♦A. He was surprised to see that it was the ♥T.

"What? How? I sorted my cards. Wait there is something on back of ♦A. It is some ja...".

"You never could tell the difference between a heart and a diamond", interrupted the Hog.

"It is a played card. Since you won the trick, you need to lead that to the next trick. Those are our rules", said the Bird.

"What? No. It is not my fault. It is those damn sandwi...".

"In fact I would not be surprised if you didn't notice that you had a club in with your diamonds too", interrupted the Hog again.

Inspite of the Rabbit's protests, he was forced to play the ♥T to the next trick.

These were the four hands

Rubber None	Hog ♠ 5432 ♥ 32 ♦ 5432 ♣ 432
Bird ♠ T98 ♥ J54 ♦ T ♣ JT8765		Karapet ♠ QJ76 ♥ A ♦ KQJ98 ♣ KQ9
	Rabbit ♠ AK ♥ KQT9876 ♦ A76 ♣ A

W	N	E	S
			1H
P	P	X	P*
2C	P	2D	4H
P	P	P

The Bird quickly played the ♥J to get the cheap trick that he had directed himself to.

Poor Karapet had to overtake with his bare Ace. He could cash two more diamonds, but even Rabbit could take the rest.

"Just my luck, as usual. Rabbit had to have a heart in with the ♦, and you had to play the ♥J. If you play low, I can win and promote your Jack for the setting trick!"

"Jam sandwiches, anyone? I am ordering more", said the Hog, licking his fingers.

[You guessed it. It was the Hog who had stuck the cards together with jam, and the Rabbit had in fact sorted his cards correctly.]