Overtaking
InterviewTime limit2sMemory limit128 MB
Given entry and exit orders of N cars, count how many cars are not part of the longest common subsequence, meaning they overtook someone.
- Level
Easy3 of 10
- Topics
- Dynamic programming, Array, String
- Solved
- No attempts yet
Problem
In most countries, changing lanes inside a tunnel is prohibited by law. This is why lane markings inside tunnels are solid rather than dashed. Therefore, a car cannot change lanes and pass another car while it is inside the tunnel.
Two police officers, Daegeun and Yeongsik, watched one tunnel to find cars that overtook other cars inside it. Daegeun recorded the license plate numbers in the order the cars entered the tunnel, and Yeongsik recorded them in the order the cars left the tunnel.
After all N cars have passed through, comparing the two lists reveals how many cars must have overtaken at least one other car inside the tunnel. Write a program that computes that number.
Input
The input consists of 2N+1 lines.
The first line contains the number of cars N (1 <= N <= 1,000). The next N lines contain the license plate numbers recorded by Daegeun, in entrance order. The following N lines contain the license plate numbers recorded by Yeongsik, in exit order.
Each license plate number is a string of length between 6 and 8 inclusive, consisting only of uppercase English letters A through Z and digits 0 through 9. No license plate number appears more than once.
Output
Print the number of cars that must have overtaken at least one other car inside the tunnel.