import Mathlib /-! # 3Sum With Multiplicity Given an integer array arr, and an integer target, return the number of tuples i, j, k such that i < j < k and arr[i] + arr[j] + arr[k] == target. As the answer can be very large, return it modulo 10^9 + 7. ## Constraints - 3 <= arr.length <= 3000 - 0 <= arr[i] <= 100 - 0 <= target <= 300 ## Provided examples - `arr = [1, 1, 2, 2, 3, 3, 4, 4, 5, 5], target = 8` → `20` - `arr = [1, 1, 2, 2, 2, 2], target = 5` → `12` - `arr = [2, 1, 3], target = 6` → `1` ## Synthesized negative examples - invalid input: `arr = [0, 0], target = 0` ([structural] a predicate that admits 3 <= arr.length <= 3000. one below the length floor; a predicate that only checks elements accepts it.) - invalid input: `arr = [-1, 0, 0], target = 0` ([structural] a predicate that admits 0 <= arr[i] <= 100. negative element; a predicate that only checks arr length and target accepts it.) - invalid input: `arr = [101, 0, 0], target = 0` ([structural] a predicate that admits 0 <= arr[i] <= 100. one past the element ceiling; catches predicates that forget the upper bound.) - `arr = [1, 1, 2, 2, 3, 3, 4, 4, 5, 5], target = 8` → `19` is wrong ([structural] off-by-one in counting loop. one fewer than the correct count) - `arr = [1, 1, 2, 2, 2, 2], target = 5` → `0` is wrong ([structural] no correctness condition requires the answer to equal the true count. zero satisfies a spec without a soundness clause) - `arr = [2, 1, 3], target = 6` → `2` is wrong ([structural] Not an optimization; off-by-one in inner loop counts an extra ordering. true count plus one from an extra ordering) -/ namespace P3sumWithMultiplicity abbrev Input := (List Int) × (Nat) abbrev Output := Nat /-! ### Specification helpers -/ /-- Indices `i < j < k` below `arr.length` whose entries sum to `target`. -/ def IsSumTriple (arr : List Int) (target : Nat) (i j k : Nat) : Prop := i < j ∧ j < k ∧ k < arr.length ∧ arr[i]! + arr[j]! + arr[k]! = (target : Int) /-! ### Validity predicate (V) -/ /-- Valid input: `arr` has 3 to 3000 elements, each in `[0, 100]`, and `target ≤ 300`. -/ def isValidInput (input : Input) : Bool := 3 ≤ input.1.length && input.1.length ≤ 3000 && input.1.all (fun x => decide (0 ≤ x ∧ x ≤ 100)) && input.2 ≤ 300 /-! ### Ideal specification (P_spec) -/ /-- `result` is the count, reduced modulo 1,000,000,007, of the index triples satisfying `IsSumTriple`, certified by a finite collection with exactly those members. -/ def countThreeSumMulti_spec (input : Input) (result : Output) : Prop := ∃ S : Finset (Nat × Nat × Nat), (S.card ≡ result [MOD 1000000007] ∧ result < 1000000007) ∧ ∀ t : Nat × Nat × Nat, t ∈ S ↔ IsSumTriple input.1 input.2 t.1 t.2.1 t.2.2 /-! ### Decidable specification (P_check) -/ /-- Decides the certificate-finset existential by replacing it with the unique filtered cube of in-range index triples, whose cardinality is computable. -/ instance (input : Input) (result : Output) : Decidable (∃ S : Finset (Nat × Nat × Nat), (S.card ≡ result [MOD 1000000007] ∧ result < 1000000007) ∧ ∀ t : Nat × Nat × Nat, t ∈ S ↔ IsSumTriple input.1 input.2 t.1 t.2.1 t.2.2) := let n := input.1.length let T : Finset (Nat × Nat × Nat) := (Finset.range n ×ˢ Finset.range n ×ˢ Finset.range n).filter (fun t : Nat × Nat × Nat => t.1 < t.2.1 ∧ t.2.1 < t.2.2 ∧ t.2.2 < n ∧ input.1[t.1]! + input.1[t.2.1]! + input.1[t.2.2]! = (input.2 : Int)) have hmem : ∀ t : Nat × Nat × Nat, t ∈ T ↔ IsSumTriple input.1 input.2 t.1 t.2.1 t.2.2 := by rintro ⟨i, j, k⟩ simp only [T, Finset.mem_filter, Finset.mem_product, Finset.mem_range, IsSumTriple, n] constructor · rintro ⟨⟨hi, hj, hk⟩, hij, hjk, -, hsum⟩ exact ⟨hij, hjk, hk, hsum⟩ · rintro ⟨hij, hjk, hk, hsum⟩ exact ⟨⟨lt_trans hij (lt_trans hjk hk), lt_trans hjk hk, hk⟩, hij, hjk, hk, hsum⟩ decidable_of_iff (T.card ≡ result [MOD 1000000007] ∧ result < 1000000007) (by constructor · rintro ⟨hcard, hlt⟩ exact ⟨T, ⟨hcard, hlt⟩, hmem⟩ · rintro ⟨S, ⟨hcard, hlt⟩, hS⟩ have hST : S = T := Finset.ext fun t => (hS t).trans (hmem t).symm exact ⟨hST ▸ hcard, hlt⟩) /-- Executable checker obtained mechanically from the specification. -/ def countThreeSumMulti_check (input : Input) (result : Output) : Bool := @decide (countThreeSumMulti_spec input result) (by unfold countThreeSumMulti_spec; infer_instance) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem countThreeSumMulti_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : countThreeSumMulti_check input result ↔ countThreeSumMulti_spec input result := by simp [countThreeSumMulti_check] /-! ### Implementation helpers -/ /-- The counts with the entry for `v` increased by one, unchanged when `v` is outside `0..100`. -/ def incrementCount (counts : Array Nat) (v : Int) : Array Nat := if 0 ≤ v ∧ v ≤ 100 then let i := v.toNat counts.set! i (counts[i]! + 1) else counts /-- The counts with the entry for `v` decreased by one, unchanged when `v` is outside `0..100`. -/ def decrementCount (counts : Array Nat) (v : Int) : Array Nat := if 0 ≤ v ∧ v ≤ 100 then let i := v.toNat counts.set! i (counts[i]! - 1) else counts /-- Occurrence counts of each value in `0..100` within `xs`, as a 101-entry array. -/ def valueCounts (xs : List Int) : Array Nat := xs.foldl (fun counts v => incrementCount counts v) (List.replicate 101 0).toArray /-- Number of pairs `(i, k)` with `i` before and `k` after a middle entry of value `v` whose values sum to `target - v`, read from prefix and suffix value counts. -/ def pairCountAtMiddle (target : Nat) (v : Int) (pre suf : Array Nat) : Nat := if 0 ≤ v ∧ v ≤ (target : Int) then let needed := target - v.toNat Finset.sum (Finset.range 101) fun x => if x ≤ needed ∧ needed - x ≤ 100 then pre[x]! * suf[needed - x]! else 0 else 0 /-- Folds over the remaining list treating each entry as the middle index: drop it from the suffix counts, add the pairs it completes modulo 1,000,000,007, then add it to the prefix counts. -/ def scanMiddleIndices (target : Nat) (pre suf : Array Nat) (rest : List Int) (acc : Nat) : Nat := match rest with | [] => acc | v :: vs => let suffix' := decrementCount suf v let add := pairCountAtMiddle target v pre suffix' let acc' := (acc + add) % 1000000007 scanMiddleIndices target (incrementCount pre v) suffix' vs acc' /-! ### Main algorithm (impl) -/ /-- Counts increasing index triples summing to `target` by a left-to-right scan with prefix/suffix value counts, accumulating modulo 1,000,000,007. -/ def countThreeSumMultiImpl (input : Input) : Output := scanMiddleIndices input.2 (List.replicate 101 0).toArray (valueCounts input.1) input.1 0 /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem countThreeSumMultiImpl_correct (input : Input) (h : isValidInput input) : countThreeSumMulti_spec input (countThreeSumMultiImpl input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ([1, 1, 2, 2, 3, 3, 4, 4, 5, 5], 8) #guard isValidInput ([1, 1, 2, 2, 2, 2], 5) #guard isValidInput ([2, 1, 3], 6) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ([0, 0], 0)) #guard !(isValidInput ([(-1), 0, 0], 0)) #guard !(isValidInput ([101, 0, 0], 0)) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard countThreeSumMulti_check ([1, 1, 2, 2, 3, 3, 4, 4, 5, 5], 8) 20 #guard countThreeSumMulti_check ([1, 1, 2, 2, 2, 2], 5) 12 #guard countThreeSumMulti_check ([2, 1, 3], 6) 1 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(countThreeSumMulti_check ([1, 1, 2, 2, 3, 3, 4, 4, 5, 5], 8) 19) #guard !(countThreeSumMulti_check ([1, 1, 2, 2, 2, 2], 5) 0) #guard !(countThreeSumMulti_check ([2, 1, 3], 6) 2) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard countThreeSumMultiImpl ([1, 1, 2, 2, 3, 3, 4, 4, 5, 5], 8) == 20 #guard countThreeSumMultiImpl ([1, 1, 2, 2, 2, 2], 5) == 12 #guard countThreeSumMultiImpl ([2, 1, 3], 6) == 1 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard countThreeSumMulti_check ([1, 1, 2, 2, 3, 3, 4, 4, 5, 5], 8) (countThreeSumMultiImpl ([1, 1, 2, 2, 3, 3, 4, 4, 5, 5], 8)) #guard countThreeSumMulti_check ([1, 1, 2, 2, 2, 2], 5) (countThreeSumMultiImpl ([1, 1, 2, 2, 2, 2], 5)) #guard countThreeSumMulti_check ([2, 1, 3], 6) (countThreeSumMultiImpl ([2, 1, 3], 6)) end P3sumWithMultiplicity