转跳到内容

每 日 算 法 挑 战 【第6期】


只显示该作者

只有该作者的内容显示中。 返回到主题

推荐贴

数学一点的描述可以是

给定数组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

,由yhz012修改
注释
摸鱼奇才咖啡喵 摸鱼奇才咖啡喵 200.00节操
链接到点评

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

经典方案就是

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

S = A + B + C

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

,由yhz012修改
链接到点评
11 分钟前, Muriya Tensei 说道:

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

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

yhz012在前往新手村的路上遇见了劫道的风神烈破,收取过路费-3节操

链接到点评
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)级别的)

,由yhz012修改
注释
Mr.K 018 Mr.K 018 50.00节操 啊,这……
链接到点评
40 分钟前, 随性而为 说道:

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

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

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

,由yhz012修改
链接到点评
×
×
  • 新建...

重要消息

为使您更好地使用该站点,请仔细阅读以下内容: 使用条款