APPROACH

Since it is max of min problem we can consider binary Search

Let's first figure out what the questions is saying a) arr[i] denotes the position of the stall b) k = number of cows c) Need to maximize the minimum distance d) So according to what we've learned i need to go over the minimum values and then find maximum among them.

Figure out Minimum Distance Values: a) Now the minimum distance will be between any 2 consecutive stalls b) So we need to go over the consecutive stalls only

Figure out high and low: a) low -> 1 (minimum distance of 1 between any two stalls) b) high -> Maximum Distance between any two stalls (max - min)

Think of the f(x) function that will help us determine the feasibity of a minimum distance x a) The minimum distance, as stated can be between any 2 consecutive stalls b) if keeping this minimum distance (note: min distance means it can take more than this as well), we can fit all k cows, then it is a possible answer.

Now the modified BS part: a) if f(x) is true, then x is a possible answer. However since we're looking for MAX, we move rightward: if stalls >= k : low = mid + 1 b) if f(x) is false, all cows did not fit. That means we need to descrease the distance: else high = mid - 1

Steps to Solve the Problem

Define the Search Range:

Determine the minimum possible value (low) and maximum possible value (high) for the answer. These are often based on the problem constraints (e.g., the distance between the first and last element in a range).

Binary Search Loop:

While low < high:

Compute the midpoint (mid) of the current range.

Check Feasibility: Determine if it's possible to achieve a maximum value of mid (i.e., if the condition is satisfied).

Adjust the Search Range:

If feasible, set high = mid to search for a smaller value.

If not feasible, set low = mid + 1 to search for a larger value.

Return the Answer:

Once the loop ends, low (or high) is the minimum value of the maximum that satisfies the condition.

Key Concepts

Feasibility Check: For a given candidate value (e.g., a distance, a value in an array), the check function determines whether it's possible to achieve the desired condition. This function is typically monotonic—if a value is feasible, all larger values are also feasible.

Binary Search on the Maximum: The search is over the range of possible maximum values, not directly over the array elements. This is because the problem is to minimize the maximum, not to find a specific element in the array.

Example: Placing Cows in Stalls

Problem: Place k cows in n stalls such that the maximum distance between adjacent cows is minimized.

Steps:

Search Range: low = 0, high = max(stalls) - min(stalls).

Feasibility Check: For a given distance mid, check if it's possible to place k cows such that no two are more than mid apart.

Binary Search: Use the above logic to find the smallest mid that satisfies the condition.

Another Example: Minimizing Maximum Subarray Sum

Problem: Find the minimum possible maximum of the sum of any subarray of length k in an array.

Steps:

Search Range: low = 0, high = sum of all elements.

Feasibility Check: For a given value mid, check if there exists a subarray of length k whose sum is ≤ mid.

Binary Search: Adjust the search range to find the smallest mid that satisfies the condition.

Why Binary Search Works

Monotonicity: If a value is feasible, all larger values are also feasible.

Efficiency: Reduces the search space by half in each iteration, resulting in O(log(max_value)) complexity.

Conclusion

To find the minimum of the maximum in a problem, perform binary search over the possible values of the maximum. For each candidate value, use a feasibility check to determine if it's possible to satisfy the condition. The minimum feasible value is the answer. This approach is widely used in optimization problems where the goal is to minimize the worst-case scenario (e.g., maximum distance, maximum sum, etc.).

----

Max of Min

To solve the "max of min" problem, we use binary search to find the maximum possible value of the minimum value that satisfies a given condition. This is often used in optimization scenarios where the goal is to maximize the minimum value (e.g., maximizing the minimum distance between cows, or maximizing the minimum number of coins in a subset). Below is a structured explanation of the approach, including how to detect the problem and implement the solution.

Key Concepts for "Max of Min" Problem

Binary Search on the Minimum Value:

The search is over the possible values of the minimum (e.g., distances, values, etc.).

The goal is to find the largest value that can be achieved as the minimum under the problem's constraints.

Feasibility Check:

For a given candidate value mid, the feasibility check determines whether it is possible to achieve a minimum value of at least mid.

If feasible, we can try higher values (i.e., set low = mid). If not, we need to try lower values (i.e., set high = mid - 1).

Monotonicity:

The feasibility of a value mid implies that all values less than mid are also feasible. This ensures the binary search can proceed correctly.

Example: Maximize the Minimum Distance Between Cows

Problem: Place k cows in n stalls such that the minimum distance between any two cows is as large as possible.

Steps:

Search Range:

low = 0 (minimum possible distance).

high = max(stalls) - min(stalls) (maximum possible distance).

Binary Search Loop:

While low < high:

Compute mid = (low + high) // 2.

Feasibility Check: Can we place k cows such that the minimum distance between any two cows is ≥ mid?

If feasible, set low = mid (try larger values).

If not feasible, set high = mid - 1 (try smaller values).

Result:

After the loop, low (or high) is the maximum possible minimum distance.

Feasibility Check for "Max of Min"

The feasibility check is reversed compared to the "min of max" case. For example:

In the min of max problem, we check if it is possible to achieve a maximum distance ≤ mid.

In the max of min problem, we check if it is possible to achieve a minimum distance ≥ mid.

Example Feasibility Check:def is_possible(stalls, k, min_dist): count = 1 # Number of cows placed last_pos = stalls[0] for pos in stalls[1:]: if pos - last_pos >= min_dist: count += 1 last_pos = pos if count == k: return True return count >= k

This function checks if it's possible to place k cows such that the minimum distance between adjacent cows is ≥ min_dist.

How to Detect the Problem

The problem is typically detected by the following:

Goal: Maximize the minimum value (e.g., distance, number of coins, etc.).

Constraints:

The problem involves a trade-off between values (e.g., placing cows to maximize the minimum distance).

The feasibility check is monotonic (if a value is feasible, all smaller values are also feasible).

Example: Maximize the Minimum Number of Coins in Subsets

Problem: Given an array of coins, find the maximum value of the minimum number of coins in any subset of size k.

Approach:

Search Range: low = 1, high = max(coins).

Feasibility Check: Can we select k subsets such that the minimum number of coins in any subset is ≥ mid?

Binary Search: Adjust the search range based on the feasibility check.

Key Differences Between "Min of Max" and "Max of Min"

Conclusion

To solve the "max of min" problem:

Perform binary search over the possible values of the minimum.

Use a feasibility check to determine if a given minimum can be achieved.

Adjust the search range based on the feasibility result.

The final answer is the largest feasible minimum.

Since it is a Minimum of Max problem, use binary search

Figuring out what the question is saying: a) arr[i] is the number of pages in i-th book b) m students. Each Student must be assigned a book c) ALL books must be covered (Each book must be allotted to only one student) d) c will help us figure out f(x) e) since this is min of max, we need to go over all the maximum page values, and then minimize them

We need to find the maximum possible values: a) In the worst case, each student can be assigned one book b) If one student, they're assigned all books

Figure out low and high: a) low -> Each book needs to be assigned. So low will be max(arr) so each assign is possible. b) high -> sum(arr) in case there is one student. can be assigned all books

Figure out the feasibility conditions and f(x) a) since all books need to be assigned. It should be exactly k. b) We start out by assigning one book, then add on till it becomes > MaxPages (x. as x is the maximum possible pages that can be assigned) c) we return x

BS a) == k -> we have found a possible solution. but since we want minimum move left b) we need to assign less pages so all students can be covered. move left. c) >k -> we have assigned too few pages and now books are left. so increase pages and move rightward if <= k: high = mid -1 else: low = mid + 1