UVa 11136: Hoax or what is a simulation problem using multisets.
Conceivably this problem could also be solved with vectors or arrays, however since the contents of the data structure is so dynamic, a multiset is faster. This is because multiset inserts and deletes can be done in O(logn), and a multiset is automatically kept in sorted order, so accessing the elements we care about is O(1). I made two implementation mistakes when writing this solution. First, note that the problem statement says that no bill is greater than 10^6. I thought this meant I was ok to use int
s everywhere, but I was wrong! Since the promotion can be at most 5000 days, the largest possible value of the promotion is 5000 * 10^6 = 5 * 10^9, which is bigger than the size of an int. I also absent-mindedly put the line of code that removed items from the multiset before the line that added them to the total, which was not correct.
UVa 11136: Hoax or what
For technical reasons, comments are temporarily unavailable on my posts. If you'd like to discuss this article with me, feel free to email me at or hit me up on Twitter.