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]...让我们调用必须彼此相等的每个元素序列， seq(i)。我们可以计算所需更改数量的最小上限，注意如果只 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)

标签： algorithmdynamic-programming

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)。然后练习包括纠正由传输通道引入的错误。在通道之后，不再遵守条件，最可靠的估计在于重建正确的序列，同时引入尽可能少的修改（校正）。

让我们称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]

通过最大化每个集合的可靠性，我们得到了B[i]集合的估计E[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 分支。