Solution to Problem 1: The End of Corruption

Well, the obvious solution to this problem is to keep storing the wealth information in a list, and whenever you see a -1, delete the largest element in the list and print it out. ------------------------------------------------------------- Algorithm 1 ------------------------------------------------------------- for (i = 1 to N+M) { x = read next input if (x != -1) insert x in L else find the maximum element m in L print m delete m from L } ------------------------------------------------------------- How long will this algorithm take? Well, that depends on how much time it takes to insert x in L, find the maximum element m from L and to delete the maximum element from L. We use an array A and a integer variable Next to maintain the list L. Next points to the position where the next element is to be inserted. Thus, A[1] ... A[Next-1] contain the elements in the list. For example if the list consisted of the elements 3 9 21 4 14 then we would have i 1 2 3 4 5 6 7 ... A[i] 3 9 21 4 14 and Next = 6. In this scheme, inserting an element involves storing it at A[Next] and increment Next by 1. This takes just 2 steps. So inserting N elements will take roughly N steps. So if we inserted 8 into the above list we would store it at position 6 and increment Next to 7 and get: i 1 2 3 4 5 6 7 ... A[i] 3 9 21 4 14 8 and Next = 7. What about finding the maximum and deleting it? Well finding the maximum would require a scan of the entire array and thus if there are k elements in the array it would take roughly k operations. Deleting the jth element involves moving the (j+1)st element to position j, the (j+2)th element to position (j+1) and so on. Thus it would take (k-j) steps. For instance, to deleting the maximum element in the above list would involve shifting everything from position 4 to 6 left by one to get: i 1 2 3 4 5 6 7 ... A[i] 3 9 4 14 8 and Next = 6. Thus, inserting N elements would cost roughly N^2 (1+2...+N is N(N+1)/2 which is roughly N^2). The cost of deleting M elements would take N*M operations and since M < N, the total cost is roughly N*N. Can we find the maximum and delete it faster? Well, if the array was maintained in sorted order, then maximum would always be found at position A[Next-1]. To delete the maximum element, you just have to decrement Next by 1. So both finding the maximum and deleting takes 1 step each. For instance, if the array was maintained in sorted order then, prior to the deletion above, it would have looked like: i 1 2 3 4 5 6 7 ... A[i] 3 4 8 9 15 21 and Next = 7. The maximum is at position Next-1 = 6, and deleting it involves just decrementing Next by 1, to get i 1 2 3 4 5 6 7 ... A[i] 3 4 8 9 15 21 and Next = 6. (Since the list is between A[1] and A[Next - 1], 21 is no longer in the list). But what about insert? In order to maintain the array in sorted order, we need to insert any new element in the appropriate place. If the array contains k elements (and since the array is sorted A[1] ≤ A[2] ≤ ... A[k])) and x is the new element to be inserted. If j is the index with A[j] ≤ x ≤ A[j+1], then we have to move element A[Next-1] to A[Next], A[Next-2] to position A[Next-1] and so on till A[j+1] is moved to position A[j+2]. Finally we set A[j+1] to x. Thus each insert can take upto k operations. Thus the N inserts would take roughly N*N steps !! For instance, if the list was maintained in sorted order then prior to the insertion of 8 the list would have looked like: i 1 2 3 4 5 6 7 ... A[i] 3 4 9 15 21 and Next = 6. Inserting 8 would have required the shifting of the entries from position 3 to position 5 to the right by 1, then setting A[3] to 8 and incrementing Next to get: i 1 2 3 4 5 6 7 ... A[i] 3 4 8 9 15 21 and Next = 7. In summary, if we keep the elements in the order they arrive, we spend roughly 1 operation to insert but roughly N operations to find the maximum and delete it. On the other hand if we keep the elements in sorted order, then we spend roughly N operations to insert an element, but it takes just 1 operation to find the maximum and delete it. So either we do well on the inserts and rather badly in finding maximum and deleting it or we do well in finding the maximum and deleting it but do rather badly in insertion. Is there a middle ground? Here is a idea that is useful in many contexts. 1) Instead of maintaining a single list of length N, maintain sqrt(N) lists of length sqrt(N) each (so that the total number of elements that can be stored in all the lists put together is N). 2) Keep each of these sqrt(N) elements in sorted order. In order to insert an element, just look for a list which has less than sqrt(N) elements and insert it into it. The insertion itself will take at the most sqrt(N) steps. What about finding a list with space in it? Well, we keep track of the number of elements in each list. So will just have to look at each list once and this can take at most sqrt(N) steps. So in roughly sqrt(N) steps we can insert an element. What about find the maximum? Since all the lists are sorted we can pick the maximum element from each of them in 1 step each (Thus we will have sqrt(N) candidates for the overall maximum in sqrt(N) steps.) We now run through this sqrt(N) elements in sqrt(N) steps and find the maximum. Deleting it will just take 1 step as it involves deleting the maximum element from a sorted list! Thus, we will spend roughly sqrt(N) steps in finding the maximum and deleting it. Thus, if there are N insert operations and M max+delete operations , we can complete the entire sequence in roughly (N+M)*sqrt(N) steps. On the other hand, the first algorithm would take N*N + M steps while the second one would take N + M*N. In effect, by breaking up the list into sqrt(N) smaller lists, we have "averaged" out the two algorithms. How do we implement this algorithm? The answer is to use a 2-dimensional array of size sqrt(N) X sqrt(N). Each row stores a list. We also keep an array Next[] of size sqrt(N) to keep track of the "Next" for each of the sqrt(N) lists. --------------------------------------------------------------------- integer array A[sqrt(N)][sqrt(N)] integer array Next[sqrt(N)] for i=1 to sqrt(N) { Next[i] = 1 } for i=1 to M+N { x = read next input if (x = -1) print (Find-Max-Delete()) else Insert(x) } Insert(x) { Find the first i such that Next[i] ≤ sqrt(N). /* Find a list with space */ Find the first j such that A[i][j] ≥ x. /* Have to insert x at position j */ for (k=Next down to j+1) /* create space to insert x */ A[i][k]=A[i][k-1] A[i][j] = x /* insert x */ Next[i] = Next[i] + 1 } Find-Max-Delete() { max = -1 index = -1 for (i=1 to sqrt(N)) { /* examine each list if (Next[i] > 1) { /* if the list is nonemtpy if (max < A[i][Next[i]-1]) { /* see if it has the max so far. max = A[i][Next[i]-1] index = i } } } Next[index]=Next[index]-1 /* delete the maximum element return (A[index][Next]) } -------------------------------------------------------------------------- This algorithm would get 100% marks in the range of data prescribed for this problem. However, it turns out that one can be very clever and carry out the N inserts and M max-deletes in time proportional to (N+M)*log(N) (where log(N) is the logarithm of N to the base 2.) That is, one can insert as well as find the maximum element and delete it in time proportional to log(N) as opposed to sqrt(N). This is considerably better. For instance if N is 1000000, sqrt(N) is 1000 while Log(N) is 17. This involves maintaining the elements in the array as a "Heap". We postpone the discussion on heaps to another day.

Copyright (c) IARCS 2003-2020; Last Updated: 15 Mar 2005