import Mathlib /-! # Profitable Schemes There is a group of n members, and a list of various crimes they could commit. The ith crime generates a profit[i] and requires group[i] members to participate in it. If a member participates in one crime, that member can't participate in another crime. Let's call a profitable scheme any subset of these crimes that generates at least minProfit profit, and the total number of members participating in that subset of crimes is at most n. Return the number of schemes that can be chosen. Since the answer may be very large, return it modulo 10^9 + 7. ## Constraints - 1 <= n <= 100 - 0 <= minProfit <= 100 - 1 <= group.length <= 100 - 1 <= group[i] <= 100 - profit.length == group.length - 0 <= profit[i] <= 100 ## Provided examples - `n = 5, minProfit = 3, group = [2, 2], profit = [2, 3]` → `2` - `n = 10, minProfit = 5, group = [2, 3, 5], profit = [6, 7, 8]` → `7` - `n = 4, minProfit = 4, group = [4], profit = [5]` → `1` ## Synthesized negative examples - invalid input: `n = 0, minProfit = 0, group = [1], profit = [0]` ([structural] a predicate that admits 1 <= n <= 100. one below the stated minimum n) - invalid input: `n = 5, minProfit = 0, group = [], profit = []` ([structural] a predicate that admits 1 <= group.length <= 100. empty group where at least one crime is required) - invalid input: `n = 5, minProfit = 0, group = [1], profit = [0, 0]` ([structural] a predicate that admits profit.length == group.length. profit list longer than group; checking either list alone accepts) - `n = 5, minProfit = 3, group = [2, 2], profit = [2, 3]` → `3` is wrong ([structural] minProfit threshold is one too low. three schemes have profit at least 2, only two at least 3) - `n = 10, minProfit = 5, group = [2, 3, 5], profit = [6, 7, 8]` → `6` is wrong ([structural] member-capacity bound is off by one, excluding the subset using exactly n members. Counts all valid schemes except the full subset using all 10 members.) - `n = 4, minProfit = 4, group = [4], profit = [5]` → `2` is wrong ([structural] dropping the minProfit requirement. empty scheme and the one crime both count) -/ namespace PProfitableSchemes abbrev Input := (Nat) × (Nat) × (List Nat) × (List Nat) abbrev Output := Nat /-! ### Specification helpers -/ /-- A scheme is valid when its total required members is at most `n` and its total profit is at least `minProfit`. -/ def IsValidScheme (group profit : List Nat) (n minProfit : Nat) (scheme : Finset (Fin group.length)) : Prop := scheme.sum (fun i => group.get i) ≤ n ∧ minProfit ≤ scheme.sum (fun i => profit.getD i.val 0) /-! ### Validity predicate (V) -/ /-- Valid input: `1 ≤ n ≤ 100`, `minProfit ≤ 100`, nonempty group of length at most 100, profit of the same length, every group entry in `[1, 100]` and every profit entry at most 100. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.1 && input.1 ≤ 100 && input.2.1 ≤ 100 && 1 ≤ input.2.2.1.length && input.2.2.1.length ≤ 100 && input.2.2.2.length == input.2.2.1.length && input.2.2.1.all (fun g => 1 ≤ g && g ≤ 100) && input.2.2.2.all (fun p => p ≤ 100) /-! ### Ideal specification (P_spec) -/ /-- `result` is the unique number below 10^9+7 congruent to the cardinality of some finite collection `C` of schemes that contains exactly the valid ones. -/ def numberOfProfitableSchemes_spec (input : Input) (result : Output) : Prop := match input with | (n, minProfit, group, profit) => result < 1000000007 ∧ ∃ C : Finset (Finset (Fin group.length)), C.card ≡ result [MOD 1000000007] ∧ ∀ scheme : Finset (Fin group.length), scheme ∈ C ↔ IsValidScheme group profit n minProfit scheme /-! ### Decidable specification (P_check) -/ /-- Decides the whole specification after `unfold` turns it into a `match` on `input`: the tuple is destructured and the body is decided in the arithmetic form it unfolds to — `C.card ≡ result [MOD 1000000007]` as the defining equality `C.card % 1000000007 = result % 1000000007`, and `IsValidScheme` as the conjunction of the two `Nat` comparisons — while the `∃ C` and `∀ scheme` range over the fintypes `Finset (Finset (Fin _))` and `Finset (Fin _)`, which Lean decides by enumeration. -/ instance decNumberOfProfitableSchemesSpec (input : Input) (result : Output) : Decidable (match input with | (n, minProfit, group, profit) => result < 1000000007 ∧ ∃ C : Finset (Finset (Fin group.length)), C.card ≡ result [MOD 1000000007] ∧ ∀ scheme : Finset (Fin group.length), scheme ∈ C ↔ IsValidScheme group profit n minProfit scheme) := match input with | (n, minProfit, group, profit) => inferInstanceAs (Decidable (result < 1000000007 ∧ ∃ C : Finset (Finset (Fin group.length)), C.card % 1000000007 = result % 1000000007 ∧ ∀ scheme : Finset (Fin group.length), scheme ∈ C ↔ (scheme.sum (fun i => group.get i) ≤ n ∧ minProfit ≤ scheme.sum (fun i => profit.getD i.val 0)))) /-- Executable checker obtained mechanically from the specification. -/ def numberOfProfitableSchemes_check (input : Input) (result : Output) : Bool := @decide (numberOfProfitableSchemes_spec input result) (by unfold numberOfProfitableSchemes_spec; infer_instance) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem numberOfProfitableSchemes_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : numberOfProfitableSchemes_check input result ↔ numberOfProfitableSchemes_spec input result := by simp [numberOfProfitableSchemes_check] /-! ### Implementation helpers -/ /-- Initial `(n+1) × (minProfit+1)` table of zero counts with the empty scheme counted once at `(0, 0)`. -/ def dpTable (n minProfit : Nat) : Array (Array Nat) := let t := Array.replicate (n + 1) (Array.replicate (minProfit + 1) 0) t.set! 0 ((t[0]!).set! 0 1) /-- One crime folded into the table: every prior state gains the option of taking this crime, capped at the profit threshold. -/ def applyCrime (dp : Array (Array Nat)) (n minProfit g p : Nat) : Array (Array Nat) := ((List.range (n + 1)).reverse.filter (fun j => g ≤ j)).foldl (fun acc j => ((List.range (minProfit + 1)).reverse).foldl (fun acc2 k => let cnt := (dp[j - g]!).getD k 0 let k' := Nat.min minProfit (k + p) let row := acc2[j]! acc2.set! j (row.set! k' ((row[k']! + cnt) % 1000000007))) acc) dp /-- Sum over all member counts of the entries whose capped profit reached the threshold, modulo 10^9+7. -/ def sumFinalColumn (dp : Array (Array Nat)) (n minProfit : Nat) : Nat := (List.range (n + 1)).foldl (fun acc j => (acc + (dp[j]!).getD minProfit 0) % 1000000007) 0 /-! ### Main algorithm (impl) -/ /-- Count profitable schemes by knapsack-style DP over the crimes with profit capped at `minProfit`. -/ def countProfitableSchemes (input : Input) : Output := match input with | (n, minProfit, group, profit) => let dp := (group.zip profit).foldl (fun acc (g, p) => applyCrime acc n minProfit g p) (dpTable n minProfit) sumFinalColumn dp n minProfit /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem countProfitableSchemes_correct (input : Input) (h : isValidInput input) : numberOfProfitableSchemes_spec input (countProfitableSchemes input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput (5, 3, [2, 2], [2, 3]) #guard isValidInput (10, 5, [2, 3, 5], [6, 7, 8]) #guard isValidInput (4, 4, [4], [5]) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput (0, 0, [1], [0])) #guard !(isValidInput (5, 0, [], [])) #guard !(isValidInput (5, 0, [1], [0, 0])) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard numberOfProfitableSchemes_check (5, 3, [2, 2], [2, 3]) 2 #guard numberOfProfitableSchemes_check (10, 5, [2, 3, 5], [6, 7, 8]) 7 #guard numberOfProfitableSchemes_check (4, 4, [4], [5]) 1 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(numberOfProfitableSchemes_check (5, 3, [2, 2], [2, 3]) 3) #guard !(numberOfProfitableSchemes_check (10, 5, [2, 3, 5], [6, 7, 8]) 6) #guard !(numberOfProfitableSchemes_check (4, 4, [4], [5]) 2) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard countProfitableSchemes (5, 3, [2, 2], [2, 3]) == 2 #guard countProfitableSchemes (10, 5, [2, 3, 5], [6, 7, 8]) == 7 #guard countProfitableSchemes (4, 4, [4], [5]) == 1 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard numberOfProfitableSchemes_check (5, 3, [2, 2], [2, 3]) (countProfitableSchemes (5, 3, [2, 2], [2, 3])) #guard numberOfProfitableSchemes_check (10, 5, [2, 3, 5], [6, 7, 8]) (countProfitableSchemes (10, 5, [2, 3, 5], [6, 7, 8])) #guard numberOfProfitableSchemes_check (4, 4, [4], [5]) (countProfitableSchemes (4, 4, [4], [5])) end PProfitableSchemes