Блог

Недавно я столкнулся с этой проблемой во время интервью:

Задан набор чисел X = [X_1, X_2, ...., X_n] , X_i lt;= 500 для 1 lt;= i lt;= n которых . Увеличьте числа (только положительные приращения) в наборе так, чтобы каждый элемент в наборе имел общий делитель gt;=2 и чтобы сумма всех приращений была минимизирована.

Например, если X = [5, 7, 7, 7, 7] новый набор будет X = [7, 7, 7, 7, 7] , так как вы можете добавить 2 к X_1. X = [6, 8, 8, 8, 8] имеет общий знаменатель 2, но неверен, так как мы добавляем 6 (добавьте 2 к 5 и 1 к каждому из 4 7).

У меня было, казалось бы, рабочее решение (так как в нем прошли все тестовые случаи), которое перебирает простые числа lt; 500 и для каждого X_i из X них находит ближайшее кратное простому числу, большее X_i.

 function closest_multiple(x, y)  return ceil(x/y)*y  min_increment = inf for each prime_number lt; 500:  total_increment = 0  for each element X_i in X:  total_increment  = closest_multiple(X_i, prime_number) - X_i  min_increment = min(min_increment, total_increment)  return min_increment  

Технически это O(n), но есть ли лучший способ решить эту проблему? Мне предложили использовать динамическое программирование, но я не уверен, как это здесь уместится.

Случай с постоянными записями

Когда X_i он ограничен константой, лучшее время , которое вы можете достичь асимптотически O(n) , — это, поскольку для чтения всех ваших входных данных требуется по крайней мере столько же времени. Есть некоторые практические улучшения:

1. Отфильтруйте дубликаты, чтобы вы работали со списком пар (элемент, частота).
2. Ранняя остановка в вашем цикле.
3. Более быстрое вычисление closest_multiple(x, p) - x . Это немного зависит от аппаратного обеспечения/языка, но операция с одним целочисленным модулем почти наверняка быстрее, чем приведение int -gt; с плавающей запятой, деление с плавающей запятой, вызов ceiling() и умножение на те же значения.

 freq_counts lt;- Initialize-Counter(X) // List of (element, freq) pairs min_increment = inf  for each prime_number lt; 500:  total_increment = 0  for each pair X_i, freq in freq_counts:  total_increment  = (prime_number - (X_i % prime_number)) * freq  if total_increment gt;= min_increment: break  min_increment = min(min_increment, total_increment)  return min_increment  

Случай больших записей

При равномерно выбранных случайных данных ответ почти всегда заключается в использовании » 2 » в качестве делителя, а гораздо большие простые делители исчезающе маловероятны. Однако давайте решим этот наихудший сценарий.

Здесь пусть max(X) = M, так что наш входной размер равен O(n (log M)) битам. Мы хотим, чтобы решение было субэкспоненциальным по этому размеру входных данных, поэтому о нахождении всех простых чисел ниже M (или даже sqrt(M)) не может быть и речи. Мы ищем любое простое число, которое дает нам минимальное общее приращение; мы будем называть такое простое число минимальным. Найдя такое простое число, мы можем получить минимальное общее приращение за линейное время. Мы будем использовать факторинговый подход наряду с двумя наблюдениями.

• Наблюдение 1: Ответ всегда не более n , так как приращение, необходимое для деления простого числа 2 X_i , составляет не более 1.
• Наблюдение 2: Мы пытаемся найти простые числа, которые делятся X_i , или число, немного большее, чем X_i для большой части наших записей X_i . Пусть Consecutive-Product-Divisors[i] будет множество всех простых чисел , делящих любое из X_i or X_i 1 них, которое я буду сокращать CPD[i]. Это именно тот набор всех простых чисел, которые делятся X_i * (1 X_i) .
• (Obs. 2 Продолжение) Если U является известной верхней границей нашего ответа (здесь не более n) и p является минимальным простым числом для X, то p необходимо разделить либо X_i или X_i 1 по крайней мере N - U/2 для одной из наших записей CPD. Используйте подсчеты частоты в массиве CPD, чтобы найти все такие простые числа.

Как только у вас будет список простых чисел-кандидатов (все минимальные простые числа гарантированно будут в этом списке), вы можете протестировать каждое из них индивидуально, используя свой алгоритм. Поскольку число k может иметь не более O(log k) различных простых делителей, это дает O(n log M) возможные различные простые числа, которые делят по крайней мере половину чисел
[X_1*(1 X_1), X_2*(1 X_2), ... X_n*(1 X_n)] это составляет наш список кандидатов. Возможно, вы сможете снизить эту границу с помощью более тщательного анализа, но это, скорее всего, не сильно повлияет на асимптотическое время выполнения всего алгоритма.

Более оптимальная сложность для больших записей

Сложность этого решения трудно описать в краткой форме, потому что узким местом является факторизация n чисел максимального размера M плюс O(n^2 log M) арифметические (т. е. Операции сложения , вычитания, умножения, по модулю) для чисел максимального размера M . Это не означает, что время выполнения неизвестно: если вы выберете любой алгоритм целочисленного факторинга и алгоритмы большой целочисленной арифметики, вы сможете точно определить время выполнения. К сожалению, из-за факторинга наиболее известным временем выполнения вышеупомянутого алгоритма является суперполиномиальное (но субэкспоненциальное).

Как мы можем сделать лучше? Я нашел более сложное решение, основанное на Наибольших общих делителях (GCD) и динамическом программировании, которое выполняется за полиномиальное время (хотя, вероятно, намного медленнее при вводе данных не астрономического размера), поскольку оно не зависит от факторинга.

Решение основано на том факте, что по крайней мере одно из следующих двух утверждений верно:

1. Число 2 является минимальным простым числом для X, или
2. По крайней мере для одного значения из i 1 lt;= i lt;= n существует оптимальное решение , в котором X_i остается неиспользованным, т. Е. Когда один из делителей X_i производит минимальное общее приращение.

Алгоритм полиномиального времени на основе GCD

Мы можем быстро протестировать 2 и все малые простые числа с минимальными затратами. Фактически, мы проверим все простые p lt;= n числа p, что мы можем сделать за полиномиальное время , и вычтем эти простые числа из X_i и его первых n приращений. Это приводит нас к следующему алгоритму:

 // Given: input list X = [X_1, X_2, ... X_n]. // Subroutine compute-min-cost(list A, int p) is  // just the inner loop of the above algorithm.  min_increment = inf; for each prime p lt;= n:  min_increment = min(min_increment, compute-min-cost(X, p));  // Initialize empty, 2-D, n x (n 1) list Y[n][n 1], of offset X-values for all 1 lt;= i lt;= n:  for all 0 lt;= j lt;= n:  Y[i][j] lt;- X[i]   j;  for each prime p lt;= n: // Factor out all small prime divisors from Y  for each Y[i][j]:  while Y[i][j] % p == 0:  Y[i][j] /= p;  for all 1 lt;= i lt;= n: // Loop 1  // Y[i][0] is the test 'unincremented' entry  // Initialize empty hash-tables 'costs' and 'new_costs'  // Keys of hash-tables are GCDs,  // Values are a running sum of increment-costs for that GCD   costs[Y[i][0]] = 0;  for all 1 lt;= k lt;= n: // Loop 2  if i == k: continue;  clear all entries from new_costs // or reinitialize to empty  for all 0 lt;= j lt; n: // Loop 3  for each Key in costs: // Loop 4  g = GCD(Key, Y[k][j]);  if g == 1: continue;  if g is not a key in new_costs:  new_costs[g] = j   costs[Key];  else:  new_costs[g] = min(new_costs[g], j   costs[Key]);    swap(costs, new_costs);  if costs is not empty:  min_increment = min(min_increment, smallest Value in costs);  return min_increment;  

Правильность этого решения следует из двух предыдущих наблюдений и (недоказанного, но простого) факта, что существует список [X_1 r_1, X_2 r_2, ... , X_n r_n] (с 0 lt;= r_i lt;= n для всех i ), чей GCD является делителем с минимальной стоимостью приращения.

The runtime of this solution is trickier: GCDs can easily be computed in O(log^2(M)) time, and the list of all primes up to n can be computed in low poly(n) time. From the loop structure of the algorithm, to prove a polynomial bound on the whole algorithm, it suffices to show that the maximum size of our ‘costs’ hash-table is polynomial in log M . This is where the ‘factoring-out’ of small primes comes into play. After iteration k of loop 2, the entries in costs are (Key, Value) pairs, where each Key is the GCD of k 1 elements:
our initial Y[i][0] , and [Y[1][j_1], Y[2][j_2], ... Y[k][j_k]] for some 0 lt;= j_l lt; n . The Value for this Key is the minimum increment sum needed for this divisor (i.e. sum of the j_l ) over all possible choices of j_l .

Существует не более O(log M) уникальных простых делителей Y[i][0] . Каждое такое простое число делит не более одного ключа в нашей таблице «затраты» в любое время: поскольку мы вычли все простые делители ниже n , любой оставшийся простой делитель p может разделить не более одного из n последовательных чисел в любом Y[j] = [X_j, 1 X_j, ... n-1 X_j] . Это означает, что общий алгоритм является полиномиальным и имеет время выполнения ниже O(n^4 log^3(M)) .

Отсюда открытые вопросы заключаются в том, существует ли более простой алгоритм и насколько лучше, чем эта граница, вы можете достичь. Вы определенно можете оптимизировать этот алгоритм (в том числе с использованием предыдущих отсчетов времени и частоты). Также вероятно, что лучшие оценки подсчета больших и различных простых делителей для последовательных чисел показывают, что это решение уже лучше, чем заявленное время выполнения, но упрощение этого решения было бы очень интересным.