Блог

Я считаю, что срок действия онлайн-судьи для этой задачи истек. Учитывая мое предложенное ниже решение, логично ли оно? Можем ли мы добиться большего с точки зрения сложности времени или пространства? Как будет выглядеть практический метод грубой силы для сравнения?

Задача:

Учитывая массив длины n , найдите минимальное количество элементов, которые необходимо было бы изменить, чтобы XOR каждого k последовательного элемента был равен 0.

Ограничения:

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

Предлагаемое решение:

Допустим, у нас есть оптимальный выбор для первых k элементов. Чтобы обновить текущее окно до следующих смежных k элементов, мы удаляем вклад первого элемента и XOR со следующим предложенным элементом. Чтобы удалить вклад первого элемента, мы выполняем с ним XOR, что означает, что единственный вариант сделать следующее окно XOR равным нулю — это XOR с элементом, который мы только что удалили. Это означает, что оптимальные первые 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) s жизнеспособным решением, включая выбор с наименьшими затратами для каждого.

Чтобы попытаться добиться большего, чем минимальная верхняя граница, мы исключаем использование любого произвольного присваивания, поэтому все целевые параметры для каждого 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)
  

Как упоминалось в 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 до to 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] для set 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, пока текущее количество модификаций больше, чем текущее полученное наилучшее решение.