PROBLEM LINK:Author: Sergey Kulik DIFFICULTY:CAKEWALK PREREQUISITES:Basic programming, sets PROBLEM:The problem can be reformulated as follows: for given two sets of integers $A$ and $B$, the goal is to find the minimum number of elements from $A$, such that after removing these elements from $A$, sets $A$ and $B$ do not have any common elements. QUICK EXPLANATION:Find the intersection of $A$ and $B$ and return its size. EXPLANATION:Since all numbers within $A$ are distinct and also all elements within $B$ are distinct, A and B are sets. What we want to do is to remove the minimum number of elements from $A$ in such a way that $A$ and $B$ do not have any common elements. In other words, it means that we want to make their intersection empty, which means that if $C$ is the intersection of $A$ and $B$, we have to remove all elements of $C$, and there is no need to remove any other elements. Thus the problem is reduced to finding the size of the intersection of $A$ and $B$. Depending on the subtask below methods are possible. Subtask 1In this subtask, we know that each $A$ and $B$ have at most $1000$ elements each and there are at most $25$ test cases to handle. This allows us to iterate over all elements of $A$, and for each one perform a full scan over elements of $B$ to check if the element belongs to both sets. For a single test case this method results in $O(A \cdot B)$ time complexity. Subtask 2In the second subtask, $A$ and $B$ can have up to $10^5$ elements, which makes the above approach too slow. However, one can use a hash map to count the number of occurrences of all elements from $A$ and $B$ together. It follows that each element belongs to intersection of $A$ and $B$ if and only if its count is equal to $2$. This approach has $O(A + B)$ time complexity per single test case. It is worth to mention that since all input elements are positive integers not greater than $10^6$, one can use a simple array instead of a hash map to compute the counters, which results in a similar time complexity and perhaps even easier implementation. AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 23 Jan '17, 17:05

The value of N and M mentioned in SubTask 2 is 10^5. But it should be 10^6. Please correct it. answered 01 Apr '17, 12:56
