Loading Similar Posts

Entering edit mode

**Approach**

- This question is solved by using a greedy approach.
- This looks like the bubbling of the cheapest stone through the entire array.
- Find out the cheapest stone first, then start updating the array values from right to left.
- Once index 0 is reached move over to the n-1 th element and then again back to the cheapest one.
- We can precalculate the total cost occurred.
- This is a greedy approach where all stones will be changed to cheapest at a cost of x.
- To keep edge cases in check, calculate the cost before making any change so as to compare with the greedy cost.
- The optimal solution will always have the following form: You will change the types of the stones
`t`

times, at a total cost of`tx`

. And for each type, you buy the stone when it is cheapest. - Let's say
`t = 3`

, so you changed the types three times. - To get a stone of
`type 7`

, for example, you could have bought the 7th stone immediately, the 6th stone after one change, the 5th stone after two changes, or the 4th stone after three changes, so you obviously buy the cheapest of stones 4 to 7 when it has type 7. - Let
`prev (i, t)`

be the index of the stone that will have`type i after t changes`

. Obviously`prev (i, 0) = i, and prev (i, t+1) = prev (i, t) - 1 if prev (i, t) ≠ 1, and prev (i, t+1) = n if prev (i, t) = 1`

. - Let
`cost (i, t)`

be the minimum cost to buy a stone of type i if t changes are made. Obviously`cost (i, 0) = 𝑎𝑖`

, and`cost (i, t+1) = min (cost (i, t), 𝑎𝑝𝑟𝑒𝑣(𝑖,𝑡+1))`

. - Let
`cost (t)`

be the minimum cost to buy a stone of each type if`t`

changes are made. This is obviously`t*x + the sum of cost (i, t)`

over all i. You pick`t`

such that`cost (t)`

is minimal that we can choose greedely. - Time Complexity: O(N*N)

**Pseudo Code**

```
int n, x, ans = 0;
cin >> n >> x;
vector<int> a(n);
for (int i = 0; i < n; i++)
{
cin >> a[i];
ans += a[i];
}
for (int k = 1; k <= n; ++k)
{
vector<int> v, res;
for (int i = n - k + 1; i < n; i++)
v.push_back(a[i]);
for (int i = 0; i < n; i++)
v.push_back(a[i]);
deque<int> q;
forz(i, 0, k)
{
while (!q.empty() and v[q.back()] >= v[i])
q.pop_back();
q.push_back(i);
}
res.push_back(v[q.front()]);
int i = 0, j = k;
while (j < v.size())
{
while (!q.empty() and v[q.back()] >= v[j])
q.pop_back();
q.push_back(j);
j++;
if (q.front() == i)
q.pop_front();
i++;
res.push_back(v[q.front()]);
}
int sum = (k - 1) * x;
for (auto it : res)
sum += it;
ans = min(ans, sum);
}
cout << ans << "\n";
```

Entering edit mode

**Approach**

- This problem is solved by using a dynamic programming approach.
- Since at any stone, you could either take the stone without changing or take the (i-1)th stone by changing its type with the cost x.
- Find the cheapest stone, since that stone will not be changed by other stone. Thereby help us do in a single iteration starting from cheapest to full circle back.
- At any stone, we could make the following choices -
- Take the stone with its original cost, thereby does not change and propagate any previous stones.
- Or Take a previous stone of any step by incurring the cost of x for each step.

- We can memoize the current stone and the last stone that can be taken at the current step.
- Time Complexity: O(N*N)

**Pseudo Code**

```
int getMinCost(vector<int> &costs, int x, int n, int i, int j, int lasti, vector<vector<int>> &dp) {
if(j == n) // base condition of circular iteration
return 0;
if(i >= n)
i -= n; // to iterate in circle
if(dp[i][lasti] == -1) {
dp[i][lasti] = costs[i] + getMinCost(costs, x, n, i+1, j+1, i, dp); // use stone i without changing
dp[i][lasti] = min(dp[i][lasti], x + costs[lasti] + getMinCost(costs, x, n, i+1, j+1, lasti, dp)); // use stone lasti with changing cost x
}
return dp[i][lasti];
}
int main() {
int n,x;
cin>>n>>x;
vector<int> costs(n);
for(auto &a:costs)
cin>>a;
int mini=0;
for(int i=0;i<n;i++)
if(costs[i] < costs[mini])
mini = i;
vector<vector<int>> dp(n+1,vector<int>(n+1,-1));
int ans = getMinCost(costs, x, n, mini, 0, mini, dp);
cout<
```

Loading Similar Posts

Hi after submitting my solution, I am getting wrong answer for Test case 2. Can someone share the test case 2 or any test case where the solution could go wrong. Want to debug my code

Test case 2 : 123 5 3388 3558 161 4935 9923 799 8327 18 3126 5179 2667 5208 7318 3482 2436 5692 8194 6755 9625 8834 6332 6319 8294 6663 8698 9950 9970 7270 7829 6862 6540 3605 7220 6972 3204 4570 2233 9450 3810 180 5730 1275 2984 7663 6858 873 1463 1887 4723 3022 8480 9762 5344 7397 5509 2915 9813 9013 6381 2649 4513 7291 4405 2659 8784 1907 6278 6551 1617 2397 4386 8609 1626 3826 7199 4649 3615 9441 8007 7954 3232 1940 897 3985 3417 7515 6872 919 1484 5327 635 4690 9198 9894 757 8737 3524 1829 4132 251 1293 1591 5042 8651 3933 2062 6280 4918 8916 9743 9210 7821 3566 3974 7843 3007 4179 4206 8284 9886 4377 4045 2314

Your answer is greater than the expected solution i.e 2824