algorithm - 最小变化使得每 k 个连续元素的 XOR 为 0

Question

我认为此任务的在线评委已过期。鉴于我在下面提出的解决方案，它在逻辑上是否合理？我们能否在时间或空间复杂度方面做得更好？用于比较的实用蛮力方法是什么样的？

任务:

给定一个长度为 n 的数组，找到需要更改的最少元素数，以使每个 k 连续元素的 XOR 为 0。

约束:

1 ≤ k ≤ n ≤ 10^4
0 ≤ A[i] < 1024

建议的解决方案:

假设我们对前 k 元素进行了最佳选择。为了将当前窗口更新为下一个连续的 k 元素，我们删除了第一个元素的贡献并与下一个提议的元素进行异或。为了删除第一个元素的贡献，我们对其进行异或，这意味着使下一个窗口异或为零的唯一选择是与我们刚刚删除的元素进行异或。这意味着最佳的前 k 元素必须在整个过程中不断重复。

e1, e2, e3,...ek, e1, e2, e3,...ek, etc.

让我们调用每个元素序列 A[i], A[i+k], A[i+2*k]... 必须彼此相等，序列(i)。我们可以通过注意如果 just one seq(i) 允许将其元素设置为任意一个元素，我们可以计算所需更改数量的最小上限，我们可以承担该成本并为剩余的 seq(i) 做出任何选择，包括每个成本最低的选择。

为了尝试比最小上限做得更好，我们排除了使用任何任意赋值，因此每个 seq(i) 的所有目标选项必须来自集合 seq(i ) 本身。此外，在我们迭代时，我们可以使用最小上限来排除任何成本相同或更高的 XOR 前缀。

时间复杂度 O(k * n/k * 1024) = O(n)。空间复杂度 O(n)。

Python 3 示例:

from collections import defaultdict
from math import ceil

A = [1, 2, 3, 1, 4]
k = 3

n = len(A)

seqs = [None] * k

for i in range(k):
  seqs[i] = defaultdict(lambda: 0)

  for j in range(i, n, k):
    seqs[i][A[j]] += 1

def cost(i, e):
  return ceil((n - i) / k) - seqs[i][e]
  
def min_cost(i):
  return min([cost(i, e) for e in seqs[i]])
  
total_min_cost = sum([min_cost(i) for i in range(k)])

upper_bound = total_min_cost + min([ceil((n - i) / k) - min_cost(i) for i in range(k)])

dp = {0: 0}

for i in range(k):
  new_dp = defaultdict(lambda: float('inf'))

  for e in seqs[i]:
    for xor_pfx in dp:
      new_cost = cost(i, e) + dp[xor_pfx]

      if new_cost < upper_bound:
        new_pfx = xor_pfx ^ e
        new_dp[new_pfx] = min(new_dp[new_pfx], new_cost)

  dp = new_dp
  
result = dp[0] if 0 in dp else upper_bound

print(result)

Answer 1

如 OP 所述，必须满足两个条件才能获得有效序列:

1. xor-sum_(i=0 to K-1) A[i] = 0
2. A[i+K] = A[i] for all i

这意味着构建这样一个序列有“K-1”个自由度。
注意:这种序列可以解释为大小为K-1的信息序列的信道编码，与简单奇偶校验编码的级联(条件1.，长度为K的序列是获得))和重复编码(条件 2 -> 长度 N)。然后练习包括纠正传输 channel 引入的错误。在 channel 之后，条件不再受到尊重，最可靠的估计包括重建正确的序列，同时引入尽可能少的修改(校正)。

让我们称 S[i] 对应于相同值的 K 个集合。 S[i] = {A[i], A[i+K], A[i+2*K], ...}, i: 0 -> K- 1,
让我们称 L[i] 为每个 S[i] 的大小。

第一步包括尝试对重复代码进行解码，即确定每个集合 S[i] 中哪些是最佳估计或哪些是最佳估计。从逻辑上讲，最佳估计在于为每个集合找到最有代表性的值。对于每个集合 S[i] 和每个可能的值 j(j 从 0 到 Amax，这里 Amax = 1023)，j的可靠性等于它在Set[i]中出现的次数。实际上:

Reliab[i][j]++ each times `j` appears in `S[i]`. 
and then, Cost[i][j] = L[i] - Reliab[i][j]

通过最大化每个集合中的可靠性，我们得到集合 E[i] 的估计 B[i]。
此时，如果估计遵守奇偶校验条件:

xor-sum B[i] = 0

然后我们找到了我们的估计，变化的数量对应一个下界:

lower_bound = sum(L[i] - reliab[i][B[i]])

然而，在一般情况下，不遵守奇偶校验条件，我们需要找到改变次数最少的方法。一种相当简单的可能性在于只修改一项估计，即对应于最低附加成本的估计。例如，如果我们接受修改估计 B[i]，那么我们必须将其替换为

C[i] = xor-sum B[j], for j different of i. 

那么额外的变化数等于

add_cost[i] = Reliab[B[i]] - Reliab[C[i]]]

但是，这种只修改一个先前估计的解决方案并不能保证始终将变化次数最小化。

要解决它，一种可能性(蛮力!)是迭代地计算与所有可能性对应的所有成本。

For (i: 0 -> K-1) For (j: 0 -> Amax)
    cumul_cost[i][j] = min(k) {cumul_cost[i-1][j^k] + Cost[i][k]} (k = 0 to Amax)

然后，如果等于 cumul_cost[K-1][0] 的答案

问题是这个方法的复杂度等于 O(N + K*Amax^2)，这看起来太多了。

至少，这个解决方案实现起来很简单，应该可以提供一个引用来检查更简单的解决方案。

在此方法中，考虑了许多中间结果，这些结果无法对应于可行的解决方案。一个应该更好的实用解决方案是实现回溯，同时优先考虑更可靠的元素。

这可以通过对集合 E[i] 进行排序而获得，并且在当前修改次数大于当前获得的最佳解决方案时不进一步探索 DFS 分支。