CSE Blog - quant, math, computer science puzzles

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 con

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. :) Solution: 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() ar