shubhiks1032's blog

Always falling from this ladder!
By shubhiks1032, history, 7 years ago, In English

Problem Name: Ladder Problem Link: http://codeforces.com/problemset/problem/279/C My solution: http://codeforces.com/contest/279/submission/23569730

I came up with a different solution that the editorial and other people solutions however its failing on one of the test cases and I am not able to find any mistake.

Basically I have inserted the checkpoints at which the ladder is starting and ending and within a query I use upper_bound to get the rightmost point if the given interval can be a ladder and compare it with the given "right" value and output the corresponding answer. Any help would be highly appreciated. :)

  • Vote: I like it
  • +1
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
7 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

I have found your problem. The issue is that you do not consider that the descending part of a ladder can also be the starting part of another latter. Take for example the array 0 0 0 1 1 1 0 0 0 1 1 1. Suppose that your query is 7 - 10. The elements in your set would be {0, 9, 13}. Your binary search would take you to to = 9. Then, you answer NO, when answer is YES. This happens because the element 7 belongs to the ladder going from 1 to 9 and the one going from 7 to 12. However, I can only diagnose the problem, and I have not been able to find any solution :/

UPD: I have found a solution! Use another set that does the opposite than the first set i.e. one that registers where does each ladder start. Then, you should also see if the biggest element lower than r in this set is lower-equal than l. If this happens, the answer is also yes.

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

10 2 1 2 2 5 3 3 6 6 8 10 5 10 6 10

for 5 to 10 answer must be Yes

→ Reply