2.1 years ago

automata_1 • 40

Question

Minimum Price

Minimum price
There are N stones lying in a line. The cost and type of the i^th 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

8 months ago

Akshay Sharma 990

Chandigarh

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";

2.0 years ago

Tayal • 40

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<

6 months ago

Ashutosh Saini • 30

Delhi

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;
}

13 months ago

Ayush Agarwal • 20

Mumbai

Ula | OA | Minimum Price (Need Solution) - LeetCode Discuss

Sharechat | OA | HackerEarth | SDE-1 | Minimum Price - LeetCode Discuss

Interview Question - LeetCode Discuss

13 months ago

Ayush Agarwal • 20

Mumbai

// #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