1074: Egg Drop

Difficulty: Advanced Category: Dynamic Programming / Binary Search Concept: Find minimum number of trials to determine the critical floor with k eggs and n floors Key Insight: The basic O(kn²) DP can be optimized with binary search on the drop floor (reducing to O(kn log n)). The optimal O(kn) approach inverts the question: "given t trials and k eggs, how many floors can we check?"

// 1074: Egg Drop — DP + Binary Search

// Approach 1: Basic DP O(k*n^2)
fn egg_drop_basic(eggs: usize, floors: usize) -> usize {
    let mut dp = vec![vec![0usize; floors + 1]; eggs + 1];
    for i in 1..=eggs {
        for j in 1..=floors {
            if i == 1 {
                dp[i][j] = j;
            } else {
                dp[i][j] = usize::MAX;
                for x in 1..=j {
                    let worst = 1 + dp[i - 1][x - 1].max(dp[i][j - x]);
                    dp[i][j] = dp[i][j].min(worst);
                }
            }
        }
    }
    dp[eggs][floors]
}

// Approach 2: DP with binary search O(k*n*log(n))
fn egg_drop_bs(eggs: usize, floors: usize) -> usize {
    let mut dp = vec![vec![0usize; floors + 1]; eggs + 1];
    for i in 1..=eggs {
        for j in 1..=floors {
            if i == 1 {
                dp[i][j] = j;
            } else {
                let (mut lo, mut hi) = (1, j);
                while lo < hi {
                    let mid = (lo + hi) / 2;
                    if dp[i - 1][mid - 1] < dp[i][j - mid] {
                        lo = mid + 1;
                    } else {
                        hi = mid;
                    }
                }
                dp[i][j] = 1 + dp[i - 1][lo - 1].max(dp[i][j - lo]);
            }
        }
    }
    dp[eggs][floors]
}

// Approach 3: Optimal — how many floors can we check with t trials and k eggs?
fn egg_drop_optimal(eggs: usize, floors: usize) -> usize {
    // dp[t][k] = max floors checkable with t trials and k eggs
    let mut dp = vec![vec![0usize; eggs + 1]; floors + 1];
    for t in 1..=floors {
        for k in 1..=eggs {
            dp[t][k] = 1 + dp[t - 1][k - 1] + dp[t - 1][k];
            if dp[t][k] >= floors {
                if k == eggs { return t; }
            }
        }
    }
    floors // fallback (1 egg case)
}

fn main() {
    println!("egg_drop(2, 10) = {}", egg_drop_bs(2, 10));
    println!("egg_drop(2, 100) = {}", egg_drop_optimal(2, 100));
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_basic() {
        assert_eq!(egg_drop_basic(1, 10), 10);
        assert_eq!(egg_drop_basic(2, 10), 4);
        assert_eq!(egg_drop_basic(2, 6), 3);
        assert_eq!(egg_drop_basic(3, 14), 4);
    }

    #[test]
    fn test_binary_search() {
        assert_eq!(egg_drop_bs(1, 10), 10);
        assert_eq!(egg_drop_bs(2, 10), 4);
        assert_eq!(egg_drop_bs(2, 6), 3);
    }

    #[test]
    fn test_optimal() {
        assert_eq!(egg_drop_optimal(1, 10), 10);
        assert_eq!(egg_drop_optimal(2, 10), 4);
        assert_eq!(egg_drop_optimal(2, 6), 3);
        assert_eq!(egg_drop_optimal(2, 100), 14);
    }
}

(* 1074: Egg Drop — DP + Binary Search *)

(* Approach 1: Basic DP O(k*n^2) *)
let egg_drop_basic eggs floors =
  let dp = Array.init (eggs + 1) (fun _ -> Array.make (floors + 1) 0) in
  for i = 1 to eggs do
    for j = 1 to floors do
      if i = 1 then dp.(i).(j) <- j
      else begin
        dp.(i).(j) <- max_int;
        for x = 1 to j do
          let worst = 1 + max dp.(i - 1).(x - 1) dp.(i).(j - x) in
          dp.(i).(j) <- min dp.(i).(j) worst
        done
      end
    done
  done;
  dp.(eggs).(floors)

(* Approach 2: DP with binary search O(k*n*log(n)) *)
let egg_drop_bs eggs floors =
  let dp = Array.init (eggs + 1) (fun _ -> Array.make (floors + 1) 0) in
  for i = 1 to eggs do
    for j = 1 to floors do
      if i = 1 then dp.(i).(j) <- j
      else begin
        let lo = ref 1 and hi = ref j in
        while !lo < !hi do
          let mid = (!lo + !hi) / 2 in
          let broke = dp.(i - 1).(mid - 1) in
          let survived = dp.(i).(j - mid) in
          if broke < survived then lo := mid + 1
          else hi := mid
        done;
        let x = !lo in
        dp.(i).(j) <- 1 + max dp.(i - 1).(x - 1) dp.(i).(j - x)
      end
    done
  done;
  dp.(eggs).(floors)

(* Approach 3: Optimal DP — how many floors can we check with t trials and k eggs? *)
let egg_drop_optimal eggs floors =
  (* dp.(t).(k) = max floors checkable with t trials and k eggs *)
  let dp = Array.init (floors + 1) (fun _ -> Array.make (eggs + 1) 0) in
  let t = ref 0 in
  while dp.(!t).(eggs) < floors do
    incr t;
    for k = 1 to eggs do
      dp.(!t).(k) <- 1 + dp.(!t - 1).(k - 1) + dp.(!t - 1).(k)
    done
  done;
  !t

let () =
  assert (egg_drop_basic 1 10 = 10);
  assert (egg_drop_basic 2 10 = 4);
  assert (egg_drop_basic 2 6 = 3);
  assert (egg_drop_basic 3 14 = 4);

  assert (egg_drop_bs 1 10 = 10);
  assert (egg_drop_bs 2 10 = 4);
  assert (egg_drop_bs 2 6 = 3);

  assert (egg_drop_optimal 1 10 = 10);
  assert (egg_drop_optimal 2 10 = 4);
  assert (egg_drop_optimal 2 6 = 3);
  assert (egg_drop_optimal 2 100 = 14);

  Printf.printf "✓ All tests passed\n"

📊 Detailed Comparison

Egg Drop — Comparison

Core Insight

The egg drop problem asks for worst-case minimum trials. The key insight for the optimal solution: instead of asking "given k eggs and n floors, what's the minimum trials?", ask "given t trials and k eggs, what's the maximum floors we can check?" This gives the recurrence `f(t,k) = 1 + f(t-1,k-1) + f(t-1,k)`.

OCaml Approach

2D array DP with nested loops
`ref` cells for binary search pointers
`max_int` as initial sentinel for minimization
`while` loop with `ref` counter for optimal approach

Rust Approach

2D `vec!` DP table
Binary search with tuple destructuring `let (mut lo, mut hi)`
`usize::MAX` as sentinel
Early return from nested loop for optimal approach
Method chaining `.max()` and `.min()`

Comparison Table

Aspect	OCaml	Rust
Sentinel	`max_int`	`usize::MAX`
Binary search	`ref` pointers + `while`	`let (mut lo, mut hi)` + `while`
Min/max	`min`/`max` functions	`.min()`/`.max()` methods
Optimal loop	`while dp.(!t).(eggs) < floors`	`for t in 1..=floors` + early return
Early exit	Increment `ref` counter	`return t` from inner loop