Editorial -CU4STORE

1

PROBLEM LINK:

Practice
Contest

Author: [Riddham]

Editorialist: [Riddham]

DIFFICULTY:

EASY

PREREQUISITES:

BruteForce, Optimisation

PROBLEM:

There are n rooms in a building which is the storage for food grains which has a weight xi.So your job is the find for each room the
nearest room to its left having a smaller weight i.e xi<xj where i<j given weight of grains in each room.

EXPLANATION:

For each room, we must find the closest room to its left that has a lower capacity than it. If we iterate from left to right, we can use
previous solutions to speed up the process.By brute force, in O(n²) we can check for all rooms to the left of the current room and find the
nearest suitable room. Intuitively, if we iterate from the current room towards the first room instead of starting from the first room each time,
we will save time.The previous solutions can now be brought into the picture to optimize this a bit further. An extra array is needed for this,
hich has been named n1 in the solution below, trading off time complexity for memory complexity.

SOLUTIONS:

Code passing all subtasks 
#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define ar array

const int mxN=2e5;
int n,a[mxN], n1[mxN];

int main(){
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        n1[i]=i-1;
        while(~n1[i]&&a[n1[i]]>=a[i])
        n1[i]=n1[n1[i]];
        cout<< n1[i]+1 <<" ";
    }
}

We hope you enjoyed the problems and if you have any questions, do ask us right away on this thread.

1 Like