Shraeyas's blog

SPOJ Aggresive Cows
By Shraeyas, history, 7 years ago, In English

How to Use Binary Search to Solve this Problem?

Here's The Problem.

Thanks in advance.

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

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

Check this out: https://www.quora.com/What-is-the-correct-approach-to-solve-the-SPOJ-problem-Aggressive-cow

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

You first fix the minimum distance which should be maintained between adjacent cows and then use binary search to validate it, i.e. check if it is possible or not. If it is, then you can increase the minimum distance as this function is monotonic.

Now, how do you validate a particular "mid" value? Greedily. Just assign the first cow at the leftmost point and keep positioning the remaining cows as far to the right as possible while satisfying the min distance condition.

I think the code will make it clear.

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

    The code you shared gives wrong answer for the input 1 3 2 1 4 9

    Output should be 8 but the code gives 7.

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

      You can change

          mid = (start+end)/2;

    if(whetherpossible(mid))   start = mid + 1;

    else end = mid;

      to

          mid = (start+end+1)/2;

    if(whetherpossible(mid))   start = mid;

    else end = mid-1;

      because searching [mid+1, hi] can exit the range of possible answers, while [mid, hi] will keep a foothold (the value mid itself) so it will always contain a valid answer

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

        Hey, one more thing that needs to be changed is that return value should be start not start-1. I actually have one more doubt.

        I wrote this solution Solution — 1 and got AC. In this solution I have maintained interval bounds (low,high) in accordance to the predicate "Will the largest minimum distance 'mid' be able to accommodate at least 'c' cows?". This will give a series of 'yes' followed by 'no' and our target is to find mid corresponding to last yes.

        After getting AC on this solution, I checked some other solutions on the internet and I got a lot of solutions doing this Solution — 2. This solution also gets AC but I'm not able to convince myself how the different bounds' assignments in this one are also correct.

        Can you help me out with this? Thanks!

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

          In the second one lo = mid+1 exits the correct bounds, but the variable maxd stores the highest correct value of mid. So even though you can exit the bounds containing an answer, maxd takes care of that.

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

Binary search the answer

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

My code is having some problem I don't know what it is, it is giving wrong answer on submission and passed the sample testcase. Please help... Thanks. https://pastebin.com/itjySpKY

→ Reply