COCI '07 Contest 5 #4 Avogadro

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 0.6s
Memory limit: 32M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Luka is slacking again during chemistry class, while the teacher is explaining Avogadro's law.

Luka first drew a table consisting of 3 rows and N columns. Then he wrote the numbers 1 to N into the first row in arbitrary order, each number appearing exactly once. In the other two rows he also wrote integers between 1 and N, but didn't care how many times a number appeared.

Luka can now delete any set of columns from the table. After doing so, he sorts the numbers in each row in ascending order.

He wants to obtain a table in which all three rows are identical after sorting. Write a program that determines the smallest number of columns he must delete.

Input Specification

The first line of input contains the integer N (1 \le N \le 100\,000), the number of columns in the table. The following three lines contain N integers each, separated by single spaces. The numbers will be between 1 and N, and there will be no duplicates in the first row.

Output Specification

Output the smallest number of columns Luka must delete.


In test cases worth 40\% of points, N will be less than 100.

In test cases worth 70\% of points, N will be less than 10\,000.

Sample Input 1

5 4 3 2 1 6 7
5 5 1 1 3 4 7
3 7 1 4 5 6 2

Sample Output 1


Sample Input 2

1 3 5 9 8 6 2 4 7
2 1 5 6 4 9 3 4 7
3 5 1 9 8 6 2 8 7

Sample Output 2


In the first example, Luka needs to delete the second, fourth, sixth and seventh columns. After deleting the columns and sorting each row, all three rows contain the numbers 1, 3 and 5.


There are no comments at the moment.