WA in Richies Mountain (REC09C)

I was solving the Richies Mountain (REC09C Problem - CodeChef) problem, though it has the dynamic programming tag, I just thought if we could solve it without using dynamic programming. What I observed was that for a YES the desired trends in the range were:- numbers are strictly increasing, or the numbers are strictly decreasing or the numbers first increase and then decrease (only once). And the only trend that gives a NO is that the numbers first decrease and then increase (even if it happens only once). Keeping these trends in mind I came up with the following solution which works correctly on the sample input but gives WA on submission:-

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin >> n;
    int h[n];
    for(int i=0; i<n; i++)
        cin >> h[i];
    int m;
    cin >> m;
    int l, r;
    for(int i=0; i<m; i++)
    {
        cin >> l >> r;
        if(l == r || n==1)
            cout << "YES\n";
        else
        {
            l -= 1;
            r -= 1;
            int trend = -1;
            int flag = 0;
            for(int j=l+1; j<=r; j++)
            {
                if(h[j] > h[j-1])
                {
                    if(trend == 0)
                    {
                        flag = 1;
                        cout << "NO\n";
                        break;
                    }
                    else
                        trend = 1;
                }
                else
                    trend = 0;
            }
            if(flag == 0)
                cout << "YES\n";
        }
    }
    return 0;
} 

In the above code, an increase is denoted by 1 and a decrease is denoted by 0. The moment we find 0 followed by 1, we break the loop and output NO, but if the value of the flag is unchanged we output YES, meaning we didn’t find decrease followed by an increase. What is wrong with the solution? Please help.

@everule1 Please Help.

This looks like O(n^2) which will TLE

But it gives WA.

Try:

5
1 2 2 2 1
1
1 3

Output comes out to be YES

That’s wrong. It cannot be equal as stated in the question

Now I am getting a TLE

How is my solution O(n^2)? I am just going through the numbers only once.

O(nm) same thing

Can you please provide a link to a well commented solution that uses dynamic programming?

Give me 10 minutes.

@everule1 ?

@everule1 Please help, how should I proceed with dynamic programming in this problem?

Just check whether there is no element in range l+1 to r-1 inclusive such that it is lesser than it’s predecessor and successor, and no two elements are equal. For some reason I find stuff like this difficult. use prefix sums to store the number of minimas and equal elements.

1 Like