kingofnumbers's blog

how to solve this problem
By kingofnumbers, 12 years ago, In English

I need help with this problem ,because I have no idea how to solve this

problem statement:


You have an array with N elements (1<=N<=1000),
you need to sort this array in non-increasing order,
you can only move the element in position i to position j:
1- by swaping i and i+1 then swaping i+1 and i+2 ... swaping j-1 and j (if i<j)
2- by swaping i and i-1 then swaping i-1 and i-2 ... swaping j+1 and j (if i>j)

in both operations the cost of the operation is i+j

find the minimal cost that you can sort the array non-increasing order

input:
first line contains integer N
second line contains N space-separated integers the elements of the array

output:
one integer the minimal cost

Sample test:
input:
5 
20 30 5 15 10 

output:
11

Note:
in the sample test moving element in position 3 to 5 will cost (3+5)=8
moving the element in position 2 to 1 will cost (2+1)=3

total cost 3+8=11
  • Vote: I like it
  • -16
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I will be happy if you show me where is the bad point of my blog instead of getting bad rating

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you say where you've found this problem?

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

please help!

I've been trying to solve this problem for months

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved problem LSORT before , so I believe similar logic can be applied to solve the one you mention , but actually I'm not quite sure , so please forgive me if the following is nonsense :) . The constraint on N suggests that an O(N^2) solution should be developed. let dp[i][j] be the requierd cost to sort the interval [i..j] of the array in non-decreasing order (1 <= i <= j <= N). The final answer would be dp[1][N] Obviously , dp[i][i] = 0 for all 1 <= i <= N. The DP recurrence will be : dp[i][j] = min{dp[i][j — 1] + f(x[j]) , dp[i + 1][j] + f(x[i])}. where f(n) is the cost required to insert element n into its proper place . To calculate ( say ) f(x[j]) , you need to know the number of elements in interval [i..j — 1] which are smaller (or bigger) than x[j] . This can efficiently done by FenwickTree in O(log N) time , hence the total time complexity is O(N^2 log N).

P.S. : the notation dp[i][j] above is just for clarity. In practice , this would be written as dp[L][S] , which can be read as : the cost to solve an interval of length L starting at S , where L= j — i + 1 , and S = i

→ Reply