Oct 14, 2008

The ring of Numbers

Again: copied from Saurabh Joshi's blog

Problem : Integers from 1 to n are arranged in a circle in some random permutation. Prove that there exist a set of k consecutive integers on the circle sum of which would be at least k(n+1)/2.

Solution : 
Highlight the part between the * symbols for the answer.
* Set of k consecutive integers can be uniquely specified by the start position and the direction ( clockwise, or counter clockwise ). We will call it a k-box. Because they are arranged in a circular fashion there are n positions. We will assume clockwise direction. For each of these n position compute sum of its corresponding k-boxes. Sum of all these k-boxes would be kn(n+1)/2. The reason is that \sum_{i=1} ^{n} i = n(n+1)/2. and each number will appear in k different k-boxes.

So on average, each k-box makes a contribution of k(n+1)/2. So there exist at least one k-box which makes contribution of at least k(n+1)/2.

Or, in other words. If none of the k-box can make contribution of at least k(n+1)/2 then the total of all k-boxes would be strictly less than kn(n+1)/2 which is a contradiction. *

Limitation of a data structure

Problem : Let there be an abstract data structure D. D is a k-Max data structure, in a sense that on performing delete() on this data structure, it returns the k-th largest(Maximum ) element of the elements stored in it. Only two operations are allowed on D, insert(number) and delete(). Obviously, insert(n) will insert the given number n to the data structure.

Prove that, it is impossible to implement D in a way such that both insert(n) and delete() takes O(1) time. Or in other words, any implementation of D will have at most one operation that can perform in O(1). The other operation can not be implemented in O(1).

This has been copied from Saurabh Joshi's blog. He acknowledges Prof. Sundar (CSE, IITB) for the problem. :)

Highlight the part between the * symbols for the answer.
* Let us assume that we have such a data structure D. and let k=1, that is D is a 1-max data structure, which returns the largest element in D. Also, assume that insert(n) and delete() are both O(1) operations. Now, if I am given n integers. I would insert them one by one. After all insertions I will perform deletions. It is easy to see that this way, I can sort n integers in time O(n)!!!!

It should be fairly easy to see why this is true for any value of k>0. In linear time we can find the largest, say Max, of n integers. I can insert (k-1) dummy integers which are greater than Max in D. And again, I have a linear time sorting algorithm in the worst case!!!

It is a clear contrast to logarithmic lower bound for sorting.

Now we know why we don’t have any such data structure :-) *

Fraction Brainteaser

Source: Sent to me by Gaurav Sinha Problem: Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20...