You are not logged in. Please login at to post your questions!


NOTINCOM - Editorial



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




Basic programming, sets


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.


Find the intersection of $A$ and $B$ and return its size.


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 1

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.

Subtask 2

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.


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

This question is marked "community wiki".

asked 23 Jan '17, 17:05

pkacprzak's gravatar image

5★pkacprzak ♦♦
accept rate: 12%

edited 29 Jan '17, 00:18

dpraveen's gravatar image

4★dpraveen ♦♦

The value of N and M mentioned in SubTask 2 is 10^5. But it should be 10^6. Please correct it.

@pkacprzak @dpraveen


answered 01 Apr '17, 12:56

horcrux2301's gravatar image

accept rate: 5%

edited 01 Apr '17, 12:57

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • 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:


question asked: 23 Jan '17, 17:05

question was seen: 1,824 times

last updated: 01 Apr '17, 12:57