0 like 0 dislike
1,119 views
| 1,119 views

0 like 0 dislike

Can anyone share the approach for solving this Problem?
Please share Any Other Similer Problem you have ever solved so that I practice.

by Expert (109,220 points)
0 like 0 dislike
``````/**
* @brief for ith index prefixCost gives the cost of setting the stick length to ith length from (1st to ith) element
* @param curr_single_length is the total cost to increase or decrease all the 1 st to i-1th length to 1 unit
*/

void findPrefixCost(vector<int> &prefixCost, vector<pair<int, int>> &sticks)
{
int n = prefixCost.size();
prefixCost[0] = 0;
int curr_single_length = sticks[0].second;
for (int i = 1; i < n; i++)
{
int diff = sticks[i].first - sticks[i - 1].first;
prefixCost[i] = prefixCost[i - 1] + diff * curr_single_length;
curr_single_length += sticks[i].second;
}
}

/**
* @brief for ith index suffixCost gives the cost of setting the stick length to ith length from (ist to end) element
* @param curr_single_length is the total cost to increase or decrease all the i+1 th to end length to 1 unit
*/

void findSuffixCost(vector<int> &suffixCost, vector<pair<int, int>> &sticks)
{
int n = suffixCost.size();
suffixCost[n - 1] = 0;
int curr_single_length = sticks[n - 1].second;
for (int i = n - 2; i >= 0; i--)
{
int diff = sticks[i + 1].first - sticks[i].first;
suffixCost[i] = suffixCost[i + 1] + diff * curr_single_length;
curr_single_length += sticks[i].second;
}
}

int magicSticks(int n, vector<int> &len, vector<int> &cost)
{
vector<pair<int, int>> sticks;
for (int i = 0; i < n; i++)
{
sticks.push_back({len[i], cost[i]});
}
sort(sticks.begin(), sticks.end());
vector<int> prefixCost(n), suffixCost(n);
findPrefixCost(prefixCost, sticks);
findSuffixCost(suffixCost, sticks);
int ans = 1e9;
for (int i = 0; i < n; i++)
{
ans = min(ans, prefixCost[i] + suffixCost[i]);
}
return ans;
}
``````
by Expert (680 points)
0 like 0 dislike

For this type of questions, i.e. minimal cost to equalize a list of numbers, the key is to note that

the minmum cost is always achieved when the equal length = one number from the list

e.g. if sticks' heights are [1,4,7], the equal length with minimum cost must be one from 1,4,7, rather than those from 0,5,6,8. etc. Try to prove it by contradiction.

With this obseration, sort stick heights, for every possible height, calculate the total cost to equalize all sticks in O(n), and then pick the smallest cost.

def magic(n,sticks,cost):
#costs=[0]*n #cost[i] is the cost to make all sticks equal to stick[i] length

``````prices=set()

for i in range(len(sticks)):
req=sticks[i]

tot=0

for j in range(len(sticks[:i])):
k=sticks[j]

while(k<req):
k+=1
tot+=cost[j]

while(k>req):
k-=1
tot+=cost[j]

for j in range(i+1,len(sticks)):
k=sticks[j]

while(k<req):
k+=1
tot+=cost[j]

while(k>req):
k-=1
tot+=cost[j]