zarif_2002's blog

By zarif_2002, history, 5 months ago, In English,

I have solved this problem with binary search before. https://codeforces.com/contest/1156/problem/C But, I am trying to find out a deque solution but it fails at test 7.Why? 54565879 the algo is here. 1. sort the vector, 2. push every element at the end of the dq, 3. while pushing we would check if the difference between back and front element is greater than z(q.back() — q.front() >= z). if this condition is true, then increment the ans and pop the front and back elements. 4. when we finished traversing through the array, we get the answer.

what's wrong? please.

 
 
 
 
  • Vote: I like it
  • -6
  • Vote: I do not like it

»
5 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I think your approach is wrong. I had a similar approach and I also got WA on test 7. Take a look at my comment which I wrote after that contest (it contains a test on which most of the greedy solutions fail (your solution fails on it, too)).