×

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

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

Setter's solution can be found here.
Tester's solution can be found here.

This question is marked "community wiki".

74485097
accept rate: 12%

2.5k53137170

 0 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 171●1●7 accept rate: 5%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,679
×1,652
×160
×81
×25
×7

question asked: 23 Jan '17, 17:05

question was seen: 1,824 times

last updated: 01 Apr '17, 12:57