Question: Apollo, Recently Asked On-Campus Questions in IIT-D, October, 2022
0
Entering edit mode

Question 1

Click here to Practice

Chocolates

Apollo1.1Apollo1.2

ADD COMMENTlink 17 days ago Rohit • 190 • updated 16 days ago QWERTY474 • 40
0
Entering edit mode

Question-1

Overview

  • Bob has N chocolates in his refrigerator to which he gives special value.
  • He performs some operations on the chocolates.
  • In each operation, he takes one or more chocolates that are lying in a continuous manner.
  • He then finds and notes down the minimum special value of chocolate in that group of chocolates.
  • He performs this operation for all groups of chocolates he could find.
  • The task is to find the sum of all the numbers he had written.

Solution

  • If we try to simplify the problem statement we would find that given an array of n integers, we have to find the sum of minimums over all the subarray of this array.
  • This can be done in O(n) using the famous stack trick.
  • For any index i we can find the left_bound and right_bound for it.
  • left_bound: Let l_index represent the left_bound for an index i. l_index for an index i can be defined as the index of the rightmost element+1 whose value is less than or equal to arr[i] having index less than i. If there is no such element, then left_bound for an index i will be equal to 0(0-based indexing).

  • To achieve this, we will insert only the index of the elements from left to right into the stack. Let us suppose, we are inserting an index i in the stack and j be the index of the topmost element currently present in the stack.

  • While the value arr[i] is less than the value at the topmost index in the stack and the stack is not empty, keep popping the elements in the stack. After the condition is dissatisfied, the left_bound for the current index is updated as the top index in the stack +1 or 0 if the stack is empty.

  • Similarly we can calculate the right_bounds for each index.

  • Now after we have left and right bounds for each index add the following to answer for each index:

`ans+= a[i]*((i-left_bound+1)*(right_bound-i+1));`
  • Now print the final answer.

Code

ll n;
cin >> n;
vector<ll> a(n);
for (ll i = 0; i < n; i++)
{
    cin >> a[i];
}
vector<ll> vminr(n, n - 1), vminl(n, 0);
stack<ll> st;
for (ll i = 0; i < n; i++)
{
    while (st.size() && a[st.top()] > a[i]) // while the topmost element is greater than current element keep popping it
    {
        st.pop();
    }
    if (st.size())
    {
        vminl[i] = st.top() + 1; // update the left_bound for the current index
    }
    st.push(i);
}
while (st.size())
{
    st.pop();
}
for (ll i = n - 1; i >= 0; i--)
{
    while (st.size() && a[st.top()] >= a[i]) // while the topmost element is greater than or equal to current element keep popping it
    {
        st.pop();
    }
    if (st.size())
    {
        vminr[i] = st.top() - 1; // update the right bound for the current index
    }
    st.push(i);
}
while (st.size())
{
    st.pop();
}
ll ans = 0;
for (ll i = 0; i < n; i++)
{
    ll lboundary = vminl[i];
    ll rboundary = vminr[i];
    ll tot = ((i - lboundary + 1) * (rboundary - i + 1));
    ans += (a[i] * tot); // Add element*total_subaarays_it_includes to the final answer
}
cout << ans << endl;
return;
ADD COMMENTlink 17 days ago Ujjwal Srivastava 160
0
Entering edit mode

ADD COMMENTlink 16 days ago QWERTY474 • 40
Entering edit mode
0

You can validate your code by submitting here: https://www.thejoboverflow.com/problem/243/

ADD REPLYlink 17 days ago
admin
1.1k

Login before adding your answer.

Similar Posts
Loading Similar Posts