Problem DISJOINTSUB

help
1

I was trying to find the intervals where value of x could lie. If all intervals can be merged to one interval then yes else no. I keep track of not taking consecutive by i += 2, and just check if two consecutive are decreasing or not.

Here is the submission link -

https://www.codechef.com/viewsolution/1054368142

Can anyone help me find the edge case for this solution?

1 Like
2

@codex4747
here plzz refer my c++ code for better understanding

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

int main() {
	// your code goes here
	int t;
	cin>>t;
	while(t--)
	{
	    int n;
	    cin>>n;
	    int a[n];
	    for(int i=0;i<n;i++)
	    {
	        cin>>a[i];
	    }
	    int xmin=0;
	    int xmax=INT_MAX;
	    int ch=0,prev=-1;
	    for(int i=1;i<n;i++)
	    {
	        if(a[i]<a[i-1])
	        {
	            if(prev==-1)
	            {
	                prev=i;
	                xmin=max(xmin,a[i-1]-a[i]);
	                if(i!=n-1)
	                {
	                    xmax=min(a[i+1]-a[i],xmax);
	                }
	                i++;
	            }
	            else
	            {
	                if(a[i]<a[prev])
	                {
	                    ch=1;
	                    break;
	                }
	                else
	                {
    	                prev=i;
    	                xmin=max(xmin,a[i-1]-a[i]);
    	                if(i!=n-1)
    	                {
    	                    xmax=min(a[i+1]-a[i],xmax);
    	                }
    	                i++;
	                }
	            }
	        }
	    }
	    if(ch==1||xmax<xmin)
	    cout<<"NO";
	    else
	    cout<<"YES";
	    cout<<endl;
	}
	return 0;
}