↵
↵
↵
↵
Algorithm to solve this problem — If all weights were distinct solution is pretty simple — find 'r' the last and only occurrence of smallest number in the weight array — now travel efficiently through the second smallest number and push it to smallest position > r -> now do the same algorithm for the third number — this time 'r' will be the last and only occurrence of the second smallest number ↵
↵
Problem — This algorithm does not work if there are duplicate numbers in the weight array ↵
↵
-> [2 1 1 1 1 2 3 3 3 3 2] ↵
↵
-> [5 1 1 1 1 2 1 1 1 1 100]↵
↵
It will take 3 moves on w[0] so it gets to a free position on the co-ordinate axis. ↵
↵
But if you make single move on w[5] towards the right — then w[0] can take place of w[5] in just total two moves. ↵
↵
So how to deal with which strategy to apply for duplicated numbers ? ↵
↵
I think it is impossible to solve this problem for duplicate numbers as it is NP-hard problem as per this blog — https://mirror.codeforces.com/blog/entry/103255
↵
↵
↵
Algorithm to solve this problem — If all weights were distinct solution is pretty simple — find 'r' the last and only occurrence of smallest number in the weight array — now travel efficiently through the second smallest number and push it to smallest position > r -> now do the same algorithm for the third number — this time 'r' will be the last and only occurrence of the second smallest number ↵
↵
Problem — This algorithm does not work if there are duplicate numbers in the weight array ↵
↵
-> [2 1 1 1 1 2 3 3 3 3 2] ↵
↵
-> [5 1 1 1 1 2 1 1 1 1 100]↵
↵
It will take 3 moves on w[0] so it gets to a free position on the co-ordinate axis. ↵
↵
But if you make single move on w[5] towards the right — then w[0] can take place of w[5] in just total two moves. ↵
↵
So how to deal with which strategy to apply for duplicated numbers ? ↵
↵
I think it is impossible to solve this problem for duplicate numbers as it is NP-hard problem as per this blog — https://mirror.codeforces.com/blog/entry/103255
