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

×

NOTINCOM - Editorial

PROBLEM LINK:

Practice
Contest

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

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

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

asked 23 Jan '17, 17:05

pkacprzak's gravatar image

5★pkacprzak ♦♦
74485097
accept rate: 12%

edited 29 Jan '17, 00:18

dpraveen's gravatar image

4★dpraveen ♦♦
2.5k53137170


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

@pkacprzak @dpraveen

link

answered 01 Apr '17, 12:56

horcrux2301's gravatar image

4★horcrux2301
17117
accept rate: 5%

edited 01 Apr '17, 12:57

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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:

×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