nbz_11's blog

Help in binary search!
By nbz_11, history, 7 years ago, In English

I read the main idea behind binary search and how it is implemented , but am never able to apply it using certain modifications . I tried solving http://www.spoj.com/problems/AGGRCOW/ , but have not been able to. Can someone please cite some useful resources , from where I can get an idea about how to modify binary search algorithm as and when the need arises. Or maybe , if someone can give an idea , as to how they think while applying binary seacrh.

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

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

u can check on geeks for geeks website

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

This is the material you want. here

→ Reply
»
7 years ago, # |
← Rev. 6   Vote: I like it +26 Vote: I do not like it

Well when I first started to learn binary search I used the topcoder one and it was pretty useful and I solved 2 questions right away after the tutorial one of them was this Aggressive cows question, I didn't find it hard tbh but it's really good in terms of "first practice" I just read the quora answer and this guy had a great answer that I hope you understood but if you didn't I'll explain what I was thinking when I solved it to answer this part of your question : "Or maybe , if someone can give an idea , as to how they think while applying binary seacrh."

So first off I took out a paper and wrote down the sorted version of the stalls positions cause it was mentioned it was lined up in a straight line and I found that I need to find a "certain number" which represents the minimum distance I need in order to line up C amount of cows away from each other without conflicts, so I was like well, why not place the first cow on position 1 and then start checking for the next stall position that is ATLEAST "certain number" (distance) away from my previous selection.

So I was like, yeah..binary search will find all the numbers that satisfy my condition and thus it'll find the minimum number too as long as I don't stop it from searching, because if our binary search got to a point where it found the FIRST number that satisfies that condition let that number be 10, it won't do anything because it'll only stop searching once "Low is greater than High", according to a regular binary search loop condition, unless you stop it on first find, but for this problem we need it to keep going.

Now to how I approached it even further, I was like..How do I know that a number satisfies my condition? Well, I'll take that number through an O(N) Loop and check if that number satisfies my condition or not(i.e place C amount of cows, away from each other and with a distance that does not make them hurt each other).

Even further elaboration: I'll have to take number 3, because that's the only number that satisfies the condition in this sample.

1 2 4 8 9 -> stall positions lined up and sorted.

I mentioned I'll put my first cow on position 1(That is a greedy approach). So now I have 1 cows places out of a total of 3.

Step 1: I placed my first cow on stall position 1 so now I need some distance between the stalls that is ATLEAST 3(The number I chose/The number I am testing for validity right now).

Step 2: I am at the stall#2 now, is my current stall position — my last selected position atleast 3? ( 2 — 1 >= 3 ? No.) So I didn't place a cow at this step.

Step 3: is my current stall position — my last selected position atleast 3? (4 — 1 >= 3? Yes.) I will place a cow here for a total of 2 out of 3 cows so far. and now I selected stall#4 to be my new "last" selected position because I'll need to search for something beyond stall#4 that satisfies this condition too.

Step 4: Repeat, (8 — 4 >= 3? Yes.) I will place a cow here too, now I have a total of 3 out of 3 cows placed and since I finished placing my cows successfully I'll take that number. and due to our nature of binary search it'll continue searching normally but fortunately nothing below 3 or above 3 will satisfy the condition so my last return from the binary search function will be 3 and that is our final answer.

If you take another number other than 3 and apply the same procedures you shall see that this number won't fulfill our condition(i.e place C cows away from each other with a minimum distance so they don't hurt each other)

Cheers, and correct me if I said something wrong!

Here is my code, I made an ideone version of it, hope it clarifies even further: Ideone Code

EDIT: This codeforces problem is almost similar to that one http://mirror.codeforces.com/problemset/problem/492/B

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

In most problems: When you need to find largest N such that ..., first check if something is true for N, will it be true for all K < N or not? If so, then apply binary search on N, and reduce search space by looking at the truth value of mid points. Try:

812C 68B 371C

→ Reply