altruist's blog

By altruist, history, 2 years ago, translation, In English,

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!

Read more »

 
 
 
 
  • Vote: I like it
  • +64
  • Vote: I do not like it

By altruist, history, 3 years ago, translation, In English,

I'm extremely sorry for late publication.

Tutorial is loading...

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

Tutorial is loading...

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

Tutorial is loading...

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

Tutorial is loading...

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

Tutorial is loading...

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

Tutorial is loading...

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

Read more »

 
 
 
 
  • Vote: I like it
  • +119
  • Vote: I do not like it