import Mathlib /-! # Smallest Range Ii You are given an integer array nums and an integer k. For each index i where 0 <= i < nums.length, change nums[i] to be either nums[i] + k or nums[i] - k. The score of nums is the difference between the maximum and minimum elements in nums. Return the minimum score of nums after changing the values at each index. ## Constraints - 1 <= nums.length <= 10^4 - 0 <= nums[i] <= 10^4 - 0 <= k <= 10^4 ## Provided examples - `nums = [1], k = 0` → `0` - `nums = [0, 10], k = 2` → `6` - `nums = [1, 3, 6], k = 3` → `3` ## Synthesized negative examples - invalid input: `nums = [], k = 0` ([structural] a predicate that admits 1 <= nums.length <= 10^4. empty where at least one element is required) - invalid input: `nums = [-1], k = 0` ([structural] a predicate that admits 0 <= nums[i] <= 10^4. negative element, one below the stated minimum) - invalid input: `nums = [10001], k = 0` ([structural] a predicate that admits 0 <= nums[i] <= 10^4. one past the stated maximum element) - `nums = [1], k = 0` → `-1` is wrong ([structural] minimum stated as a lower bound without requiring attainability. no assignment yields -1; scores are nonnegative) - `nums = [0, 10], k = 2` → `10` is wrong ([structural] minimality stated as achievability alone. 10 is attained by a valid modification but is not minimum.) - `nums = [1, 3, 6], k = 3` → `4` is wrong ([structural] minimum stated as achievability alone. score 4 is attainable by [4,0,3] but not minimal.) -/ namespace PSmallestRangeIi abbrev Input := (List Int) × (Int) abbrev Output := Int /-! ### Specification helpers -/ /-- `ys` arises from `nums` by replacing each entry `x` with either `x + k` or `x - k`. -/ def IsValidModification (nums : List Int) (k : Int) (ys : List Int) : Prop := List.Forall₂ (fun x y => y = x + k ∨ y = x - k) nums ys /-- `s` is the score of `ys`, its greatest element minus its least; the empty list has none. -/ def Score (ys : List Int) (s : Int) : Prop := ∃ mx mn : Int, IsGreatest {y | y ∈ ys} mx ∧ IsLeast {y | y ∈ ys} mn ∧ s = mx - mn /-! ### Validity predicate (V) -/ /-- Valid input: a nonempty list of at most 10000 entries in `[0, 10000]`, with `0 ≤ k ≤ 10000`. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.1.length && input.1.length ≤ 10000 && input.1.all (fun x => 0 ≤ x && x ≤ 10000) && 0 ≤ input.2 && input.2 ≤ 10000 /-! ### Ideal specification (P_spec) -/ /-- `result` is the least score attained by any valid modification of `input.1` by `±input.2`. -/ def minimumScore_spec (input : Input) (result : Output) : Prop := IsLeast {s : Int | ∃ ys : List Int, IsValidModification input.1 input.2 ys ∧ Score ys s} result /-! ### Decidable specification (P_check) -/ /-- The modification selected by one Boolean sign choice per entry. -/ def applySigns (nums : List Int) (k : Int) (signs : Fin nums.length → Bool) : List Int := List.ofFn fun i => if signs i then nums.get i + k else nums.get i - k /-- The score of a nonempty list, with `none` for the empty list. -/ def scoreOf? : List Int → Option Int | [] => none | y :: ys => let h : (y :: ys).toFinset.Nonempty := ⟨y, by simp⟩ some ((y :: ys).toFinset.max' h - (y :: ys).toFinset.min' h) /-- Every Boolean list of a given length, one per sign choice. -/ def signVectors : Nat → List (List Bool) | 0 => [[]] | n + 1 => (signVectors n).map (false :: ·) ++ (signVectors n).map (true :: ·) /-- Executable checker for `minimumScore_spec` over Boolean sign choices. -/ def minimumScore_check (input : Input) (result : Output) : Bool := let n := input.1.length let scores := (signVectors n).filterMap fun bs => if h : bs.length = n then scoreOf? (applySigns input.1 input.2 fun i => bs.get ⟨i.1, h.symm ▸ i.2⟩) else none scores.any (fun s => decide (s = result)) && scores.all (fun s => decide (result ≤ s)) /-- The list of scores the checker enumerates. -/ def scoresList (nums : List Int) (k : Int) : List Int := (signVectors nums.length).filterMap fun bs => if h : bs.length = nums.length then scoreOf? (applySigns nums k fun i => bs.get ⟨i.1, h.symm ▸ i.2⟩) else none theorem check_eq (nums : List Int) (k : Int) (result : Int) : minimumScore_check (nums, k) result = ((scoresList nums k).any (fun s => decide (s = result)) && (scoresList nums k).all (fun s => decide (result ≤ s))) := rfl theorem spec_unfold (nums : List Int) (k : Int) (result : Int) : minimumScore_spec (nums, k) result ↔ ((∃ ys : List Int, IsValidModification nums k ys ∧ Score ys result) ∧ ∀ y : Int, (∃ ys : List Int, IsValidModification nums k ys ∧ Score ys y) → result ≤ y) := Iff.rfl theorem mem_signVectors : ∀ (n : Nat) (bs : List Bool), bs ∈ signVectors n ↔ bs.length = n := by intro n induction n with | zero => intro bs; simp [signVectors] | succ n ih => intro bs simp only [signVectors, List.mem_append, List.mem_map] constructor · rintro (⟨cs, hcs, rfl⟩ | ⟨cs, hcs, rfl⟩) <;> simp [(ih cs).1 hcs] · intro hlen cases bs with | nil => simp at hlen | cons b cs => have hcs : cs ∈ signVectors n := (ih cs).2 (by simpa using hlen) cases b · exact Or.inl ⟨cs, hcs, rfl⟩ · exact Or.inr ⟨cs, hcs, rfl⟩ theorem applySigns_eq_zipWith (nums : List Int) (k : Int) (bs : List Bool) (h : bs.length = nums.length) : applySigns nums k (fun i => bs.get ⟨i.1, h.symm ▸ i.2⟩) = List.zipWith (fun x b => if b then x + k else x - k) nums bs := by apply List.ext_getElem · simp [applySigns, h] · intro i h1 h2 simp [applySigns, List.get_eq_getElem] theorem isValidModification_iff : ∀ (nums ys : List Int) (k : Int), IsValidModification nums k ys ↔ ∃ bs : List Bool, bs.length = nums.length ∧ ys = List.zipWith (fun x b => if b then x + k else x - k) nums bs := by intro nums induction nums with | nil => intro ys k simp only [IsValidModification, List.forall₂_nil_left_iff] constructor · rintro rfl exact ⟨[], rfl, rfl⟩ · rintro ⟨bs, hbl, rfl⟩ simp | cons x xs ih => intro ys k simp only [IsValidModification, List.forall₂_cons_left_iff] constructor · rintro ⟨y, ys', hy, hrest, rfl⟩ obtain ⟨bs, hbl, rfl⟩ := (ih ys' k).1 hrest rcases hy with rfl | rfl · exact ⟨true :: bs, by simp [hbl], by simp⟩ · exact ⟨false :: bs, by simp [hbl], by simp⟩ · rintro ⟨bs, hbl, rfl⟩ cases bs with | nil => simp at hbl | cons b cs => refine ⟨(if b then x + k else x - k), List.zipWith (fun x b => if b then x + k else x - k) xs cs, ?_, (ih _ k).2 ⟨cs, by simpa using hbl, rfl⟩, by simp⟩ cases b <;> simp theorem isGreatest_toFinset_max' (l : List Int) (hne : l.toFinset.Nonempty) : IsGreatest {y : Int | y ∈ l} (l.toFinset.max' hne) := by refine ⟨?_, ?_⟩ · exact List.mem_toFinset.1 (Finset.max'_mem _ hne) · intro y hy exact Finset.le_max' _ y (List.mem_toFinset.2 hy) theorem isLeast_toFinset_min' (l : List Int) (hne : l.toFinset.Nonempty) : IsLeast {y : Int | y ∈ l} (l.toFinset.min' hne) := by refine ⟨?_, ?_⟩ · exact List.mem_toFinset.1 (Finset.min'_mem _ hne) · intro y hy exact Finset.min'_le _ y (List.mem_toFinset.2 hy) theorem scoreOf?_eq_some_iff (ys : List Int) (s : Int) : scoreOf? ys = some s ↔ Score ys s := by cases ys with | nil => simp only [scoreOf?, Score] constructor · intro hc exact absurd hc (by simp) · rintro ⟨mx, mn, hgm, hlm, rfl⟩ have hm := hgm.1 simp at hm | cons y ys => have hne : (y :: ys).toFinset.Nonempty := ⟨y, by simp⟩ have hg := isGreatest_toFinset_max' (y :: ys) hne have hl := isLeast_toFinset_min' (y :: ys) hne simp only [scoreOf?, Score, Option.some.injEq] constructor · intro hs exact ⟨(y :: ys).toFinset.max' hne, (y :: ys).toFinset.min' hne, hg, hl, hs.symm⟩ · rintro ⟨mx, mn, hgm, hlm, rfl⟩ have h1 : mx = (y :: ys).toFinset.max' hne := IsGreatest.unique hgm hg have h2 : mn = (y :: ys).toFinset.min' hne := IsLeast.unique hlm hl subst h1 subst h2 rfl theorem mem_scoresList (nums : List Int) (k s : Int) : s ∈ scoresList nums k ↔ ∃ ys : List Int, IsValidModification nums k ys ∧ Score ys s := by unfold scoresList rw [List.mem_filterMap] constructor · rintro ⟨bs, hbs, hval⟩ have hlen : bs.length = nums.length := (mem_signVectors _ _).1 hbs rw [dif_pos hlen] at hval refine ⟨List.zipWith (fun x b => if b then x + k else x - k) nums bs, ?_, ?_⟩ · exact (isValidModification_iff nums _ k).2 ⟨bs, hlen, rfl⟩ · rw [← applySigns_eq_zipWith nums k bs hlen] exact (scoreOf?_eq_some_iff _ _).1 hval · rintro ⟨ys, hvalid, hscore⟩ obtain ⟨bs, hlen, rfl⟩ := (isValidModification_iff nums ys k).1 hvalid refine ⟨bs, (mem_signVectors _ _).2 hlen, ?_⟩ rw [dif_pos hlen, applySigns_eq_zipWith nums k bs hlen] exact (scoreOf?_eq_some_iff _ _).2 hscore /-- On valid input the checker accepts exactly the specified outputs. -/ theorem minimumScore_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : minimumScore_check input result ↔ minimumScore_spec input result := by obtain ⟨nums, k⟩ := input rw [check_eq, Bool.and_eq_true, List.any_eq_true, List.all_eq_true, spec_unfold] constructor · rintro ⟨⟨s, hmem, hs⟩, hall⟩ have hs' : s = result := by simpa using hs subst hs' refine ⟨(mem_scoresList nums k s).1 hmem, ?_⟩ intro y hy have hy2 := hall y ((mem_scoresList nums k y).2 hy) simpa using hy2 · rintro ⟨hmem, hlb⟩ refine ⟨⟨result, (mem_scoresList nums k result).2 hmem, by simp⟩, ?_⟩ intro y hy have hy2 := hlb y ((mem_scoresList nums k y).1 hy) simpa using hy2 /-! ### Implementation helpers -/ /-- The score of the modification that raises `arr[0..i]` by `k` and lowers `arr[i+1..]` by `k`. -/ def splitCandidate (arr : Array Int) (k : Int) (i : Nat) : Int := max (arr[i]! + k) (arr[arr.size - 1]! - k) - min (arr[0]! + k) (arr[i + 1]! - k) /-- The minimum of `best` and every split candidate of the sorted array. -/ def scanSplits (arr : Array Int) (k : Int) (best : Int) : Int := (List.range (arr.size - 1)).foldl (fun b i => min b (splitCandidate arr k i)) best /-! ### Main algorithm (impl) -/ /-- Minimum score by sorting and scanning the split positions of the sorted array. -/ def smallestRangeII (input : Input) : Output := let arr := (input.1.mergeSort (fun a b : Int => decide (a ≤ b))).toArray if arr.size = 0 then 0 else scanSplits arr input.2 (arr[arr.size - 1]! - arr[0]!) /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem smallestRangeII_correct (input : Input) (h : isValidInput input) : minimumScore_spec input (smallestRangeII input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ([1], 0) #guard isValidInput ([0, 10], 2) #guard isValidInput ([1, 3, 6], 3) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ([], 0)) #guard !(isValidInput ([(-1)], 0)) #guard !(isValidInput ([10001], 0)) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard minimumScore_check ([1], 0) 0 #guard minimumScore_check ([0, 10], 2) 6 #guard minimumScore_check ([1, 3, 6], 3) 3 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(minimumScore_check ([1], 0) (-1)) #guard !(minimumScore_check ([0, 10], 2) 10) #guard !(minimumScore_check ([1, 3, 6], 3) 4) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard smallestRangeII ([1], 0) == 0 #guard smallestRangeII ([0, 10], 2) == 6 #guard smallestRangeII ([1, 3, 6], 3) == 3 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard minimumScore_check ([1], 0) (smallestRangeII ([1], 0)) #guard minimumScore_check ([0, 10], 2) (smallestRangeII ([0, 10], 2)) #guard minimumScore_check ([1, 3, 6], 3) (smallestRangeII ([1, 3, 6], 3)) end PSmallestRangeIi