Hard Amazon OA Problem | Which greedy strategy is correct ? 
Разница между en1 и en2, 164 символ(ов) изменены
![ ](/predownloaded/f4/ec/f4ece3835c8edb2fbb4063f519f9974da020c91d.jpg)↵

![ ](/predownloaded/56/08/56082c5d6f786c9cb2aec12653ed279ca00c4304.jpg)↵

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://codeforces.net/blog/entry/103255

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский LovesProgramming 2024-11-11 13:05:03 53 Tiny change: '![ ](/pred' -> 'This problem was asked in Amazon OA few days back\n\n![ ](/pred'
en2 Английский LovesProgramming 2024-11-11 11:08:00 164
en1 Английский LovesProgramming 2024-11-11 08:13:15 1080 Initial revision (published)