I used an auxiliary array initialized it with zeroes than update an index with 1 if it’s greater than previous value in the actual array else remain 0 signifies that whether sequence increased or decreased at that index.
I observe that if the value at L+1 is not equal to the value at R then answer is yes
Else No
Please check this solution :-
https://www.codechef.com/viewsolution/28967994
I got TLE in this solution , please tell how to avoid it?
U r getting tle bcoz u iterating for each given ranges making complexity of your code of an order of O (n^2).
Just check above solutions for an idea.
Because its O((R-L)Q) and (R-L) in worst case can be N so O(NQ) which is of order 10^10, you need to reduce this order to 10^5-10^6 ish. Read the editorial and check solutions posted above.
Quite commendable nice…
Thank you
Please tell me where i am wrong in my approach!
check the solution link
that was amazing!
How did you got this approach…is it just by observing the pattern in auxiliary array or there is some logic behind it ??
Thank you!!
i used segment tree for this however got tle .complexity was just O(Qlog(N)+N).also got segmentation for 1st case.can you take a look at the solution.
https://www.codechef.com/viewsolution/28976764
It is an observation but a true fact
If the values at L+1 and R is same then the no. Of increase and decrease in between will not
Will always diff by at least 1 you can check it out. But if the values are different then for sure the increase and decrease is equal.
I am getting TLE in some of the test cases…can somebody please explain where i am going wrong??
here is my submission :- CodeChef: Practical coding for everyone
I am not getting the approaches used in above solutions as I am new to programming .
Can you explain how to reduce time complexity of a written code , for example - reducing complexity of : CodeChef: Practical coding for everyone
Is there any way to reduce complexity?
There is no need to count the number of increasing/decreasing sub sequences. Just observe the nature of sequence(inc/dec) formed by first two and the last two elements of the series between the given L, R bounds ( both inclusive). If the nature of both sequences is same then verdict is NO, otherwise YES. It’s because after the end of every increasing sequence, there has to be a decreasing sequence before the next increasing sequence begins. Therefore in any given L-R span, the difference of counts of both of these sequences cannot be more than 1. Think about it. Here’s my solution : ISBIAS solution
Try increasing the size of segment tree.
So perfect bro!
Perfect explanation!! Thank You!!
It can be done in O(N+Q) if you store the prefix count of decreasing and increasing arrays.
Every query can be solved in O(1) without pre-computation. Wait for the official editorial
