STONE - Editorial

editorial
, , ,
1

PROBLEM LINK:

Contest

Setter: Reet Roy
Tester: Rashed Mehdi
Editorialist: Saranya Naha Roy

DIFFICULTY:

EASY

PREREQUISITES:

Stack

PROBLEM:

There is an input array of size N. We need to produce an output array of size N such that:
output_i= maximum number of consecutive values up till input_i for which each of the consecutive values is less than or equal to input_i. Finally, we need to find the sum of the output array and compare it to Q.

QUICK EXPLANATION:

The idea is to use a stack. The stack is used to maintain a subsequence of the values that have been processed so far and output for those values can be used to calculate the output for later values that have not been processed yet.

EXPLANATION:

Initialize the output array to all 1s as output for each number of the input array will be at least 1. Now to find the output of a number we will use outputs of already visited numbers. Example:

input : [4, 5, 2, 3, 4, 10]

output : [1, 2, 1, 2, 3, \_]

Suppose we need to calculate the output for number 10 and the outputs for previous numbers are already calculated. At first, we initialize the output of 10 as 1. Now we see 4<10 and output for number 4 is 3. That means there are two more consecutive numbers with 4 which are <= 4. These 3 consecutive numbers are also <10 and we can add 3 to the output of 10.

So\ now\ the\ output\ of\ 10\ is\ 4 (4 \ consecutive\ numbers\ with\ 10<=10).

At this point, we can skip 3 numbers on the left of 10 as we know they are <=10 and the count of them has already been added. So we reach 5. As 5<10 we add output of 5 to the output of 10. Now the output of 10 is 4+2=6. Again we skip 5 numbers on left and there is no more element to check. So to calculate the output of 10 we only need to visit 4(input_4) and 5(input_1) instead of visiting all the elements on the left of 10.

This idea can be implemented using a stack. Create an empty stack. This stack stores indexes of elements we have visited and are required to calculate the output of elements that are not visited yet.

Let us assume the input array is input[], the output array is output[], and the size of the input and output array is N.

1) Initialize the output array to all 1s.

2) Create a new empty stack S

3) For every element input[i] in the input array input[],
   where i goes from 0 to n-1.
    a) while S is nonempty and the item indexed in input array by the top of 
       S is less than or equal to arr[i]:
           i) let TOP = top element of S
	       ii) output[i]+=output[TOP]
           iii) S.pop() // as we have already added the output of TOP to the output of i, TOP is no longer required to calculate the output of rest of the unvisited elements. So we remove TOP from the stack.  
    
    b) if S is empty:
           // input[i] has no preceding values to check.
    c) else:
           let TOP = top element of S.
	       // Here input[TOP] > input[i]. So we can not go farther to the left.

    d) push i onto S.

4) Finally we can calculate the sum of the output array and compare it to Q.

Time complexity of above solution is O(n) as index of every element is pushed and popped at most once to the stack. So overall constant number of operations are performed per element.

SOLUTIONS:

Setter's Solution 
#include <iostream>
#include <stack>
#include <fstream>
#include <cstdlib>
using namespace std;
void calculateSpan(int price[], int n, int S[])
{
    stack<int> st;
    st.push(0);
    S[0] = 1;
    for (int i = 1; i < n; i++)
    {
        while (!st.empty() && price[st.top()] <= price[i])
            st.pop();
        S[i] = (st.empty()) ? (i + 1) : (i - st.top());
        st.push(i);
    }
}
int main()
{
    int q, n;
    cin >> n >> q;
    int *S = (int *)malloc(n * sizeof(int));
    int *K = (int *)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++)
        cin >> S[i];
    calculateSpan(S, n, K);
    long long int sum = 0;
    for (int i = 0; i < n; i++)
    {
        cout << K[i] << " ";
        sum += K[i];
    }
    cout << "\n";
    if (sum >= q)
        cout << "YES";
    else
        cout << "NO";
    return 0;
}
Tester's Solution 
n,qq = map(int,input().split())
arr = list(map(int,input().split()))
st = []
top = res = 0
for i in range(n):
   ct = 0
   while top!=0 and arr[st[top-1]] <= arr[i]:
       st.pop()
       top-=1
   if top == 0:
       ct=i+1
   else:
       ct=(i-st[top-1])
   st.append(i)
   top+=1
   res+=ct
   print(ct,end=" ")
print()
if res >= qq:
   print("YES")
else:
   print("NO")
1 Like