Разбор задачи «Ocean Cleanup Signals»

Идея задачи

Дан отрезок целых чисел [l, r]. Нужно удалить минимальное количество чисел так, чтобы побитовое AND всех оставшихся чисел было не равно нулю.

Если побитовое AND нескольких чисел не равно нулю, это означает, что существует хотя бы один бит, который равен 1 у всех этих чисел.

Значит, задача на самом деле сводится к следующему:

• выбрать какой-то бит;
• оставить только те числа на отрезке [l, r], у которых этот бит равен 1;
• удалить все остальные.

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

Остаётся понять, какой бит выбрать. Очевидно, выгоднее выбрать тот бит, который установлен у максимального количества чисел на отрезке.

Тогда:

• len = r - l + 1 — всего чисел на отрезке;
• cnt(bit) — сколько чисел на отрезке имеют данный бит, равный 1.

Если мы выбрали этот бит, то можем оставить cnt(bit) чисел и удалить len - cnt(bit) чисел.

Значит, ответ равен:

len - max(cnt(bit)).

Ключевое наблюдение

Побитовое AND набора чисел будет ненулевым тогда и только тогда, когда существует хотя бы один бит, который равен 1 у всех чисел этого набора.

Это очень важный переход.

Многие сначала думают, что нужно как-то моделировать сам процесс AND для разных подмножеств. Но это было бы слишком сложно. Вместо этого нужно смотреть не на всё число целиком, а на каждый бит отдельно.

Если некоторый бит встречается у большого количества чисел, то именно эти числа можно оставить. Тогда общий AND по ним точно сохранит этот бит.

Как быстро считать количество единиц в каждом бите

Для одного запроса можно просто перебрать все числа от l до r и для каждого проверить все биты. Но если запросов много, такой способ будет слишком медленным.

Ограничение на числа позволяет сделать предварительный подсчёт.

Пусть

• pref[b][x] — количество чисел от 1 до x, у которых бит b равен 1.

Тогда количество чисел на отрезке [l, r], у которых бит b равен 1, можно найти так:

pref[b][r] - pref[b][l - 1].

Это стандартная идея префиксных сумм.

Почему достаточно рассматривать около 20 битов

По условию верхняя граница r не превосходит 2 * 10^5.

Так как:

• 2^17 = 131072,
• 2^18 = 262144,

то все числа из условия помещаются меньше чем в 18 бит. Для надёжности можно взять 20 бит.

Этого более чем достаточно.

Алгоритм

Предподсчёт

Для каждого бита b от 0 до 19:

• для каждого числа x от 1 до MAXN:

  • проверяем, равен ли бит b у числа x единице;
  • строим массив префиксных сумм.

Ответ на запрос

Для запроса [l, r]:

1. Находим длину отрезка: len = r - l + 1.

2. Для каждого бита b считаем:

   • сколько чисел на отрезке имеют этот бит равным 1.
3. Берём максимум по всем битам.
4. Ответ: len - best.

Разберём на примере

Пусть запрос: [2, 8].

Числа:

• 2 = 0010
• 3 = 0011
• 4 = 0100
• 5 = 0101
• 6 = 0110
• 7 = 0111
• 8 = 1000

Посмотрим, сколько раз встречаются единицы в разных битах:

• младший бит равен 1 у чисел 3, 5, 7 — 3 числа;
• второй бит равен 1 у чисел 2, 3, 6, 7 — 4 числа;
• третий бит равен 1 у чисел 4, 5, 6, 7 — 4 числа;
• четвёртый бит равен 1 только у числа 8 — 1 число.

Лучший результат — оставить 4 числа. Значит, удалить нужно:

7 - 4 = 3.

Именно это и будет ответом.

Почему алгоритм корректен

Докажем это аккуратно.

Пусть мы хотим оставить некоторое множество чисел так, чтобы их побитовое AND был ненулевым.

Это означает, что в результате AND есть хотя бы один бит, равный 1.

Но бит в результате AND равен 1 только тогда, когда он равен 1 у каждого числа из выбранного множества.

Значит, все оставленные числа обязательно должны содержать некоторый общий бит b.

Следовательно, количество оставленных чисел не может быть больше, чем количество чисел на отрезке [l, r], у которых бит b равен 1.

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

А раз мы хотим удалить минимальное число элементов, то должны оставить максимальное число элементов.

Поэтому ответ действительно равен:

(r - l + 1) - max(cnt(bit)).

Что и требовалось доказать.

Оценка сложности

Пусть MAXN = 200000, число битов B = 20.

Предподсчёт

Мы строим таблицу размера B × MAXN, значит:

• время: O(B * MAXN);
• память: O(B * MAXN).

Один запрос

Для каждого запроса мы перебираем все биты:

• время: O(B).

Так как B = 20, это очень быстро.

Реализация на C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    const int MAXN = 200000;
    const int BITS = 20;

    vector<vector<int>> pref(BITS, vector<int>(MAXN + 1, 0));

    for (int bit = 0; bit < BITS; bit++) {
        for (int x = 1; x <= MAXN; x++) {
            pref[bit][x] = pref[bit][x - 1] + ((x >> bit) & 1);
        }
    }

    int t;
    cin >> t;

    while (t--) {
        int l, r;
        cin >> l >> r;

        int len = r - l + 1;
        int best = 0;

        for (int bit = 0; bit < BITS; bit++) {
            int cnt = pref[bit][r] - pref[bit][l - 1];
            best = max(best, cnt);
        }

        cout << len - best << '\n';
    }

    return 0;
}

Реализация на Python

import sys

MAXN = 200000
BITS = 20

pref = [[0] * (MAXN + 1) for _ in range(BITS)]

for bit in range(BITS):
    for x in range(1, MAXN + 1):
        pref[bit][x] = pref[bit][x - 1] + ((x >> bit) & 1)

input = sys.stdin.readline
t = int(input())

for _ in range(t):
    l, r = map(int, input().split())

    length = r - l + 1
    best = 0

    for bit in range(BITS):
        cnt = pref[bit][r] - pref[bit][l - 1]
        if cnt > best:
            best = cnt

    print(length - best)

Частые ошибки

1. Пытаться перебирать все подмножества

Так делать нельзя: количество подмножеств слишком велико.

Здесь нужно заметить свойство побитового AND и перейти к анализу отдельных битов.

2. Считать AND всех чисел подряд и пытаться что-то исправлять

Это тоже не помогает. Даже если AND всего отрезка равен нулю, можно удалить несколько чисел и получить ненулевой результат. Нужно искать не текущее значение AND, а бит, который встречается у максимального числа элементов.

3. Забыть про l - 1 в префиксных суммах

Количество единиц на отрезке [l, r] считается как:

pref[b][r] - pref[b][l - 1].

Если написать просто pref[b][r] - pref[b][l], ответ будет неверным.

4. Взять слишком мало битов

Нужно, чтобы все возможные числа из условия помещались в рассматриваемый диапазон битов. Для этой задачи 20 битов достаточно.

Итог

Главная мысль задачи — не работать с AND целиком, а посмотреть на него через отдельные биты.

Если мы хотим, чтобы итоговый AND был ненулевым, нужно оставить числа, у которых есть общий установленный бит. Значит, нужно найти бит, который встречается на отрезке чаще всего.

После этого ответ получается очень просто:

• оставить можно максимум best чисел;
• удалить нужно остальные;
• ответ равен len - best.