Basically, XXXX has its warehouses lined up in a circle, you can start from any warehouse move in either clockwise or anti-clockwise direction, the direction must remain the same throughout the remaining moves. Each warehouse stores some items. The goal is to collect excess items from some warehouses and deliver them to others need them, so that each warehouse stores the same number of items in the end (guaranteed).
The distance between 2 adjacent warehouses is 1, and the cost of each product transfer is the distance the product is moved. For example, say we have 6->6->6->3->4 (linked back to the first 6), we can optimally start from the first 6 and collect 1 item, repeat the same for the following 2 warehouses and deliver 2 to 3 and 1 to 4. In the end each warehouse has 5 items and the total cost is 1 + 2 + 3 + 1 = 7. This is just a possible clockwise move, the optimal cost should consider the anti-clockwise direction as well and return the minimum cost. I figured this was similar to LC 134 Gas Station but could not come up with a solution without using brute force.
Here is one of the comments containing sample code
The basic idea of the solution is similar to the gas station problem. We need to find a point where the balance is minimal and start moving from the point next to it. It looks like the total cost can be calculated in 1 pass. Then repeat for moving in the opposite direction and compare the results.
Imagine a chart showing the current balance. The shape of the chart does not depend on the choice of the starting point of the route. This choice only raises or lowers the chart relative to the Y axis. If we choose the starting point as I described earlier, the balance will never go below 0. At each point it will be increased by -minBalance. So we can just add -n*minBalance at the very end.
int getCost(const int n, const vector<int>& a, const int target) {
int cost = 0, balance = 0, minBalance = 0;
for (const auto x : a) {
balance += x - target;
minBalance = min(minBalance, balance);
cost += balance;
}
return cost - minBalance * n;
}
int solve(vector<int>& a) {
const int n = (int)a.size(), target = reduce(a.cbegin(), a.cend()) / n;
const int cw = getCost(n, a, target);
ranges::reverse(a);
const int ccw = getCost(n, a, target);
return min(cw, ccw);
}
int main() {
vector a {6,6,6,4,3};
cout << solve(a) << endl; // 7
}
There a few lines which I don’t understand
balance += x – target;
x - target means the diff at each point, to reach balance, why do we need to accumulate them?
minBalance = min(minBalance, balance); why do we need to find out he minBalance?
cost += balance; balance1 = point1, balance2 = point1 + point2, balanceN = point1 + ..pointN. Why is this “cost”?
cost - minBalance * n? What is minBalance*n? Why do we take it off from cost?
I did try to come up with my own solution, but it did not work.
const ans = (inarr) => {
let arr = [];
const sum = inarr.reduce((item, all) => {
return item + all;
}, 0) / inarr.length;
// * g: convert to new arr
for (let i = 0; i < inarr.length; ++i) {
const ele = inarr[i];
const diff = ele - sum;
arr.push(diff);
}
// * g: arr = [-2, -1, 1, 1, 1]
const scan = (local_arr) => {
let total = 0;
// * g: forward looking
for (let i = 0; i < local_arr.length; ++i) {
if (local_arr[i] === 0 || local_arr[i] < 0) {
continue;
}
// * g: it is positive now
// * g: 1. double the arr
// * g: 2. double the ind, but not arr
// * g: 3. the double arr ind has own range, but need mod to access origin arr
let j = i + 1;
while (j < i + inarr.length) {
const i_ind = j % inarr.length;
// * g: we don't want >= 0
if (local_arr[i_ind] > 0 || local_arr[i_ind] === 0) {
++j;
continue;
}
// * g: it is now negative; the i need to share some positive energy to it
// * g: 1. full balance
// * g: 2. partial balance
// * g: 3. how much to give out; how much to absort;
//
// * g: local_arr[i] -> local_arr[i_ind]
// * g: 1. |a| <= |b|; a give all; a become zero; b update; but a finish
// * g: 2. |a| > |b|; b absort all; b become zero; a update; but a still not finish
if (Math.abs(local_arr[i]) <= Math.abs(local_arr[i_ind])) {
total = total + Math.abs(i_ind - i);
local_arr[i_ind] = local_arr[i_ind] + local_arr[i];
local_arr[i] = 0;
break;
} else {
total = total + Math.abs(i_ind - i);
local_arr[i] = local_arr[i] + local_arr[i_ind];
local_arr[i_ind] = 0;
}
++j;
}
}
return total;
}
let min = Infinity;
for (let i = 0; i < inarr.length; ++i) {
// * g: backup
const arr1 = arr.slice(0);
const arr2 = arr.slice(0);
// * g: forward scan; arr destroy
const o1 = scan(arr1);
// * g: backward scan; arr1 destroy
const o2 = scan(arr2);
// * g: min
min = Math.min(min, o1, o2);
// * g: 1st ele to end
arr.push(arr.shift());
}
return min;
}
// const in_arr = [3, 4, 6, 6, 6];
const in_arr = [6, 6, 6, 3, 4];
const out = ans(in_arr);
console.log(out)
original: https://leetcode.com/discuss/interview-question/5834906/amazon-new-grad-oa/2648819
