Friday, April 10, 2009

A few algorithmic puzzles

Hello There,

Today I will be telling you about a few algorithmic puzzles.

The talk basically involves a problem with its solution. So, if you are a reader who wants to try these out before peeking out at the solution, beware.

Also, I would say that unfortunately, one of these puzzles has been made too popular through interview forums and other discussions, which makes the solving techniques used for these kinds of puzzles look futile.

It is my opinion that interview forums should operate a little differently.

Too much digression, now I will come straight to the point.
Below, I present the first of the two questions that I will be tackling in this blog.

Prob.1) Given 2 special eggs and a building 100 floors high, can you dear reader, find the minimum number of drops in which you can find the height after which these 2 eggs start breaking.

Oh yes, the eggs are special in the sense that they wont start breaking unless dropped from or above the threshold height.

Sol.) The key fact here is to realise that you need to prove the minimality of your solution for which the most general approach that you can use is a recursive one.

Infact, in my opinion, for handling discrete minimization/maximization problems, the best way is to establish a recursive equation. Once you have done that, establishing the lower/upper bound is as easy (hard) as solving the recurrence.

Okay, did you try this problem on your own so far. If yes, did you arrive at the first wrong answer most people do (19). Or did you arrive at the correct answer 14?

Whatever you did, probably reading the explanation for 14 below won't hurt. (I will not explain how people arrive at 19).

Well, the first thing we see is that, its a minimization problem. A good thing about these problems is that, they can always be inverted. You can recast it into a maximization problem which maybe (and in most cases, in my experience is) easier to answer.

There is actually a reason for this as well. Maximization problems tie well with out intuition of "overflow". The analogy is that a bucket is said to hold a 'maximum quantity' when adding anymore quantity leads to 'quantity spillage'.

In mathematical terms, you try to show that a set S contains maximum elements with Property P when adding anymore quantity of elements with Property P will spill one or more quantities. (However, there maybe a few subtle issues involved.) More on this later.

A small, but powerful technique.

In this case, the corresponding maximization problem is to determine the maximum height you can scale using 2 eggs and 'd drops.'

Vary 'the number of drops' till the height scaled is greater than or equal to the number of floors in the question.

Well, the above discussion suggests a not-too-hard/easy-to-find recurrence for this problem.

Try one last time before I give it away in its full grandeur.

Let us assume that T(e, d) indicates the height you scale when you have 'e eggs' and 'd drops'

Hmm. I have selected the notation. What remains is notion. As Gauss remarked, it is notion not notation which is important.

But a notation is also good enough as a starting point. Now - the notion.

Well, its recurrence, right? (Notation says so)

Then the corresponding notion is to setup on its RHS another invocation(s) of the same. (Notion)

Clearly it involves using on RHS some quantity smaller than the quantity you begin with so that the recursion terminates.

SO, what can that be? Well you pick an intelligent height, and go for the first drop. And then you have d-1 drops left. Hold it. You can see your recursion now.

After 1st intelligent drop, you can scale T(e, d-1) floors. The intelligent choice must be so placed, that if the egg breaks, then the culprit floor among the floors below is locat-able with 'e-1 eggs' and 'd-1 drops'. That is the intelligent drop is one level above T(e-1, d-1)!

Thus, T(e, d) = T(e, d-1) + [T(e-1, d-1) + 1]

And for recursion termination?

T(1, d) = d.

NOTE: I have not highlighted (maybe even not told)in this problem where does that 'overflow analogy' is. But rest assured, you can find it.

Will post it later, and then remove this note.

Prob. 2) Well, now we come to the second problem. It is from a competition called felicity (organised by IIIT Hyderabad).

The problem asks you to 'maximize' the number of elements in a set S. All of the elements in S come from a set A of natural numbers which contains numbers from 1 to 2000.

But you need to be sure that you do not include a number thrice (or one-third) and five-times (or one-fifth) of some number you already picked. These elements thrice (or one third) and five times (or one-fifth) are called respectively the first-kin and the second-kin of the number picked.

You need to determine the maximal size the set S can be.

Go on, try it! Below I produce the solution.

Sol.) The key fact here is that it is (indeed) a direct maximization problem. We can try to use the 'overflow analogy' as I demonstrate below. As of now I have not tried a recursive solution to this problem myself, but anyways I have put the 'overflow analogy' to good use here.

See if you can arrive at the solution using what has been said this far (which by the way is no hint..but its okay to try with the assurance that you may need to invoke this process, no matter how insignificant the 'place of invoking' is).

Well, if you tried and did not get it (or maybe did not try it at all) here is the solution again in full grandeur.

Ask yourself, when does overflow begin?
The answer is when maximum cardinality is reached, right?
And how exactly do I arrange matters to create it?

It is this question which puts your creativity on trial.
You can begin with a few cases simpler to analyze. For example limit the size of the set A to 10. How big set S can you create now?

The first choice, guys (usually) come up with. is S = {1 2 X 4 X X 7 8 9 X}.
(X indicates the absence of an element.)

Have we achieved true maximality?
Sadly, no.

Hmmm... these guys say that 'overflow analogy' says that placing any absent element into the set S would cause spill and therefore, they claim that they have achieved true maximality.

And this is where we change all the rules. This is precisely the subtlety I talked about earlier. Call it the subtle issue.

You can see that you can make S bigger by removing 1 and keeping 3 and 5 in the set. Thus, the notion of 'quantity spillage' in these problems is of a different kind. Here, your bucket holds maximum quantity when there are no left out quantities keeping which back spills less.
For example, consider one second answer : S = {X 2 3 4 5 X 7 8 X X}. Hell, its no good than the first one.
This configuration (in second answer) is bad as we can allow 'overflow of just one quantity (2) by adding two quantities (6, 10).

A little experimentation shows true maximality is achieved when S is the set with precisely the above modification= {X X X X 4 5 6 7 8 9 10}

You can see that adding any other element leads to 'spillage'. Also, notice that no quantity 'spills less than it contributes'. That is, you can't (in this particular example) add two quantities spilling out just one.

Thus, we have achieved true maximality.

Similarly, for A = {1, 20} the maximal S is
{1(stop) 7,8,9,10,11,12,13,14,15,16,17,18,19,20}.

But, hold your horses. Do you see it?
See what?
An Aha! insight my friend.

The maximal solution outlined above has contiguous elements! Maybe its 2 or 3 sections but within each section, elements are contiguous.

We will prove that you can always arrange matters so that this condition holds true.

First, notice that your examples above for 10 and 20 elements have one thing in common.
Both of them end at the last element.

So we can try beginning in general with the last element. We will create a decreasing sequence of numbers till we hit n/3. We list all the numbers starting from n down to floor(n/3) + 1. Call these numbers Range-1-start and Range-1-end respectively. You can see that Range-1-start and Range-1-end hold a decreasing sequence of numbers.

Next, we make another sequence starting from (Range-2-start) ceiling(Range-1-start/5) - 1 and continue down till we hit floor(Range-2-start/3) + 1.

This way, you go on till you run out of elements.

Creating this sequence for 1st 300 numbers goes like this.

first-sequence: all numbers from 300 down to 101 (inclusive)
second-sequence: all numbers from 20 down to 7. (inclusive, 21 and others are not there as including them would result in throwing away elements of the first sequence).
third sequence - Containing just the number 1.

This way, you can achieve maximality for any n. It seems you have already proved it for its clear enough.

In case you have not, here is one proof. Including any discarded element will cause spill of one or more than one entries and you don't have the bad situation of more elements getting added at expense of fewer getting discarded in the above construction.

Consider the case when A holds 300 elements. Discarded elements are between 21 and 100 (inclusive) and also between 2 and 6 (again inclusive). Putting 'boundary elements' looks like a dangerous idea; we will analyze it later (It is related with the subtle issue). Putting non-boundary elements leads to spillage of two and is definitely wasteful.

Now back to 'boundary elements' (and neighbors). Putting these back spills an element from the first sequence which cannot lead to the subtle issue as the second-kin of the spilled element from the first set is not in any of the two sequences. Putting it back will lead to one other spillage. So it is also wasteful. And there, finally you have seen true maximality.

Also, I will help you with an extample of one boundary element. For example in the case of A holding 300 elements, if you add 100 to the set S, you spill 300. Hmm. can subtle issue arise? And can it lead to inclusion of two elements at the cost of one 300?

No, it won't. For after inclusion of 100, 300's first-kin, you cannot include its second-kin, 50. Including it will spill 10.

This is the general idea behind the proof which can be easily made more rigorous.

NOTE: Some of my friends told me that it was difficult to make the connection between consecutive-ness of elements and the maximality of the set S. I agree.

Also, they say that 'I got lucky' by guessing the pattern with 2 examples which normally requires many turns. And they also say what if the pattern did not hold for long. I could have got stuck.

True. But my answer is that I did not stop at 2 trials (examples for 10 and 20). I tried a total of 20 trials! (From |A| = 10 to |A| = 30)!!

Thats what mathematical problem solving is about. This is what research is about and this is what interview forums do not do. And yes, this is as far from this research as anything might be but my primary attack is not at its unimaginable light-yearish distance from research but it is primarily again at interview forums which do not promote students to think.

They make you more of an analyst and less of a designer.
And the subject was called 'Design and Analysis of algorithms'. Absurd

Enough for now.

There are a few other problems, I would later include in this post itself. Right now, I want to rest.



Amar Bajpai said...

first one was good but second one was mind blowing & nicely put.

taking 2 smaller sets for explanation was worth beause that itself made eth crystal clear. (i guess second sequence has been taken w/o taking the conditions into account? ie take 1--19, but check for the conditions)

i wonder this will work for more primes (3,5,7) as well.

in the same example
Largest prime LP : 7
Smallest Prime SP :3
maximum element max :300

1st sequence : [300--100) ie [max--max/SP)

2nd sequence : max = (max/SP)/LP ie max = (300/3)/7 = 14


keep updating the puzzles. at least this will make your frnds read sth real good.


Akash said...

Hello Amar,

Thanks for the corrections you suggested. I have incorporated them.