Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

kipawa's blog

Need help in problem 279C (Ladders)
By kipawa, history, 9 years ago, In English

I was solving problem 279C (Ladders)
My logic is to create two arrays inc and dec
inc[i] contains the largest j, such that i<=j and the sequence from ai, ai+1, ..., aj is increasing.
dec[i] contains minimum j, such that i>=j and the sequence from aj, aj+1, ..., ai is decreasing.
Now the sequence l,r is ladder if inc[l-1]==dec[r-1] || inc[l-1]>=r-1 || dec[r-1]<=l-1 (I used 0 based indexing)
I am getting WA on test 20, please help me!
Solution Link
Thanks in advance!

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Hey I have solved the problem and used a similar approach here. Although my array names are a bit confusing, I have commented what they mean.

→ Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it
  1. have 2 dp arrays say rt[100005] and lt[100005];
  2. rt[i] stores the highest index to the right of i such that arr[i....rt[i]] is non decreasing
  3. and lt[i] stores the smallest index such that arr[lt[i].....i] is non-increasing.
  4. you can do each of these in O(n)
  5. now for a given query a,b , if rt[a] >= lt[b] ... i,e. arr[a..........rt[a]] — >non-decreasing ..........arr[lt[b].......b] ->non-increasing means there is a ladder. Came from a friend of mine. Helped me.
→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks man, your solution helped me identify the test case where I was wrong.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks a lot. That really helped me.

    → Reply