### Online Programming Contest, 4-5 December 2004

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) {

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 ... 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 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 ≤ A ≤ ... 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 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  {
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