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

Question

Minimum Price

Click here to Practice

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

Qenter image description here

 

 

x

Copyfish

 
 
 
 
 
 
 
 
 
 
 
 
 

 

OCR Result(Auto-Detect)
N/A
Translated(English)

N/A

 
Redo OCRRecaptureRe-TranslateCopy to clipboard
 
 

Please select text to grab.

 
 
 
 
ADD COMMENTlink 19 months ago automata_1 • 40
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 19 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 19 months ago
Akshay Sharma
960
Entering edit mode
0

can u share the 5th test case I'm getting correct for the other 4 test cases

ADD REPLYlink 7 months ago
Viswanath
• 10
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 19 months ago Akshay Sharma 960
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 19 months ago Tayal • 30
1
Entering edit mode

Just simple brute force works:

1. Make the size of the array to 2*n by appending it to itself to avoid any circular array headache.

2. Find the minimum value for each l to r and store in 2D array.

3. Find the minimum cost for each i (0<=i<=n-1) where i is the maximum number of rotations we will do.

4. To find the minimum cost for any i : For each type of stone we will choose stone minimum cost from currIdx to currIdx+i (can be done in O(1) using the step 2 array).

 

Here is code: 

#include<bits/stdc++.h>

using namespace std;
 
#define input(arr) for(ll i=0; i<n; i++){cin>>arr[i];}
#define ll long long

int main() {
    DRAMA;

    ll n,x;
    cin>>n>>x;

    vector<ll> v(n);
    input(v);

    for(ll i=0;i<n;i++)v.push_back(v[i]);

    ll ans=LLONG_MAX;

    vector<vector<ll>> minimum(2*n,vector<ll> (2*n));

    for(int i=0;i<2*n;i++){
        ll mini=LLONG_MAX;

        for(int j=i;j<2*n;j++){
            mini=min(mini,v[j]);
            minimum[i][j]=mini;
        }
    }

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

        ll curr=i*x;

        for(int j=0;j<n;j++)
            curr+=minimum[j][j+i];

        ans=min(ans,curr);
    }

    cout<<ans<<endl;
}

 

 

ADD COMMENTlink 4 months ago Ashutosh Saini • 10
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 10 months ago Ayush Agarwal • 10
0
Entering edit mode
#includeusing namespace std; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n,k; cin>>n>>k; vectorarr(n); int ans=0; for(int i=0;i>arr[i]; ans+=arr[i]; } vectormini = arr; for(int iteration=1;iteration
ADD COMMENTlink 7 months ago Anurag Ravi • 0
0
Entering edit mode
#includeusing namespace std; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n,k; cin>>n>>k; vectorarr(n); int ans=0; for(int i=0;i>arr[i]; ans+=arr[i]; } vectormini = arr; for(int iteration=1;iteration
ADD COMMENTlink 7 months ago Anurag Ravi • 0

Login before adding your answer.

Similar Posts
Loading Similar Posts