zplesivcak's blog

Efficiently count minimal number of swap operations to sort an array
By zplesivcak, 10 years ago, In English

I don't know how to approach this question. Can someone please help me? Thank you.

Problem statement:

Given an array A[1...N] of positive integers, you have to sort it in ascending order in the following manner : In every operation, select any 2 non-overlapping sub-arrays of equal length and swap them. i.e, select two sub-arrays A[i...(i+k-1)] and A[j...(j+k-1)] such that i+k-1 < j and swap A[i] with A[j], A[i+1] with A[j+1] ... and A[i+k-1] with A[j+k-1].

Example:

For n = 6 and array ( 6 7 8 1 2 3 ), only one operation is needed as after swapping ( 6 7 8 ) and ( 1 2 3 ) sub-arrays we can get ( 1 2 3 6 7 8 ), that is sorted array.

Source: Careercup

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

This problem was given in the recent HackerEarth contest as a "challenge" problem. I suggest you reading submissions and try to understand them (you must be logged in on HackerEarth). Personally, I do not know how to solve it efficiently.

→ Reply