import Mathlib /-! # Assign Cookies Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie. Each child i has a greed factor g[i], which is the minimum size of a cookie that the child will be content with; and each cookie j has a size s[j]. If s[j] >= g[i], we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number. ## Constraints - 1 <= g.length <= 3 * 10^4 - 0 <= s.length <= 3 * 10^4 - 1 <= g[i], s[j] <= 2^31 - 1 - Note: This question is the same as 2410: Maximum Matching of Players With Trainers. ## Provided examples - `g = [1, 2, 3], s = [1, 1]` → `1` - `g = [1, 2], s = [1, 2, 3]` → `2` - `g = [1], s = [1]` → `1` ## Synthesized negative examples - invalid input: `g = [], s = []` ([structural] a predicate that admits 1 <= g.length <= 3 * 10^4. empty children array below length minimum) - invalid input: `g = [0], s = []` ([structural] a predicate that admits 1 <= g[i], s[j] <= 2^31 - 1. greed factor one below minimum) - invalid input: `g = [-1], s = [1]` ([structural] a predicate that admits 1 <= g[i], s[j] <= 2^31 - 1. negative greed factor outside allowed set) - `g = [1, 2, 3], s = [1, 1]` → `0` is wrong ([structural] answer is not required to maximize content children. giving no cookies achieves 0; only maximality rejects it) - `g = [1, 2], s = [1, 2, 3]` → `3` is wrong ([structural] no assignment is required to reach the answer. 3 exceeds the number of children; no assignment can content 3.) - `g = [1], s = [1]` → `0` is wrong ([structural] relaxed_reading not applicable; maximality stated as achievability alone. 0 is achieved by ignoring the cookie but is not maximum) -/ namespace PAssignCookies abbrev Input := (List Nat) × (List Nat) abbrev Output := Nat /-! ### Specification helpers -/ /-- `m` is a valid assignment of cookies `s` to children `g`: every pair's indices are in range with `g[i] ≤ s[j]`, and no child or cookie index repeats. -/ def IsValidMatching (g s : List Nat) (m : Finset (Nat × Nat)) : Prop := (∀ p ∈ m, p.1 < g.length ∧ p.2 < s.length ∧ g[p.1]! ≤ s[p.2]!) ∧ (∀ p₁ ∈ m, ∀ p₂ ∈ m, p₁.1 = p₂.1 → p₁ = p₂) ∧ (∀ p₁ ∈ m, ∀ p₂ ∈ m, p₁.2 = p₂.2 → p₁ = p₂) /-! ### Validity predicate (V) -/ /-- Valid input: `g` nonempty, both lists of length at most 3·10^4, every entry between 1 and 2^31 − 1. -/ def isValidInput (input : Input) : Bool := decide (1 ≤ input.1.length ∧ input.1.length ≤ 3 * 10^4 ∧ input.2.length ≤ 3 * 10^4 ∧ (∀ x ∈ input.1, 1 ≤ x ∧ x ≤ 2^31 - 1) ∧ (∀ x ∈ input.2, 1 ≤ x ∧ x ≤ 2^31 - 1)) /-! ### Ideal specification (P_spec) -/ /-- `result` is the greatest number of children that any valid cookie assignment makes content. -/ def maxContentChildren_spec (input : Input) (result : Output) : Prop := IsGreatest {k | ∃ m : Finset (Nat × Nat), IsValidMatching input.1 input.2 m ∧ m.card = k} result /-! ### Decidable specification (P_check) -/ /-- The finite grid of in-range child-cookie index pairs; `IsValidMatching`'s in-range clause confines every valid matching to subsets of it. -/ def matchingGrid (g s : List Nat) : Finset (Nat × Nat) := Finset.range g.length ×ˢ Finset.range s.length /-- Every clause of `IsValidMatching` is a bounded quantification over a `Finset` with decidable body, so the predicate is decidable once the definition is unfolded. -/ instance decidableIsValidMatching (g s : List Nat) (m : Finset (Nat × Nat)) : Decidable (IsValidMatching g s m) := inferInstanceAs (Decidable ((∀ p ∈ m, p.1 < g.length ∧ p.2 < s.length ∧ g[p.1]! ≤ s[p.2]!) ∧ (∀ p₁ ∈ m, ∀ p₂ ∈ m, p₁.1 = p₂.1 → p₁ = p₂) ∧ (∀ p₁ ∈ m, ∀ p₂ ∈ m, p₁.2 = p₂.2 → p₁ = p₂))) /-- Executable checker for `maxContentChildren_spec` over the matchings contained in `matchingGrid`. -/ def maxContentChildren_check (input : Input) (result : Output) : Bool := decide ((∃ m ∈ (matchingGrid input.1 input.2).powerset, IsValidMatching input.1 input.2 m ∧ m.card = result) ∧ (∀ m ∈ (matchingGrid input.1 input.2).powerset, IsValidMatching input.1 input.2 m → m.card ≤ result)) /-- `IsGreatest` restated with explicit binders. -/ theorem acg_spec_eq (input : Input) (result : Output) : maxContentChildren_spec input result ↔ ((∃ m : Finset (Nat × Nat), IsValidMatching input.1 input.2 m ∧ m.card = result) ∧ ∀ y : Nat, (∃ m : Finset (Nat × Nat), IsValidMatching input.1 input.2 m ∧ m.card = y) → y ≤ result) := Iff.rfl /-- Every valid matching is a subset of the grid the checker enumerates. -/ theorem acg_mem_powerset_matchingGrid (g s : List Nat) (m : Finset (Nat × Nat)) (hm : IsValidMatching g s m) : m ∈ (matchingGrid g s).powerset := by rw [Finset.mem_powerset] intro p hp obtain ⟨h1, h2, -⟩ := hm.1 p hp unfold matchingGrid rw [Finset.mem_product, Finset.mem_range, Finset.mem_range] exact ⟨h1, h2⟩ /-- On valid input the checker accepts exactly the specified outputs. -/ theorem maxContentChildren_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : maxContentChildren_check input result ↔ maxContentChildren_spec input result := by rw [acg_spec_eq] unfold maxContentChildren_check rw [decide_eq_true_eq] constructor · rintro ⟨⟨m, hmp, hmv, hmcard⟩, hub⟩ refine ⟨⟨m, hmv, hmcard⟩, ?_⟩ rintro y ⟨t, ht, rfl⟩ exact hub t (acg_mem_powerset_matchingGrid input.1 input.2 t ht) ht · rintro ⟨⟨m, hmv, hmcard⟩, hub⟩ refine ⟨⟨m, acg_mem_powerset_matchingGrid input.1 input.2 m hmv, hmv, hmcard⟩, ?_⟩ intro t _ ht exact hub t.card ⟨t, ht, rfl⟩ /-! ### Implementation helpers -/ /-- Sort a list of naturals into nondecreasing order by merge sort. -/ def sortNatList (xs : List Nat) : List Nat := xs.mergeSort (fun a b => decide (a ≤ b)) /-- Two-pointer scan over sorted greed factors and sorted cookie sizes, counting the greedy assignments. -/ def greedyMatch : List Nat → List Nat → Nat | [], _ => 0 | _, [] => 0 | g :: gs, c :: cs => if g ≤ c then greedyMatch gs cs + 1 else greedyMatch (g :: gs) cs termination_by g s => g.length + s.length /-! ### Main algorithm (impl) -/ /-- Maximum number of content children: sort both lists and greedily give each child the smallest sufficient cookie. -/ def findContentChildren (input : Input) : Output := greedyMatch (sortNatList input.1) (sortNatList input.2) /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem findContentChildren_correct (input : Input) (h : isValidInput input) : maxContentChildren_spec input (findContentChildren input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ([1, 2, 3], [1, 1]) #guard isValidInput ([1, 2], [1, 2, 3]) #guard isValidInput ([1], [1]) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ([], [])) #guard !(isValidInput ([0], [])) #guard !(isValidInput ([0 - 1], [1])) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard maxContentChildren_check ([1, 2, 3], [1, 1]) 1 #guard maxContentChildren_check ([1, 2], [1, 2, 3]) 2 #guard maxContentChildren_check ([1], [1]) 1 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(maxContentChildren_check ([1, 2, 3], [1, 1]) 0) #guard !(maxContentChildren_check ([1, 2], [1, 2, 3]) 3) #guard !(maxContentChildren_check ([1], [1]) 0) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard findContentChildren ([1, 2, 3], [1, 1]) == 1 #guard findContentChildren ([1, 2], [1, 2, 3]) == 2 #guard findContentChildren ([1], [1]) == 1 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard maxContentChildren_check ([1, 2, 3], [1, 1]) (findContentChildren ([1, 2, 3], [1, 1])) #guard maxContentChildren_check ([1, 2], [1, 2, 3]) (findContentChildren ([1, 2], [1, 2, 3])) #guard maxContentChildren_check ([1], [1]) (findContentChildren ([1], [1])) end PAssignCookies