娱乐 每 日 算 法 挑 战 【第6期】

[yhz012]

等下是我理解错了么？M/3侧是开区间，所以三个加一起怎么也小于M？

[yhz012]

1 分钟前, Mr.K 018 说道:

领会精神就好M已修改为M的右界

那最暴力方案O(n^3)肯定能跑了（

顺带是不是应该用maxM +1，不然如果M刚好取最大值也可以直接说没方法了（x

[yhz012]

数学一点的描述可以是

给定数组ABC，求系数abc，使得abc各分量都是01，且 sum a = sum b = sum c = 1，sum aA+bB+cC = M

所以这个是个01规划问题……，如果求精确解估计最好也只能伪多项式级别了

 

  

54 分钟前, Mr.K 018 说道:

原题如此

n^3怕是只能AC掉easy……

什么我以为连easy都会有问题的（x

因为真的太暴力了（

退一万步说sort一下之后也可以拉到O(n^2)的（

先把ABC 花O(nlogn)sort出来

for a in A:
  tempC = C[-1]
  for b in B:
    while a + b + tempC > M:
      tempC = tempC.prev
    if a + b + tempC == M:
      count = count + 1

这样BC实际上是一起跑的，所以事实上只有2个循环，能拉到O(n^2)

嗯这里我假定了ABC所有元素都不同，如果相同稍微改一下上面的代码问题应该也不大

或者舍得空间复杂度的话直接写哈希表

for a in A:
  dict = dict + {M - a: a}
for b in B:
  for c in C:
    if b + c in dict:
      count = count + 1

这个改相同元素很简单

for a in A:
  dict[M - a] = dict[M - a] + 1
for b in B:
  for c in C:
    if b + c in dict:
      count = count + dict[b + c]

避免误解，这里的dict始终都是hashmap，key存在的时候返回value，key不存在的时候返回0，所以前面打表A的时候我手懒判断M-a存不存在了（理解意思就好（x

四月 15, 2020，由yhz012修改

[yhz012]

暴力一点的处理方法就是规约到3SUM了吧

经典方案就是

A = 10 * A + 1
B = 10 * B + 2
C = (10 * C - 3) - 10 * M

S = A + B + C

然后用3sum的伪多项式求法就可以了吧？等下，3sum有更快的伪多项式算法么

四月 15, 2020，由yhz012修改

[yhz012]

11 分钟前, Muriya Tensei 说道:

暴力点，第三行打表，然后遍历前两行就行了，但是表要打M/3讲道理有点长

打哈希表的话，长度只有N，问题不大，尤其在最难的情况下数量级差太多了

[yhz012]

刚刚, Muriya Tensei 说道:

但是只会c，不会写哈希表（单论算法还好，但是我太菜了，表都打不好）

C啊……我记得C甚至不自带hash相关库吧……会很痛苦…………

[yhz012]

1 分钟前, Mr.K 018 说道:

C++的set和map库都是用堆实现的，C甚至根本就没那库

C我记得可以用开源的uthash来着好像，我找找

在这http://troydhanson.github.io/uthash/

四月 15, 2020，由yhz012修改

[yhz012]

1 小时前, Muriya Tensei 说道:

c想打哈希表需要先自己代码实现（但是之前研究过，太菜了，没搞懂，很绝望）

自己实现需要一些知识点

为了方便我们以这道题考虑，每个石头的魔力是0~M/3，为了方便我就用u = M/3来写了，我们一共打算开n个空位来保存这些石头。这里u大概是10^17，n大概是10^4

 

第一个就是universal hash family

 

作为大前提，任何确定的hash函数都会在某些特定的输入上出现严重的冲突。因为很显然我们要把10^17映射到10^4里，那至少有一个格子要对应至少10^13个不同的石头。在这种情况下，如果你先给我个确定的函数来映射，那我一定能找到这个格子，然后挑这堆格子的对应的石头给你，结果就是所有石头全跑一个格子里去了，打表大失败

 

所以我们需要的是反过来，我有一组hash函数，你先给我石头，然后我随机挑一个函数来映射。如果映射的结果好，那万事大吉。如果映射的结果不好，退一万步说最坏情况下我可以重选一个，然后再映射。

只要我映射的结果好的概率足够大，那就不是问题。

更数学一点的说法就是，我现在有一组函数。我任意拿出两块石头，我都能保证在我这一组函数中，我随便拿出来一个，让这俩石头映射到一个格子里的概率只有1/n

再换一个表述方式就是，假设我们一共有H个函数，对于任意两块石头，最多有H/n个函数把这两块石头放到一起

 

而满足这个定义的这一组函数的集合，称为universal hash family

 

之所以需要这个集合，是因为我们核心目的是希望平均来说，每个格子尽可能少的石头

具体来讲比如我们现在需要一个x的石头，这时候如果同一个格子里有个y石头，那我们就需要再花时间来判断哪个是x哪个是y，如果更多，我就需要花费更多的时间。

根据上面的universal hash family定义，和x映射到同一个格子的概率是1/n，我一共有n块石头，所以期望是1块。换句话说平均来说，每个格子里只会有2块石头，分辨2块石头的时间是O(1)的级别，所以问题不大。

 

接下来的问题就是我们需要找到一个这样的universal hash family

这里开始会涉及一点数论的知识了。另外构造方法不唯一，我只是拿一个我习惯的例子

我们目标是开至少n个格子，为了方便一点，我能找到一个刚好比n大一点的素数p，我直接开p个格子

每个石头的魔力量我都可以写成p进制的形式，举例来说p = 3的情况下，5魔力我就可以写成(0, 0, 0, ..., 0, 1, 2)，一共log_3 (u) 个分量

因此任意的一个石头x，我都能写成(x_r, x_{r-1}, ..., x_2, x_1, x_0)的形式。这里r = log_p (u)

同时我构造这样一个数组，a = (a_r, a_{r-1}, ..., a_2, a_1, a_0)，每一位也都是在[0, p-1]里面随机选

我的hash函数就是 a 和 x 对应位相乘后对p取余，然后求和，即 sum_i (a_i * x_i) % p

因此整个universal hash family 就是所有可能取到的a

 

接下来我需要证明这个确实是个universal hash family

那我们考虑两个不同的石头x和y

因此我写成p进制之后至少存在一个分量 x_k != y_k

我们把这一个分量单独拿出来，选择随机的一个hash函数h：

h(x) = (x' + a_k * x_k) % p，其中x'是其他分量的求和

h(y) = (y' + a_k * y_k) % p

如果相等，意味着

a_k (x_k - y_k) % p = (x' - y') %p

这里我需要两个数论的定理了

定理1： 给定非零整数 i < p，那么有 ix %p = iy %p 当且仅当 x %p = y %p

定理2： 给定整数 b, c < p，且b != 0，有且仅有一个整数a < p，使得 a * b %p = c

根据这两个定理，我们回到上面的 a_k (x_k - y_k) % p = (x' - y') %p

意味着有且仅有一个a_k使得上述等式成立

而a_k我们是在0~p-1里面随机选的。所以h(x) = h(y)的概率就只有1/p。证明完毕。

 

给定以上情况，我们已经找到了一个universal hash family，用这个就可以构造hashmap了

接下来是性能分析的问题

平均来说，映射到一起的概率是1/n，所以平均查找速度是O(1 + n * 1/n) = O(1)

但是上面只是平均结果，我们会存在一些格子有更多的石头，可以计算得到最满的格子里的石头个数的期望是O(log n / log(log n) )，如果你不是很在意这一丁点的性能差异的话，几乎和O(1)没啥问题，直接用也可以了

如果很在意，我们有以下解决方案

 

1. 之前我们考虑的是放到n个格子里，现在如果我们用放到n^2个格子里，经过计算是可以保证时间复杂度的（可以用马尔科夫不等式证明不产生冲突的概率至少是1/2），不过问题是我们需要n^2空间，有的时候还是挺肉疼的

 

2. 之前我们是用类似链表的形式处理放在同一个格子里的石头的，实际上我们可以再进一步在这个格子里继续构造一个二级的hashmap，经过计算也是可以保证时间复杂度和空间复杂度的。（假设每个格子里的石头数是S_i，可以证明sum (S_i)^2的期望是O(n)级别的）

四月 15, 2020，由yhz012修改

[yhz012]

40 分钟前, 随性而为 说道:

01规划已经看见大佬提了好多次了

其实就是线性规划但是要求解只能是0和1里面选

某种意义上你可以理解为扫雷其实就是01规划问题，顺带一提这问题是NP完全问题，所以会有很多相关的问题

四月 16, 2020，由yhz012修改