I was trying to solve 279C
but getting WA in test case-21, the case is huge that is why cannot figure out why getting WA.
My Approach : First i find out all ladder segment using two-pointer technique, then i used binary search to find whether the given segment is in any ladder segment. I think my logic correct but still why getting WA. My Code
As you can see per my submission history on this task, I had the same problem :)
On this test your code gives a wrong answer.
can you plz tell me what is wrong with my solution https://codeforces.net/contest/279/submission/82392621
logic- we need to count the no. of valleys that lie in the segment except corners and answer if Yes if no. of valley=0
upd-: sorry for asking, i got that array =4 4 4 3 3 3 4 4 4 and l=5 r=8
Thanks for your reply! Now my code is giving correct answer for your case but still i am getting wa.
I solved this problem in another approach, but i just want to know what is wrong in this Code
Nevermind i got it, i was missing some ladder count. Thanks to Abhayp001, seeing your upd i got it.
This can be solved in $$$O(M+N)$$$, which should be better complexity that your binary search solution.
(Pseduo-code):
Array $$$a$$$ is taken as input (0-based index)
For $$$i = 0 .. n - 1$$$, define $$$l_i$$$ as the leftmost(smallest) index such that $$$a[l_i] \leq a[l_{i}+1] \leq ... \leq a[i] $$$ Note: $$$l_i <= i$$$
Similarly, for $$$i = 0 .. n - 1$$$, define $$$r_i$$$ as the rightmost (largest) index such that $$$a[i] \geq ... \geq a[r_{i}+1] \geq a[r_i] $$$
Then to process each query in $$$O(1)$$$, we precompute for each index $$$i \in 0 .. n - 1 : pre[i] = $$$ the rightmost point of any ladder passing through index $$$i$$$.
For DP recurrences, see code. Note the order of the for loops. For $$$r_i$$$, we need to go in reverse.
If anything is unclear, let me know.
I didn't understand your solution. What exactly are you storing in the array that you do binary search on? Its hard to debug your code when if you don't tell your idea..
I understood your approach. Thanks!!
Anyway, what i did in my code is : i iterate the array and by two pointer i took the largest valid ladder and push their starting and ending point in pair of vector. Now, i know how many ladder i have, than i did binary search on the ladders and tried to find out whether given segment lies in any of ladder.