COCI '14 Contest 2 #2 Utrka

Points: 5 (partial)

Time limit: 0.6s

Memory limit: 64M

Problem type

Numerous local and international recreational runners were eager to take part in this year's Zagreb Marathon! It is an already traditional race 42125 meters long. A curious statistical info is that this year every single contestant managed to complete the race, except one.

Since marathons are all about taking part, help the organizers figure out, based on the list of registered contestants and ranking list, the identity of the contestant that did not complete the race.

Input Specification

The first line of input contains the integer $N$ ~N~ $(1 \le N \le 10^5)$ ~(1 \le N \le 10^5)~, the number of contestants.
Each of the following $N$ ~N~ lines contains the names of registered contestants.
The additional $N - 1$ ~N - 1~ lines contain the names of contestants in the order which they completed the race.

The contestants' names will consist of at least one and at most twenty lowercase letters of the English alphabet.

The contestants' names won't necessarily be unique.

Output Specification

The first and only line of output must contain the name of the contestant who didn't finish the race.

Scoring

In test cases worth 50% of total points, it will hold $1 \le N \le 1\,000$ ~1 \le N \le 1\,000~.

Sample Input 1

3
leo
kiki
eden
eden
kiki

Sample Output 1

leo

Sample Input 2

5
marina
josipa
nikola
vinko
filipa
josipa
filipa
marina
nikola

Sample Output 2

vinko

Sample Input 3

4
mislav
stanko
mislav
ana
stanko
ana
mislav

Sample Output 3

mislav

Comments

-4

Plasmatic commented on July 15, 2017, 11:12 p.m.

tle

1

wleung_bvg commented on July 15, 2017, 11:23 p.m. ← edited →

Try using a HashSet or HashMap instead, since that supports constant time insertions and removals.