Question: Hilabs SDE OA | Minimum Price
2
Entering edit mode

# Question

## Minimum Price

Minimum price
There are N stones lying in a line. The cost and type of the ith stone is a; units) and i respectively. You are
initially having zero stones and you wish to collect all the N types of stones, type 1, type 2, . .., type N.
You can perform the following operation multiple times (probably zero) to change the types of all the stones in one
step:
• The stone of the type i will be changed to the type i + 1. If i is N, then change its type to 1. (1 ≤ i ≤ N)
Applying this operation single time costs x units).
Your task is to print the minimum price that you have to pay to get all the N types of stones in your collection.
Input format

• First line: Two integers N, a
• Next line: N space-separated integers representing the price of each stone
Output format
• Next line: M space-separated integers representing the price of each stone
Output format
Print a single integer representing the minimum price to get all the N types of stones.

Input Constraints
1 < N < 2000
0<x<109

Sample input 1                             Sample output
3 5                                                         13
50 1 50

Copyfish

N/A
##### Translated(English)

N/A

Redo OCRRecaptureRe-TranslateCopy to clipboard

Please select text to grab.

ADD COMMENTlink 11 months ago automata_1 • 30
Entering edit mode
1

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

ADD REPLYlink 11 months ago
Atharva
• 10
Entering edit mode
1

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

ADD REPLYlink 11 months ago
Akshay Sharma
940
3
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 &gt;&gt; n &gt;&gt; x;
vector&lt;int&gt; a(n);
for (int i = 0; i &lt; n; i++)
{
cin &gt;&gt; a[i];
ans += a[i];
}
for (int k = 1; k &lt;= n; ++k)
{
vector&lt;int&gt; v, res;
for (int i = n - k + 1; i &lt; n; i++)
v.push_back(a[i]);
for (int i = 0; i &lt; n; i++)
v.push_back(a[i]);
deque&lt;int&gt; q;
forz(i, 0, k)
{
while (!q.empty() and v[q.back()] &gt;= v[i])
q.pop_back();
q.push_back(i);
}
res.push_back(v[q.front()]);
int i = 0, j = k;
while (j &lt; v.size())
{
while (!q.empty() and v[q.back()] &gt;= 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 &lt;&lt; ans &lt;&lt; "\n";
``````
ADD COMMENTlink 11 months ago Akshay Sharma 940
2
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&lt;int&gt; &amp;costs, int x, int n, int i, int j, int lasti, vector&lt;vector&lt;int&gt;&gt; &amp;dp) {
if(j == n)              // base condition of circular iteration
return 0;

if(i &gt;= 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&gt;&gt;n&gt;&gt;x;
vector&lt;int&gt; costs(n);
for(auto &amp;a:costs)
cin&gt;&gt;a;

int mini=0;
for(int i=0;i&lt;n;i++)
if(costs[i] &lt; costs[mini])
mini = i;

vector&lt;vector&lt;int&gt;&gt; dp(n+1,vector&lt;int&gt;(n+1,-1));
int ans = getMinCost(costs, x, n, mini, 0, mini, dp);
cout&lt;
``````
ADD COMMENTlink 11 months ago Tayal • 30
0
Entering edit mode
ADD COMMENTlink 6 weeks ago Ayush Agarwal • 0
0
Entering edit mode

// #include <bits/stdc++.h>

//   using namespace std;

//   int main() {

//     // cout << "Hello World";

//     int n , x ;

//     cin>>n;

//     cin>>x;

//     vector<int> prices;

//     int inputer = 0 ;

//     for(int i=0; i<n; i++){

//       cin>>inputer;

//       prices.push_back(inputer);

//     }

//     int ans = 0 ;

//     int itr = 0 ;

//     int temp_ans = 0 ;

//     cout<<"hello"<<endl;

//     for(itr = 0 ; itr<n; itr++){

//       int temp_itr = itr;

//       temp_ans = 99999 ;

//       int count = 0 ;

//       while(temp_itr!=itr+1){

//         temp_itr--;

//         if(temp_itr==itr){

//             break;

//         }

//         count++;

//         if(temp_itr==-1){

//           temp_itr=n-1;

//         }

//         temp_ans = min({temp_ans,prices[itr],prices[temp_itr]+(x*count)});

//         cout<<prices[temp_itr]+(x*count)<<" ";

//       }

//       cout<<endl;

//       ans+=temp_ans;

//     }

//     cout<<ans<<endl;

//     return 0;

//   }

#include <bits/stdc++.h>

#include <iostream>

using namespace std;

int main() {

int n, x;

cin >> n;

cin >> x;

vector<int> prices(n);

for (int i = 0; i < n; ++i) {

cin >> prices[i];

}

int totalCost = 0; // Initialize totalCost to a large value

for (int i = 0; i < n; ++i) {

int currentCost = prices[i];

for (int j = 0; j < n; ++j) {

// Calculate the cost to convert all stones to type j starting from type i

currentCost = min(currentCost,prices[(n+i - j) % n] + x * j) ;

// cout<<currentCost<<" ";

cout<<prices[(n+i - j) % n] + x * j<<" ";

}

// totalCost = min(totalCost, currentCost);

totalCost += currentCost ;

cout<<endl<<totalCost<<endl;

}

cout << totalCost << endl;

return 0;

}

cyclic iteration

ADD COMMENTlink 6 weeks ago Ayush Agarwal • 0

Login before adding your answer.

Similar Posts
Loading Similar Posts