Skip to content

Latest commit

 

History

History
227 lines (174 loc) · 6.25 KB

6.AggressiveCows.md

File metadata and controls

227 lines (174 loc) · 6.25 KB

🐄 Aggressive Cows (Maximize Minimum Distance)

📄 Problem Statement

You have n stalls located at positions given by the integer array stalls. You want to place k cows in these stalls such that the minimum distance between any two cows is maximized. Return that maximum possible minimum distance.

  • Input:

    • Integer n: number of stalls
    • Vector stalls of length n, giving stall positions
    • Integer k: number of cows to place

  • Output:

    • Maximum minimum distance possible between any two cows

💡 Intuition

  • If you pick a candidate distance d, you can greedily place cows:

    1. Place the first cow at the first (lowest) stall.
    2. For each subsequent stall, if its position is at least d away from the last placed cow, place another cow there.
    3. Count how many cows you can place.

  • If you can place ≥ k cows at distance ≥ d, then d is feasible; otherwise it's too large.

  • The feasibility of d is a monotonic predicate:

    • Smaller d → easier to place cows → feasible.
    • Larger d → harder → eventually infeasible.

  • Binary‑search on d over [1 … max(stalls)-min(stalls)] finds the largest feasible distance in O(log D · n).

🐢 Brute‑Force Approach

Try every possible d from 1 up to (max–min):

int aggressiveCowsBrute(vector<int>& stalls, int k) {
    sort(stalls.begin(), stalls.end());
    int low = 1;
    int high = stalls.back() - stalls.front();
    int best = 0;
    for (int d = low; d <= high; ++d) {
        int placed = 1, last = stalls[0];
        for (int x : stalls) {
            if (x - last >= d) {
                placed++;
                last = x;
            }
        }
        if (placed >= k) best = max(best, d);
    }
    return best;
}
  • Time Complexity: O((max–min)·n)
  • Space Complexity: O(1)

❌ Too slow when stall positions span a large range.

🚀 Optimal Approach: Binary Search on Distance

  1. Sort the stalls array.

  2. Bounds for d:

    int low  = 1;
int high = stalls.back() - stalls.front();

  3. Predicate canWePlace(d):

    int count = 1, last = stalls[0];
for (int i = 1; i < n; ++i) {
  if (stalls[i] - last >= d) {
    count++;
    last = stalls[i];
  }
  if (count == k) return true;
}
return false;

  4. Binary search:

    int best = 0;
while (low <= high) {
  int mid = low + (high - low) / 2;
  if (canWePlace(mid)) {
    best = mid;       // mid works, try larger
    low = mid + 1;
  } else {
    high = mid - 1;   // mid too big, try smaller
  }
}
return best;

This runs in O(n log D), where D = high.

✏️ Full Code with main()

#include <bits/stdc++.h>
using namespace std;

/**
 * Checks if we can place 'k' cows in sorted 'stalls' such that
 * the minimum distance between any two is at least 'd'.
 */
bool canWePlace(const vector<int>& stalls, int d, int k) {
    int count = 1;
    int last  = stalls[0];
    for (int x : stalls) {
        if (x - last >= d) {
            count++;
            last = x;
            if (count == k) return true;
        }
    }
    return false;
}

/**
 * Returns the maximum minimum distance to place k cows.
 */
int aggressiveCows(vector<int>& stalls, int k) {
    sort(stalls.begin(), stalls.end());
    int n    = stalls.size();
    int low  = 1;
    int high = stalls[n-1] - stalls[0];
    int best = 0;

    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (canWePlace(stalls, mid, k)) {
            best = mid;       // feasible, try larger
            low  = mid + 1;
        } else {
            high = mid - 1;   // not feasible, decrease d
        }
    }
    return best;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;
    vector<int> stalls(n);
    for (int i = 0; i < n; ++i) {
        cin >> stalls[i];
    }

    cout << aggressiveCows(stalls, k) << "\n";
    return 0;
}

📊 Complexity Analysis

Phase Time Complexity Space Complexity
Sorting stalls O(n log n) O(1)*
Each canWePlace check O(n) O(1)
Binary search (~log D) O(n log D) O(1)
Overall O(n log n + n log D) ≈ O(n log n) O(1)

* Sorting uses O(log n) stack space in some implementations.

✅ Test Cases

stalls k Output Explanation
[1,2,4,8,9] 3 3 Place at 1,4,8 → min distance = 3.
[1,2,4,8,9] 4 2 Place at 1,2,4,8 → min distance = 2.
[3,1,4,7,2] 3 3 Sorted [1,2,3,4,7], place at 1,4,7.
[0,5,10,15] 2 15 Best spacing = between 0 and 15.
[5,5,5,5] 2 0 All stalls same ⇒ max min distance = 0.

🎯 Tips & Tricks

  • Always sort your positions before greedy placement.
  • Use long or int64 if positions can exceed 10⁹ to avoid overflow in subtraction.
  • Remember to track the last placed stall index.

🔄 Variations

  1. Aggressive Horses (same problem under different guise).
  2. Place k antennas to maximize minimum signal distance.
  3. Social distancing: place people in seats to maximize minimum spacing.

❓ FAQs

Q1. Why binary search on distance and not linear?
The range of possible distances can be large (up to 10⁹), so linear would be too slow.

Q2. Can we place cows in any order?
They must occupy distinct stalls; greedy in sorted order is optimal.

Q3. What if stalls have duplicates?
Duplicate positions effectively force distance zero; solution still handles correctly.

Q4. What if k = 1?
You can place one cow anywhere; maximum minimum distance is irrelevant—return any stall difference (commonly 0).