Problem: Resource hog

[•Cosmin]

http://www.infoarena.ro/blog/resourcehog

[•szili]

Can quantity also be negative? Because in case it is positive we can just simply use a map (hash table) and update the max when a new update comes along.

[•dutzul]

nice task ! , here is my ideea:

keep (32) or (64)  maps , (ie: map< pair<string,int> > bin[32] , lets call this "bins"

now we map each integer X to the closest bin with index i , such that 2^i <=X
ex: 35 gets mapped to bin[5] because 2^5<=32 . so we do bin[5].push_back(X);

case 1: How we handle an update  , lets say we add 1 new user , now we need to binary search its matching "bin" , but the binary search is on values 0..32 so log(32)~loglog(X)~5-6 operations

case 2: when we update an already present user , we search its "bin" position using the above binary search, we remove it in O(1) since removal from a Map is O(1) using Hashes, then we re-insert it like in the case 1

 NOTE : each time we do an update , we keep for each "bin" a bit which is 0 if the bin is empty or 1 if the bin is occupied by atleast 1 user
 We can store all the values of the bits as a 32 bit integer (as we got a total of 32 bits)
 
 Lets call this integer Q;

case 3: we are facing an query :
 
 what we need to do is to find the bin with the greater index such that its NOT empty
 this relates to finding the least semnificant bit of integer Q  ; lsb(Q)  = (Q ^ (Q-1)) & Q
 so we know the biggest-index "bin" that is not empty , and we can just print any element from it .

 So the query part takes O(1)

 We will be off by a factor of at most 2 because of the way we are mapping the integers.

the complexity is O(log(log(32)))+O(1) ~ is preety close to O(1)

[•Cosmin]

@Szilard Yes it can. Good comment. I'll update the question.
@Dan Pretty good! That's the idea, but you can make that binary search step a bit more efficient. Also you meant log 32 not log log 32 right?

[•sorin_olimpicuu]

Suppose that we have this array of users' resources:
Array = [1, 5, 35, 40 ,100 ,80 ]
We map each number to the nearest power 2, we perform this operation

Cod:

 2^ log2(Nr) 

We apply the following function

Cod:

 MultiValueMap.put( 2 POW (log2 ( Array[i])) , Array[i] )

We will have 64 buckets for unsigned integer.
We perform the following operations
Map.put(1,1);
Map.put(4,5);
Map.put(32, 35);
Map.put(32, 40);
Map.put(64, 100);
Map.put(64, 80);

BucketList with a List
For bucket number 0 => [ 1 ]
For bucket number 1 => []
For bucket number 2 => [ 5 ]
For bucket number 3 => []
For bucket number 4 => []
For bucket number 5 => [35, 40]
For bucket number 6 => [100, 80]
For bucket number 7 => []
For bucket number 8 => []
For bucket number 9 => []
.............................

Operations :

• use_resources(name, quantity)  we just keep a hash between user and the object stored in the BucketList with a List
• get_approximate_max()  
  We have to find the first nonempty bucket and just perform a random on that set.
  In this case as we find that bucket number 6 is not empty we could take either the 80 or the 100.
  Because the maximum buckets' number is 64 or 32 I do not see the need for a binary search.
  

I have this idea because in the final round of Algoritmiada I saw a problem where I need to make a compression very fast but not a optimal compression and the solution was using power of 2.

[•retrograd]

@dutzul How about not using hashmaps at all (they are a heck of a complexity to estimate). Why not just use regular lists?

I.e. We keep a list of values for each of the "bins". The values will not be the real values, though. They will be indices. That will allow us for an easy update that could "lazily" delete the value from one of the bins (and, eventually, insert it in some other bin, if the value's MSB has changed). It is clear that the total elements of each bin can be stored this way (be aware, though, they do NOT equal the size of the actual lists, as we are doing deletions in a lazy manner). Now, when extracting a min / max, we look for the MSB / LSB of the mask we keep dynamically as you said, and we take its log. Then we eliminate all indices that should have been deleted and take the last element (think of the lists as "stacks"). All operations should be now O(log b), without the annoying "hashmap" constant. (b is the number of bits of the values), and total memory is O(M + b) (M is the total number of operations). Also, it can never exceed O(N * b), where N is the number of insertions, so that is also nice.

[•retrograd]

EDIT: Also, if the model we build it on allows us to extract the index of the MSB of some number in O(1), all operations become O(1). That is slick!

[•Cosmin]

Good job Lucian. That's the step I was waiting for!

C++ has

— Built-in Function: int __builtin_clz (unsigned int x)
Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined.

as a builtin function. Some processors also have it as a built in function so the algorithm now has O(1) time per query/update.