We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Maybe we can give some details for tricky part: we don't know how many chocolates to give at the beginning to get the mininal path. For example let's take as initial problem "1 2 4" and compute the difference between the minimum colleague (=1) and the others so you start with "0 1 3" :
if you add +5 chocolates, you get "6 7 4" and the difference increases to "2 3 0" => not good!
now add +2 chocolates so you get "3 4 4" and the difference is decrease to "0 1 1" => much better!!!
adding +1 chocolates "2 3 4" and "0 1 2" => intermediate solution.
So the optimal first move is adding +2 chocolates for every colleagues excepted the last one.
Finaly the problem becomes: "reducing the difference between the number of colleague chocolates".
But if we start immediately to answer this new problem we will have an issue: how to deal with this example : "4 4 3"? In this case it is better to not start the reducing part because the initial state is not optimal. Let's transform it to "4 5 4" and then "5 5 5" and removing -5 chocolates is quicker than removing -2 chocolates with the initial state ("4 4 3"). Five operations < six operations!
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Equal
You are viewing a single comment's thread. Return to all comments →
Maybe we can give some details for tricky part: we don't know how many chocolates to give at the beginning to get the mininal path. For example let's take as initial problem "1 2 4" and compute the difference between the minimum colleague (=1) and the others so you start with "0 1 3" :
if you add +5 chocolates, you get "6 7 4" and the difference increases to "2 3 0" => not good!
now add +2 chocolates so you get "3 4 4" and the difference is decrease to "0 1 1" => much better!!!
adding +1 chocolates "2 3 4" and "0 1 2" => intermediate solution.
So the optimal first move is adding +2 chocolates for every colleagues excepted the last one.
Finaly the problem becomes: "reducing the difference between the number of colleague chocolates".
But if we start immediately to answer this new problem we will have an issue: how to deal with this example : "4 4 3"? In this case it is better to not start the reducing part because the initial state is not optimal. Let's transform it to "4 5 4" and then "5 5 5" and removing -5 chocolates is quicker than removing -2 chocolates with the initial state ("4 4 3"). Five operations < six operations!