import Mathlib /-! # Arithmetic Slices Ii Subsequence Given an integer array nums, return the number of all the arithmetic subsequences of nums. A sequence of numbers is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same. For example, [1, 3, 5, 7, 9], [7, 7, 7, 7], and [3, -1, -5, -9] are arithmetic sequences. For example, [1, 1, 2, 5, 7] is not an arithmetic sequence. A subsequence of an array is a sequence that can be formed by removing some elements (possibly none) of the array. For example, [2,5,10] is a subsequence of [1,2,1,2,4,1,5,10]. The test cases are generated so that the answer fits in 32-bit integer. ## Constraints - 1 <= nums.length <= 1000 - -2^31 <= nums[i] <= 2^31 - 1 ## Provided examples - `nums = [2, 4, 6, 8, 10]` → `7` - `nums = [7, 7, 7, 7, 7]` → `16` - `nums = [1]` → `0` ## Synthesized negative examples - invalid input: `nums = []` ([structural] a predicate that admits 1 <= nums.length <= 1000. catches a predicate that forgets the length floor) - invalid input: `nums = [-2147483649]` ([structural] a predicate that admits -2^31 <= nums[i] <= 2^31 - 1. one below the stated minimum; catches a predicate checking only the upper bound) - invalid input: `nums = [2147483648]` ([structural] a predicate that admits -2^31 <= nums[i] <= 2^31 - 1. one above the stated maximum; catches a predicate checking only the lower bound) - `nums = [2, 4, 6, 8, 10]` → `6` is wrong ([structural] upper length bound stops one short of the array length. drops the full-length arithmetic subsequence) - `nums = [7, 7, 7, 7, 7]` → `15` is wrong ([structural] proper subsequence only, dropping the possibly none allowance. excludes the full-length subsequence, one less) - `nums = [1]` → `2` is wrong ([structural] Drops the at-least-three element requirement and counts empty subsequence as arithmetic. Counts [] and [1]; both pass the relaxed length check) -/ namespace PArithmeticSlicesIiSubsequence abbrev Input := List Int abbrev Output := Nat /-! ### Specification helpers -/ /-- `idx` picks out an arithmetic subsequence of `nums`: strictly increasing in-bounds indices, at least three of them, with all consecutive differences equal. -/ def IsArithmeticSubsequence (nums : List Int) (idx : List Nat) : Prop := 3 ≤ idx.length ∧ idx.Chain' (· < ·) ∧ (∀ i ∈ idx, i < nums.length) ∧ ∃ d : Int, idx.Chain' (fun i j => nums[j]! - nums[i]! = d) /-! ### Validity predicate (V) -/ /-- Valid input: a nonempty list of at most 1000 signed 32-bit integers. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.length && input.length ≤ 1000 && input.all (fun x => -2147483648 ≤ x && x ≤ 2147483647) /-! ### Ideal specification (P_spec) -/ /-- `result` counts the arithmetic subsequences of `input`: some finite collection of index lists has size `result` and contains an index list exactly when it is an arithmetic subsequence of `input`. -/ def countArithmeticSubsequences_spec (input : Input) (result : Output) : Prop := ∃ s : Finset (List Nat), s.card = result ∧ ∀ idx : List Nat, idx ∈ s ↔ IsArithmeticSubsequence input idx /-! ### Decidable specification (P_check) -/ /-- The common difference forced by the first two selected indices, with a default for shorter lists. -/ def forcedDifference (input : Input) (idx : List Nat) : Int := match idx with | i :: j :: _ => input[j]! - input[i]! | _ => 0 /-- Boolean test that an index list is strictly increasing. -/ def strictlyIncreasing : List Nat → Bool | [] => true | [_] => true | i :: j :: rest => i < j && strictlyIncreasing (j :: rest) /-- Boolean test that the consecutive differences of `input` along the index list are all equal to `d`. -/ def constantDifferences (input : Input) (d : Int) : List Nat → Bool | [] => true | [_] => true | i :: j :: rest => input[j]! - input[i]! = d && constantDifferences input d (j :: rest) /-- Decidable form of `IsArithmeticSubsequence`, using the difference forced by the first two indices. -/ def arithmeticSubsequenceB (input : Input) (idx : List Nat) : Bool := 3 ≤ idx.length && strictlyIncreasing idx && idx.all (· < input.length) && constantDifferences input (forcedDifference input idx) idx /-- Every strictly increasing in-bounds index list, encoded as a sublist of the index range. -/ def indexTuples (input : Input) : List (List Nat) := (List.range input.length).sublists /-- The finite collection of arithmetic index subsequences of `input`. -/ def arithmeticSubsequences (input : Input) : Finset (List Nat) := ((indexTuples input).filter (arithmeticSubsequenceB input)).toFinset /-- Executable checker for `countArithmeticSubsequences_spec`. -/ def countArithmeticSubsequences_check (input : Input) (result : Output) : Bool := decide ((arithmeticSubsequences input).card = result) theorem strictlyIncreasing_eq_true_iff (idx : List Nat) : strictlyIncreasing idx = true ↔ idx.Chain' (· < ·) := by induction idx with | nil => constructor · intro _; exact .nil · intro _; rfl | cons i tail ih => cases tail with | nil => constructor · intro _; exact .singleton i · intro _; rfl | cons j rest => rw [strictlyIncreasing, Bool.and_eq_true, decide_eq_true_eq] constructor · rintro ⟨hij, htail⟩ exact .cons_cons hij (ih.mp htail) · intro h exact ⟨(List.isChain_cons_cons.mp h).1, ih.mpr (List.isChain_cons_cons.mp h).2⟩ theorem constantDifferences_eq_true_iff (input : Input) (d : Int) (idx : List Nat) : constantDifferences input d idx = true ↔ idx.Chain' (fun i j => input[j]! - input[i]! = d) := by induction idx with | nil => constructor · intro _; exact .nil · intro _; rfl | cons i tail ih => cases tail with | nil => constructor · intro _; exact .singleton i · intro _; rfl | cons j rest => rw [constantDifferences, Bool.and_eq_true, decide_eq_true_eq] constructor · rintro ⟨hij, htail⟩ exact .cons_cons hij (ih.mp htail) · intro h exact ⟨(List.isChain_cons_cons.mp h).1, ih.mpr (List.isChain_cons_cons.mp h).2⟩ theorem forcedDifference_eq_of_chain (input : Input) (idx : List Nat) (d : Int) (hlen : 2 ≤ idx.length) (hchain : idx.Chain' (fun i j => input[j]! - input[i]! = d)) : forcedDifference input idx = d := by cases idx with | nil => simp at hlen | cons i tail => cases tail with | nil => simp at hlen | cons j rest => simpa [forcedDifference] using (List.isChain_cons_cons.mp hchain).1 theorem arithmeticSubsequenceB_eq_true_iff (input : Input) (idx : List Nat) : arithmeticSubsequenceB input idx = true ↔ IsArithmeticSubsequence input idx := by unfold arithmeticSubsequenceB IsArithmeticSubsequence simp only [Bool.and_eq_true, decide_eq_true_eq, strictlyIncreasing_eq_true_iff, List.all_eq_true, constantDifferences_eq_true_iff] constructor · rintro ⟨⟨⟨hlen, hinc⟩, hbnd⟩, hdiff⟩ exact ⟨hlen, hinc, hbnd, ⟨forcedDifference input idx, hdiff⟩⟩ · rintro ⟨hlen, hinc, hbnd, d, hdiff⟩ have hforced : forcedDifference input idx = d := forcedDifference_eq_of_chain input idx d (by omega) hdiff refine ⟨⟨⟨hlen, hinc⟩, hbnd⟩, ?_⟩ simpa [hforced] using hdiff theorem chain_lt_sublist_range {idx : List Nat} {n : Nat} (hc : idx.Chain' (· < ·)) (hb : ∀ i ∈ idx, i < n) : idx.Sublist (List.range n) := by unfold List.Chain' at hc rw [List.isChain_iff_pairwise] at hc apply List.sublist_of_subperm_of_pairwise (List.subperm_of_subset hc.nodup ?_) hc List.pairwise_lt_range intro i hi simpa only [List.mem_range] using hb i hi theorem wx_count_of_mem (input : Input) (result : Output) (bridge : ∀ idx : List Nat, idx ∈ arithmeticSubsequences input ↔ IsArithmeticSubsequence input idx) : countArithmeticSubsequences_check input result ↔ countArithmeticSubsequences_spec input result := by simp only [countArithmeticSubsequences_check, decide_eq_true_eq, countArithmeticSubsequences_spec] constructor · intro hc exact ⟨arithmeticSubsequences input, hc, bridge⟩ · rintro ⟨s, hs, hm⟩ have heq : s = arithmeticSubsequences input := by ext idx exact (hm idx).trans (bridge idx).symm simpa only [heq] using hs /-- On valid input the checker accepts exactly the specified outputs. -/ theorem countArithmeticSubsequences_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : countArithmeticSubsequences_check input result ↔ countArithmeticSubsequences_spec input result := by apply wx_count_of_mem intro idx simp only [arithmeticSubsequences, List.mem_toFinset, List.mem_filter, indexTuples, List.mem_sublists, arithmeticSubsequenceB_eq_true_iff] constructor · exact And.right · intro hi exact ⟨chain_lt_sublist_range hi.2.1 hi.2.2.1, hi⟩ /-! ### Implementation helpers -/ /-- Scan previous indices before `i`, adding extensions to the answer and to `i`'s difference table. -/ def visitPrevious (input : Input) (maps : Array (Std.HashMap Int Nat)) (i : Nat) (js : List Nat) (ans : Nat) (mi : Std.HashMap Int Nat) : Nat × Std.HashMap Int Nat := match js with | [] => (ans, mi) | j :: js => let d := forcedDifference input [j, i] let cnt := (Std.HashMap.get? (maps[j]!) d).getD 0 let here := (Std.HashMap.get? mi d).getD 0 visitPrevious input maps i js (ans + cnt) (Std.HashMap.insert mi d (here + cnt + 1)) /-- Process last indices in order, carrying the per-index difference tables and the running count. -/ def processIndices (input : Input) (is_ : List Nat) (maps : Array (Std.HashMap Int Nat)) (ans : Nat) : Nat := match is_ with | [] => ans | i :: is_ => let step := visitPrevious input maps i (List.range i) ans (∅ : Std.HashMap Int Nat) processIndices input is_ (maps.set! i step.2) step.1 /-! ### Main algorithm (impl) -/ /-- Count arithmetic subsequences by pair-index dynamic programming over common differences. -/ def numberOfArithmeticSlices (input : Input) : Output := let n := input.length let maps0 := (List.replicate n (∅ : Std.HashMap Int Nat)).toArray processIndices input (List.range n) maps0 0 /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem numberOfArithmeticSlices_correct (input : Input) (h : isValidInput input) : countArithmeticSubsequences_spec input (numberOfArithmeticSlices input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput [2, 4, 6, 8, 10] #guard isValidInput [7, 7, 7, 7, 7] #guard isValidInput [1] /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput []) #guard !(isValidInput [(-2147483649)]) #guard !(isValidInput [2147483648]) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard countArithmeticSubsequences_check [2, 4, 6, 8, 10] 7 #guard countArithmeticSubsequences_check [7, 7, 7, 7, 7] 16 #guard countArithmeticSubsequences_check [1] 0 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(countArithmeticSubsequences_check [2, 4, 6, 8, 10] 6) #guard !(countArithmeticSubsequences_check [7, 7, 7, 7, 7] 15) #guard !(countArithmeticSubsequences_check [1] 2) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard numberOfArithmeticSlices [2, 4, 6, 8, 10] == 7 #guard numberOfArithmeticSlices [7, 7, 7, 7, 7] == 16 #guard numberOfArithmeticSlices [1] == 0 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard countArithmeticSubsequences_check [2, 4, 6, 8, 10] (numberOfArithmeticSlices [2, 4, 6, 8, 10]) #guard countArithmeticSubsequences_check [7, 7, 7, 7, 7] (numberOfArithmeticSlices [7, 7, 7, 7, 7]) #guard countArithmeticSubsequences_check [1] (numberOfArithmeticSlices [1]) end PArithmeticSlicesIiSubsequence