Hello everybody. Recently, I was thinking about a one problem and now I want to share it with you:

You have two arrays of the same length n, and you have to calculate minimum number of swaps of two arbitrary indexes which transform the first array A into the second B. ( All elements in arrays are not neccessery distinct ) I know how to solve this problem when all elements are distinct in O(n). Do you know how to solve common problem in effective asymptotics?

Thank you in advance!

I'm extremely sorry for late publication.

Complexity: O(1).
Author of the idea: Vladik.
Worked on the problem: Vladik.

Complexity: O(n²).
Author of the idea: MikeMirzayanov.
Worked on the problem: fcspartakm.

Complexity: O(n³ * m).
Author of the idea: altruist.
Worked on the problem: Vladik.

Complexity: O(n).
Author of the idea: altruist.
Worked on the problem: altruist.

Complexity: O(n).
Author of the idea: MikeMirzayanov.
Worked on the problem: altruist.

Complexity: O(d * (N * M + K)), where d — alphabet power.
Author of the idea: Vladik.
Worked on the problem: Vladik.