UVa 11849: CD is an easy problem, as long as you use a set. Using a vector or array will not work. If you try to use a vector to store whether or not Jack owns each cd, you will use up too much memory, since there are 1 billion possible cds. If you try to keep a sorted vector of the cds Jack owns, you will get TL because the input size (1 million) is too large for an O(nlogn) operation. A set solves both of these problems, because it only stores the elements it needs to and does insertions and lookups in O(logn). Once we know to use a set, we can solve the problem this way: Keep all of the cds Jack owns in a set. For each cd that Jill owns, check to see if it is in the set. If so, increment the number of cds that both Jack and Jill own by 1.
UVa 11849: CD
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.