Поиск подмассива с целевым побитовым значением И

Question

Учитывая массив A размера N и целое число P, найдите подмассив B = A[i...j] такой, что i <= j, вычислите поразрядное значение элементов подмассива, скажем K = B[i] & B[i + 1] & ... & B[j].
Выведите минимальное значение |K-P| среди всех возможных значений K.

Answer 1

Здесь другой квазилинейный алгоритм, смешивающий yonlif Найти подрешетку с заданной суммой задачи решение с Гарольдом идея для вычисления K[i,j]; поэтому я не использую предварительную обработку, которая требует памяти. Я использую счетчик для отслеживания битов и вычисляю самое большее 2N значений K, каждое из которых стоит максимум O(log N). поскольку log N обычно меньше размера слова (B), он быстрее линейного алгоритма O(NB).

Подсчет битов N чисел может быть выполнен только с помощью ~ log N слов:

Таким образом, вы можете вычислять A[i]&A[i+1]& ... &A[I+N-1] только с log N операциями.

Вот способ управления счетчиком: если

• counter равно C0,C1, ...Cp и
• Ck - Ck0,Ck1, ...Ckm,

Тогда Cpq ... C1q,C0q - это двоичное представление числа бит, равного 1, среди q-го бита {A[i],A[i+1], ... ,A[j-1]}.

Реализация на битовом уровне (в python); все биты управляются параллельно.

def add(counter,x):
    k = 0
    while x :
        x, counter[k] = x & counter[k], x ^ counter[k]
        k += 1

def sub(counter,x):
    k = 0
    while x :
        x, counter[k] = x & ~counter[k], x ^ counter[k]
        k += 1

def val(counter,count):  # return A[i] & .... & A[j-1] if count = j-i.  
    k = 0
    res = -1
    while count:
       if count %2 > 0 : res &= counter[k]
       else: res &= ~counter[k]
       count //= 2
       k += 1
    return res

И алгоритм:

def solve(A,P):
    counter = np.zeros(32, np.int64) # up to 4Go
    n = A.size
    i = j = 0
    K=P # trig fill buffer
    mini = np.int64(2**63-1)

    while i<n :

        if  K<P or j == n :     # dump buffer 
            sub(counter,A[i])
            i += 1
        else:                   # fill buffer
            add(counter,A[j])
            j += 1

        if j>i: 
            K = val(counter, count)
            X = np.abs(K - P)
            if mini > X: mini = X
        else : K = P            # reset K     

    return mini

val, sub и add равны O(ln N), поэтому весь процесс составляет O(N ln N)

Тест:

n = 10**5
A = np.random.randint(0, 10**8, n, dtype=np.int64)
P = np.random.randint(0, 10**8, dtype=np.int64)

%time solve(A,P)
Wall time: 0.8 s
Out: 452613036735

Версия, скомпилированная с помощью Numba (украсьте 4 функции @numba.jit), работает в 200 раз быстрее (5 мс).

Answer 2

Вот квазилинейный подход, предполагающий, что элементы массива имеют постоянное число битов.

Строки матрицы K[i,j] = A[i] & A[i + 1] & ... & A[j] монотонно убывают (игнорируйте нижний треугольник матрицы). Это означает, что абсолютное значение разницы между K[i,:] и параметром поиска P является унимодальным и минимумом (необязательно, минимум , поскольку тот же минимум может встречаться несколько раз, но тогда они будут делать это в ряд) можно найти за O (log n) с помощью троичный поиск (при условии, что доступ к элементам K может быть организован в постоянное время). Повторите это для каждой строки и выведите позицию наименьшего минимума, доведя ее до O (n log n).

Выполнение поиска минимума строки за время, меньшее размера строки, требует неявного доступа к элементам матрицы K, что может быть достигнуто путем создания b массивов с префиксной суммой, по одному для каждого бита элементы A. Затем можно найти диапазон AND, вычислив все b однобитовые суммы диапазонов и сравнив их с длиной диапазона, причем каждое сравнение дает один бит диапазона AND. Это берет O (nb) предварительную обработку и дает O (b) (настолько постоянный, по предположению, которое я сделал в начале) доступ к произвольным элементам K.

Я надеялся, что матрица абсолютных различий будет матрицей Монжа, позволяющей использовать алгоритм SMAWK, но, похоже, это не так, и я не смог найти способ перейти к этому свойству.

Answer 3

Вы знакомы с подмассивом Find с заданной суммой ?Предлагаемое мной решение использует тот же метод, что и в эффективном решении по ссылке.Настоятельно рекомендуется прочитать его перед тем, как продолжить.

Сначала отметим, что чем длиннее подрешетка, тем больше будет ее K, так как оператор & между двумя числами может создать только меньшее число.

Поэтому, если у меня есть подмассив от i до j, и я хочу уменьшить его K, я добавлю больше элементов (теперь подмассив имеет от i до j + 1), если я хочу увеличить K, я удалю элементы (i + 1 до j).

Если мы рассмотрим решение для Find subarray with given sum, мы увидим, что его можно легко преобразоватьк нашей проблеме - данная сумма равна K, а суммирование аналогично использованию оператора &, но больше элементов меньше K, поэтому мы можем перевернуть сравнение сумм.

Эта проблема говорит вамесли решение существует, но если вы просто сохраняете минимальную разницу, которую вы нашли, вы также можете решить свою проблему.

Редактировать

Это решение верно, если всецифры положительные, как указано вкомментарии, если не все числа положительны, решение немного отличается.

Обратите внимание, что если не все числа отрицательны, K будет положительным, поэтому для нахождения отрицательного P мы можем рассмотреть только негативы в алгоритме, чем использовать алгоритм, как показано выше.

Answer 4

Вот решение, которое я написал и которое требует временной сложности порядка O(n^2). Приведенный ниже фрагмент кода написан на Java.

class Solution{
    public int solve(int[] arr,int p){
        int maxk = Integer.MIN_VALUE;
        int mink = Integer.MAX_VALUE;
        int size = arr.length;

        for(int i =0;i<size;i++){
            int temp = arr[i];
            for(int j = i;j<size;j++){
                temp &=arr[j];
                if(temp<=p){
                    if(temp>maxk)
                        maxk = temp;
                }
                else{
                    if(temp < mink)
                        mink = temp;
                }
            }
        }
        int min1 = Math.abs(mink -p);
        int min2 = Math.abs(maxk -p);
        return ( min1 < min2 ) ? min1 : min2;
    }
}

Это простой метод грубой силы, где 2 числа, скажем, x и y, такие, что x <= k и y> = k, где x и y - разные K = arr [i] & arr [i + 1 ] & ... arr [j] где i <= j для разных i и j для x, y. Ответом будет как минимум минимум | x-p | и | у-р | , </p>

Answer 5

Yonlif ответ неверный.

В Find subaray с заданной суммой решение у нас есть цикл, в котором мы выполняем подстановку.

while (curr_sum > sum && start < i-1)
    curr_sum = curr_sum - arr[start++];        

Так как нет обратного операторалогического И, мы не можем переписать эту строку и не можем использовать это решение напрямую.

Можно сказать, что мы можем пересчитать сумму каждый раз, когда увеличиваем нижнюю границу скользящего окна (что приведет нас кна O(n^2) сложность времени), но это решение не будет работать (в конце я приведу пример кода и счетчика).

Вот решение методом грубой силы, которое работает в O(n^3)

unsigned int getSum(const vector<int>& vec, int from, int to) {
    unsigned int sum = -1;
    for (auto k = from; k <= to; k++)
        sum &= (unsigned int)vec[k];
    return sum;
}

void updateMin(unsigned int& minDiff, int sum, int target) {
    minDiff = std::min(minDiff, (unsigned int)std::abs((int)sum - target));
}

// Brute force solution: O(n^3)
int maxSubArray(const std::vector<int>& vec, int target) {
    auto minDiff = UINT_MAX;
    for (auto i = 0; i < vec.size(); i++) 
        for (auto j = i; j < vec.size(); j++)                           
            updateMin(minDiff, getSum(vec, i, j), target);          
    return minDiff;
}

Вот решение O(n^2) в C ++ (благодаря BM ответ) Идея состоит в том, чтобы обновить текущую сумму вместо вызова getSum длякаждые два показателя.Вам также следует взглянуть на ответ BM , поскольку он содержит условия для раннего пробоя.Вот версия C ++:

int maxSubArray(const std::vector<int>& vec, int target) {
    auto minDiff = UINT_MAX;
    for (auto i = 0; i < vec.size(); i++) {
        unsigned int sum = -1;
        for (auto j = i; j < vec.size(); j++) {
            sum &= (unsigned int)vec[j];
            updateMin(minDiff, sum, target);
        }
    }               
    return minDiff;
}

Здесь НЕ работает решение со скользящим окном: Это идея из ответа Йонлифа с предварительным вычислением суммы в O(n^2)

int maxSubArray(const std::vector<int>& vec, int target) {
    auto minDiff = UINT_MAX;
    unsigned int sum = -1;
    auto left = 0, right = 0;

    while (right < vec.size()) {
        if (sum > target)
            sum &= (unsigned int)vec[right++];
        else                                
            sum = getSum(vec, ++left, right);       
        updateMin(minDiff, sum, target);            
    }
    right--;
    while (left < vec.size()) {
        sum = getSum(vec, left++, right);
        updateMin(minDiff, sum, target);            
    }   
    return minDiff;
}

Проблема этого решения в том, что мы пропускаем некоторые последовательности, которые на самом деле могут быть лучшими.

Ввод: vector = [26,77,21,6], target = 5.

Выход должен быть равен нулю при 77 & 21 = 5, но подход с скользящим окном не может найти его, поскольку он сначала будет рассматривать окно [0..3], а затем увеличить нижнюю границу, не имея возможности рассмотреть окно [1..2].

Если у кого-то есть линейное или логарифмическое решение, которое работает, было бы неплохо опубликовать.