Check Reachability in a Moving Sequence Problem

Given heights of n rectangles and two positive integers x and y. You start moving from the rectangle at 0th index. In one move you can perform one of the following operations:

If h[ i-1 ] <= h[ i ], move from i-1 to i rectangle
If h[ i-1 ] > h[ i ], move from i-1 to i rectangle and reduce x to x-1 , if x>0
If h[ i-1 ] > h[ i ], move from i-1 to i and reduce y to y = y- ( h[i-1] -h[i]) ,if y>=h[i-1]-h[i]

Find if its possible to reach index z by any combination of above operations or not. If you can perform none of the above operations you should stop.

Examples:

Input:
n = 8
h[n] = [10,2,8,6,9,14,12,29]
x = 1
y = 5
z = 7
Output: YES
 
Input:
n = 9
h[n] =  [4,12,2,7,3,18,20,5,25]
x = 2
y = 10
z = 8
Output: YES

Approach:

Lets greedily try and reach the maximum possible index . If the given index z is less than or equal to max possible index then we can reach z otherwise we can not. Steps involved in finding the max possible index are as follows:-

We start iterating from i =1.
When h[i] >= h[i-1] we move to next rectangle
When h[i] < h[i-1] we have to choose between the second and third operation.
It’s optimal to use x for largest h[i-1]-h[i] difference.
We iterate , maintaining the largest x height differences (h[i-1]-h[i]) and the sum of the remaining ones so far, and stop whenever this sum exceeds y .We use min priority queue here to keep a track of differences between the heights . We keep the x largest differences in the queue and remaining differences in a variable s. When the value of s becomes more than y we can not move any further.

Implementation of above approach:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n = 8;
    int heights[n] = { 10, 2, 7, 5, 9, 14, 12, 29 };
    int x = 1;
    int y = 5;
    int z = 7;
    priority_queue<int, vector<int>, greater<int> > p;
    int s = 0;
    int ans = 0;
    for (int i = 1; i < n; i++) {
        int d = heights[i - 1] - heights[i];
        if (d <= 0) {
            continue;
        }
        else {
            p.push(d);
            if (p.size() > x) {
                int temp = p.top();
                s = s + temp;
                p.pop();
                if (y < s) {
                    ans = i - 1;
                    break;
                }
            }
        }
    }
    if (ans <= z)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
    return 0;
}

Output :

YES

Time Complexity : O(nlogn)

Please write comments below if you find anything incorrect, or you want to share more information about the topic discussed above. A gentle request to share this topic on your social media profile.