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
I will be happy if you show me where is the bad point of my blog instead of getting bad rating
haters all the way
bad truth! :(
Can you say where you've found this problem?
in http://ace.delos.com/ioigate SOI March 2012 Third IOI-Selection Round
but the problem statment in arabic
please help!
I've been trying to solve this problem for months
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