DMOPC '14 Contest 8 P3 - Globally Unique Shells

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type

Stranded on an island, Tusk decided to kill time by collecting shells. But he doesn't want just any broken shell: he's interested in bivalves — that is, shells with both the right and left halves (valves) intact.

A bivalve.

In fact, he spent so much time searching that he's collected N such mollusks.

Tusk has a programming hobby, so he killed some more time by assigning each mollusk a GUID (strangely, these "GUIDs" are integers from 1 \dots 999\,999, but they still satisfy the property that they're pairwise distinct). Each mollusk has both its left and right halves labeled with the same GUID.

A labeled bivalve.

However, in an unfortunate turn of events, he accidentally smashed into the shells with a giant aircraft. In doing so, all N of the bivalves have broken apart into their respective valves. On top of this, a number of valves were either crushed or lost.

Tusk has collected and repaired all the shells he can. How many were crushed or lost?

Input Specification

The first line of input will contain the single integer N (1 \le N \le 60\,000), the original number of mollusks.
The second line of input will contain two space-separated integers A and B (1 \le A, B \le N). A represents the number of shell right halves, while B represents the number of left halves. It is guaranteed that the valves left are valid.
The next line will contain A space-separated integers, the list of right-half shell GUIDs.
The last line of input will contain B space-separated integers, the list of left-half shell GUIDs.

Output Specification

The number of shells that were either partially or fully lost.

Sample Input

4 3
1 2 8 4
1 8 5

Sample Output



The only shells that survived were 1 and 8. Part of 2, 4 and 5 were recovered, but they're incomplete. Aside from these, 5 of the original 10 shells are fully unaccounted for. Therefore, 8 shells were destroyed.


There are no comments at the moment.