# NOTINCOM - Editorial

Author: Sergey Kulik
Tester: Kamil Debowski
Editorialist: Pawel Kacprzak

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.

In 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.