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.