Блог пользователя Shraeyas

SPOJ Aggresive Cows
Автор Shraeyas, история, 7 лет назад, По-английски

How to Use Binary Search to Solve this Problem?

Here's The Problem.

Thanks in advance.

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      6 лет назад, # ^ |
      ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      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

      → Ответить
      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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!

        → Ответить
        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

          → Ответить
»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Binary search the answer

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить