Tối thiểu cặp giao nhau

Điểm: 1,00 (OI)

Giới hạn thời gian: 4.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Tại sao bò lại qua đường? Chúng ta có thể không bao giờ biết lý do đầy đủ, nhưng chắc chắn rằng những con bò của Farmer John thường xuyên qua đường. Trên thực tế, chúng qua đường thường xuyên đến mức thường xuyên va chạm nhau khi đường đi của chúng giao nhau — đây là tình huống Farmer John muốn khắc phục.

Farmer John nuôi $N$ giống bò ( $1 \leq N \leq 100 000$ ). Mỗi cánh đồng chỉ dành cho một giống bò nhất định. Một con đường dài chạy qua trang trại của anh. Có một dãy $N$ cánh đồng ở một bên đường (mỗi giống một cánh đồng) và một dãy $N$ cánh đồng ở bên kia đường (cũng mỗi giống một cánh đồng). Khi một con bò qua đường, nó đi từ cánh đồng của giống mình bên này sang cánh đồng của giống mình bên kia.

Nếu Farmer John đã sắp xếp cẩn thận hơn, anh sẽ đặt các cánh đồng theo cùng thứ tự giống nhau ở cả hai bên, để hai cánh đồng của mỗi giống nằm đối diện nhau qua đường. Điều này cho phép bò qua đường mà không có cặp giống nào giao nhau. Đáng tiếc là thứ tự ở hai bên đường có thể khác nhau.

Một cặp giống khác nhau $(a, b)$ được gọi là "giao nhau" nếu đường đi qua đường của giống $a$ và đường đi qua đường của giống $b$ bắt buộc phải cắt nhau.

Farmer John muốn tối thiểu hóa số cặp giống giao nhau. Vì lý do thực tế, anh có thể di chuyển bò ở một bên đường sao cho các cánh đồng bên đó trải qua một dịch chuyển vòng (cyclic shift). Cụ thể, với $0 \leq k < N$ , mỗi con bò chuyển đến cánh đồng cách nó $k$ vị trí về phía trước, với các con ở $k$ vị trí cuối chuyển về $k$ vị trí đầu. Ví dụ, dãy $3, 7, 1, 2, 5, 4, 6$ sau khi dịch chuyển $k = 2$ trở thành $4, 6, 3, 7, 1, 2, 5$ .

Hãy xác định số cặp giống giao nhau tối thiểu có thể đạt được sau một lần dịch chuyển vòng thích hợp ở một trong hai bên đường.

Dữ liệu vào

Dòng đầu tiên chứa $N$ .
$N$ dòng tiếp theo: thứ tự các giống bò (theo ID) ở bên thứ nhất của đường.
$N$ dòng tiếp theo: thứ tự các giống bò (theo ID) ở bên thứ hai của đường.

Dữ liệu ra

In ra số cặp giống giao nhau tối thiểu sau một lần dịch chuyển vòng ở một bên đường.

Ràng buộc

$1 \leq N \leq 100 000$
Mỗi ID giống bò là số nguyên trong khoảng $1 \dots N$ , mỗi giống xuất hiện đúng một lần ở mỗi bên.

Ví dụ

Input	Output	Giải thích
5 5 4 1 3 2 1 3 2 5 4	0	Bên trái: $[5, 4, 1, 3, 2]$ , bên phải: $[1, 3, 2, 5, 4]$ . Dịch chuyển bên phải $k = 3$ : bên phải thành $[5, 4, 1, 3, 2]$ . Hai dãy giống nhau → 0 cặp giao nhau.

Ghi chú

Cả hai bên đường đều có thể được dịch chuyển vòng. Chọn bên và giá trị $k$ sao cho số cặp giao nhau là nhỏ nhất.

Bình luận

Không có bình luận tại thời điểm này.