11 weeks ago

Rohit • 610

Hyderabad

Question 1

Chocolates

Rob likes chocolates. He finds N chocolates in his refrigerator to which he gives a special value. He is also a mathematics lover, so he decides to do something peculiar with the chocolates. 

He performs some operations on the chocolates. In each operation, he takes one or more chocolates which are lying in a continuous manner. He then finds and notes down the special value of a chocolate in that group of chocolates. He performs this operation for all the group of chocolates he could find. But unfortunately his pet dog ate the paper on which he had written the results. Your task is to find the sum of all the numbers he had written. 

Input Specification: 

Input1: The number of chocolates N.

Input2: The array representing the special values of chocolates. 

Output Specification:   

The desired sum. 

Example 1:

Input1: 2

Input2: (3,4)

Output: 10

Explanation: Here, the groups he can form by using one or more continuous. 

4 months ago

Ujjwal Srivastava 320

Bengaluru

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;