← 返回编程题库
coding-min-contracts-cover-greek-buckets中等免费版2000ms未尝试

用位掩码 BFS 求覆盖希腊字母 bucket 的最少合约数

Min Contracts to Cover Greek Buckets via Bitmask BFS

开始编码

实现 solution(B, target_mask, contract_masks) -> int。先看例子:取 B = 4target_mask = 15(二进制为 0b1111),合约列表 [12, 3, 5, 10](二进制为 0b1100, 0b0011, 0b0101, 0b1010),挑选下标 0 和 1 的合约可以得到 0b1100 | 0b0011 = 0b1111,2 条合约就能覆盖全部 4 个 bucket,而这就是最小值,所以 solution(4, 15, [12, 3, 5, 10]) 返回 2

总体描述:B 是 greek/exposure bucket 的总数,编号从 bit 零到 bit B - 1target_mask 中 bit i 为 1 表示 bucket i 必须被覆盖;contract_masks 是一个长度为 N 的列表,每个元素是 [0, 2**B - 1] 范围内的位掩码,标记该合约会触及哪些 bucket。返回最少使用多少条合约才能让选中合约的按位或覆盖 target_mask 中所有需要的 bucket;若不存在任何子集可以做到,返回 -1

每一次"选取"都从列表里消耗一个槽位,因此即便多条合约的掩码相同,它们仍然是各自独立的项;但当目标是最小化条数时,重复的掩码并不能帮你选得更少——每种相异的掩码留一份就够了。

边界约定:target_mask == 0 表示"无需覆盖",无论列表内容如何都返回 0;当列表为空且 target_mask > 0,或者所有合约掩码与 target_mask 求与之后都为 0 时,返回 -1target_mask 之外的比特对覆盖判定没有影响。

复杂度目标为 O(N * 2^B) 时间与 O(2^B) 空间——以状态 0 为起点在已覆盖联合的格上做 BFS,转移是 state | contract_masks[k],答案就是首次满足 (state & target_mask) == target_mask 的 BFS 深度。

实现细节由 stubs/stub.py 提供。

实践背景

一个做波动率的交易桌通常会把账本分解到少量的 greek/exposure bucket 上——比如短端 delta、长端 delta、近行权 vega、远行权 vega——并维护一个标准化对冲合约目录,每条合约打上"它实际会移动哪些 bucket"的标签。当桌面要平掉一组暴露时,运营层面的问题就是"最少用几条合约把我需要抹掉的 bucket 都覆盖到"——这与名义额度的背包问题不同,因为这里的目标函数是条数(操作复杂度、下单笔数、审计痕迹),而不是名义金额。位掩码 BFS 正好契合这一形态:每条合约是一个表示"它触及哪些 bucket"的位掩码,可达联合态的格在 B 较小(B <= 12 已经足以覆盖任何现实的 bucket 划分)时最多 2^B 个状态,覆盖目标 bucket 集合所需的最少合约数恰好是从状态 0 到任意满足 (state AND target_mask) == target_mask 的状态的 BFS 深度。

约束条件

  • 1 <= B <= 12,因此状态空间最多 2^B = 4096 个
  • 0 <= N <= 200,其中 N 为 contract_masks 的长度(空列表且 target_mask > 0 时返回 -1)
  • 每个 contract_masks[k] 是 [0, 2^B - 1] 区间内的整数
  • target_mask 是 [0, 2^B - 1] 区间内的整数;target_mask == 0 时返回 0
  • 若任何子集都无法覆盖 target_mask,返回 -1

样例

Case 1 · statement-example: B=4 covered by two contracts

输入: [4,15,[12,3,5,10]]

期望: 2

选取下标 0 和 1:0b1100 | 0b0011 = 0b1111,恰好覆盖全部 4 个 bucket,最少 2 条。

Case 2 · visible: target_mask 0 returns 0

输入: [3,0,[1,2,4]]

期望: 0

target_mask = 0 表示无需覆盖,直接返回 0,与列表内容无关。

Case 3 · visible: single contract already covers target

输入: [3,7,[7,1,2]]

期望: 1

下标 0 的合约 0b111 单条即可覆盖 target,最少 1 条。

Case 4 · visible: impossible coverage returns -1

输入: [3,7,[1,2]]

期望: -1

所有合约的并集仅为 0b011,bit 2 永远缺失,故返回 -1。

最近提交

还没有提交记录。

编码区

实现 solution(...)。本地运行当前支持 Python 可见样例;服务端提交会运行可见样例和隐藏测试。

加载编辑器...
计时0:00

默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。

Case 1 · statement-example: B=4 covered by two contracts

输入: [4,15,[12,3,5,10]]

期望: 2

选取下标 0 和 1:0b1100 | 0b0011 = 0b1111,恰好覆盖全部 4 个 bucket,最少 2 条。

Case 2 · visible: target_mask 0 returns 0

输入: [3,0,[1,2,4]]

期望: 0

target_mask = 0 表示无需覆盖,直接返回 0,与列表内容无关。

Case 3 · visible: single contract already covers target

输入: [3,7,[7,1,2]]

期望: 1

下标 0 的合约 0b111 单条即可覆盖 target,最少 1 条。

Case 4 · visible: impossible coverage returns -1

输入: [3,7,[1,2]]

期望: -1

所有合约的并集仅为 0b011,bit 2 永远缺失,故返回 -1。