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

[Mr.K 018]

第6期来啦！

本题有4个输入数据量的版本，分别对应不同复杂度的算法。大家能做到的最好的复杂度是多少呢？

第6期 PQ的魔法石

 

题目描述：

    PQ收集到了很多魔法石。

    魔法石一共有红黄蓝三种颜色，每块魔法石都有一个魔力值。PQ每种颜色的魔法石都有N块。

    传说，只要三块魔力值的和恰好等于M的三种魔法石各一块聚在一起时，就可以召唤出会长大人（注：出题时还没有Hololive，大家不用往那个方向想），并满足PQ的三个愿望。

    请问，PQ有多少种方法可以召唤出会长大人? 

输入：

第一行,两个整数N,M. 

    接下来三行,代表三种魔法石,每行N个整数,依次代表魔法石的魔力值. 所有魔力值的取值范围都在[0 , max(M)/3).

输出：

    符合条件的方案数. 保证结果在int范围内。

作者：

    PQ

 

---数据量---

Easy:         0 < N <= 500 , 0 < M <= 3000

Normal:    0 < N <= 5000 , 0 < M <= 3000

Hard:        0 < N <= 3000 , 0 < M <= 3 * 10 ^ 8

Extreme:   0 < N <= 10000 , 0 < M <= 3 * 10 ^ 17

做出难度更高的版本，奖励的节操更多哦！

召唤阵：

@yhz012 @inuisanaa @ZERC @随性而为 @NianRuoshui @摸鱼奇才咖啡喵

四月 15, 2020，由Mr.K 018修改

[yhz012]

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

[Mr.K 018]

1 分钟前, yhz012 说道:

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

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

[yhz012]

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

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

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

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

[Mr.K 018]

2 分钟前, yhz012 说道:

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

原题如此

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

四月 15, 2020，由Mr.K 018修改

[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修改

[NianRuoshui]

只要我的for够多什么都写的出来（暴言）

[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修改

[Muriya Tensei]

（继续潜水等大佬思路）（我太菜了，只能想到快排二分或者用空间换时间）

[Mr.K 018]

刚刚, Muriya Tensei 说道:

（继续潜水等大佬思路）（我太菜了，只能想到快排二分或者用空间换时间）

说说看嘛

反正不要钱，多少写一点，何况有节操

[Muriya Tensei]

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

说说看嘛

反正不要钱，多少写一点，何况有节操

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

(有没有测试案例啊)写了一串感觉很不靠谱

四月 15, 2020，由Muriya Tensei修改

[yhz012]

11 分钟前, Muriya Tensei 说道:

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

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

[Muriya Tensei]

1 分钟前, yhz012 说道:

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

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

[yhz012]

刚刚, Muriya Tensei 说道:

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

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

[Mr.K 018]

刚刚, yhz012 说道:

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

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

[Muriya Tensei]

刚刚, yhz012 说道:

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

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

[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修改

[Muriya Tensei]

52 分钟前, yhz012 说道:

自己实现需要一些知识点

为了方便我们以这道题考虑，每个石头的魔力是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)级别的）

太棒了，学到许多

[魍魉QAQ]

咱脑子里第一个蹦出来的就是遍历，哈希值也就研究md5的时候了解了一下。。

上面那位大佬的发言真的看得我云里雾里的。。

（没打过ACM，咱比较喜欢ctf这种逆算法的）

刚刚服务器好像炸了一下，直接404了

[随性而为]

22 小时前, Muriya Tensei 说道:

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

(有没有测试案例啊)写了一串感觉很不靠谱

 

22 小时前, yhz012 说道:

数学一点的描述可以是

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

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

 

  

什么我以为连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

浏览了下题目和大佬的初步分析，我感觉没必要用哈希表啊，如果想要o(n^2)的话，可以这样

for(i=0;i<=N;i++)

     for(j=0;j<=N;j++)

          if((M-i*A-j*B)%C==0&&(M-i*A-j*B)/C<=N)

                   count ++;

应该是可以跑hard难度的？extreme难度……，你这M怎么记录呢，unsigned long long好像也只能记到2^64-1

（理解错题目的意思了，尴尬）

（01规划已经看见大佬提了好多次了，看来是时候取学习一下了）

ps:昨天练了一天的车，真jb累，第一次跑还被教练冷嘲热讽的

四月 16, 2020，由随性而为修改

[Muriya Tensei]

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

 

浏览了下题目和大佬的初步分析，我感觉没必要用哈希表啊，如果想要o(n^2)的话，可以这样

for(i=0;i<=N;i++)

     for(j=0;j<=N;j++)

          if((M-i*A-j*B)%C==0&&(M-i*A-j*B)/C<=N)

                   count ++;

应该是可以跑hard难度的？extreme难度……，你这M怎么记录呢，unsigned long long好像也只能记到2^64-1

（01规划已经看见大佬提了好多次了，看来是时候取学习一下了）

ps:昨天练了一天的车，真jb累，第一次跑还被教练冷嘲热讽的

抛掉打表我也写了两个o(n^2)的了，但是跑不了ex

[yhz012]

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

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

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

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

四月 16, 2020，由yhz012修改

[随性而为]

1 分钟前, yhz012 说道:

我有点没看懂最里面的判断条件？

ABC是三种颜色石头的魔力组成的数列吗？

所以说我不是修改了那个回复了么……