Алгоритм нахождения чисел без пар из большого потока данных?

Question

[ArtemE]

Добрый день!

Сегодня проходила олимпиада KPI-Open и на ней была интересная задача:

Ограничения: 8 сек. 8Мб

Условие

Есть N натуральных чисел ( N парное от 2 до 10 000 000) по модулю не больше 1 000 000 000. Среди этих чисел почти все имеют себе пару. Но два числа — без пары. Необходимо найти те самые два числа без пары.

Внимание обращаю на ограничения.

Пример

На вход

6

4 8 4 7 9 9

Ответ

7 8



Пример2

На вход

8

7 7 7 5 5 5 5 6

Ответ

6 7

Решение с BitMap не проходит по памяти. Содержать все числа в памяти не получается. Думаем, что решение основывается на xor-е всех чисел между собой и подбором двух чисел, которые бы при xor-е их с хоr-ом всех чисел дали бы 0.

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

Comments

[ArtemE]

Решение уже известно. Рассказать? =)

Answer 1

[jcmvbkbc]

uint32_t xor_all = 0;
uint32_t xor_bit[32] = {0};

....

for (i = 0; i < n; ++i) {
    xor_all ^= in;
    for (j = 0; j < 32; ++j) {
        if (in & (1 << j))
            xor_bit[j] ^= in;
    }
}

for (j = 0; j < 32; ++j) {
    if (xor_all & (1 << j)) {
        out1 = xor_bit[j];
        out2 = xor_all ^ xor_bit[j];
        break;
    }
}

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

Comments

[ArtemE]

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

[jcmvbkbc]

Непарные числа различаются по меньшей мере одним битом. Значит если мы посчитаем xor от всех чисел, в которых этот бит установлен, то результатом будет одно из непарных чисел (поскольку парные числа друг друга компенсируют, а второе непарное число не будет посчитано, т.к. этот бит в нем не установлен). Поскольку мы заранее не знаем, в каком бите будут отличаться непарные числа, будем отдельно подсчитывать результат xor для всех чисел в которых установлен 0й бит, 1й бит,… 31й бит (хотя, для чисел до 1 000 000 000 достаточно будет и 30 бит). Для этого потребуется 4 * 32 = 128 байт памяти (: Кроме того будем тащить xor вообще для всех чисел. В конце концов парные числа в нём так же друг друга компенсируют, а результатом будет число, единичные биты которого соответствуют различающимся битам непарных чисел.
Полная рабочая программка выглядит так:

#include <stdio.h>

unsigned xor_all = 0;
unsigned xor_bit[32] = {0};

int main(void)
{
        int i, j;
        int n, in, out1, out2;

        scanf("%i", &n);

        for (i = 0; i < n; ++i) {
                scanf("%i", &in);
                xor_all ^= in;
                for (j = 0; j < 32; ++j) {
                        if (in & (1 << j))
                                xor_bit[j] ^= in;
                }
        }

        for (j = 0; j < 32; ++j) {
                if (xor_all & (1 << j)) {
                        out1 = xor_bit[j];
                        out2 = xor_all ^ xor_bit[j];
                        printf("%d %d\n", out1, out2);
                        break;
                }
        }
        return 0;
}

[greatvovan]

ИМХО вместо того, чтобы тащить с собой дополнительные 32 XOR-суммы, лучше в общей сумме найти ненулевой бит и ещё раз пройти по массиву, просуммировав те элементы, где он установлен. В этом случае проходов по массиву два, зато общее количество операций на каждом шаге в 32 раза меньше. И маску 1 << j тоже можно сохранить.

[jcmvbkbc]

@greatvovan да, есть такой вариант, но с точки зрения производительности он заведомо проигрышный из-за кеширования. И один проход -- несомненный плюс, если данные приходят из stdin.

Answer 2

[turboNOMAD]

Я бы использовал множество (set).
Алгоритм такой: для каждого числа проверяем, есть ли оно в множестве. Если нет, добавляем, иначе удаляем. Проверка эта идет за O(log n) для std::set на C++, или вообще за константу для хэш-контейнеров. (Я не знаю, какой язык можно использовать по условию задачи).
Единственная проблема — если числа и их пары расположены не псевдослучайно, а например сначала все уникальные, а потом все их пары. В таком случае при проходе первой половины массива размер множества будет только увеличиваться и можем пролететь с ограничением по памяти.

Comments

[turboNOMAD]

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

[ArtemE]

это решение не пройдет, увы. В память не поместятся в худшем случае.

Answer 3

[nicolausYes]

+1, писал то же самое. В зависимости от компилятора, на С++ можно использовать либо С++11 контейнеры (unordered_set), либо из пространства имен tr1 на более старых компиляторах, если такое присутствует. По сути, при решении в лоб, придется хранить как минимум половину значений, либо хранить как-то более хитро.

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

Так вы еще их в массив сохраняете? Сразу сохраняйте в используемую структуру при считывании (set, unordered_set, unordered_map — в tr1 точно есть).

Comments

[nicolausYes]

Ой, промахнулся :(

[turboNOMAD]

Я не предлагаю сохранять в массив, просто не знаю, по условию числа вводятся потоково или массивом. Если массивом, то применим мой комментарий к ответу.

[nicolausYes]

Значения обычно читаются последовательно с файла (на олимпиадах встречается довольно редко), либо со стандартного ввода (stdin, обычным scanf или cin. Первое число — количество чисел. А дальше цикл на прочитанное число раз – чтение данных).

[ArtemE]

хранить придется, но хитро.

Answer 4

[Arktos]

Нам нужно будет считать этот массив 2 или 3 раза. Сначала будем хранить эти числа по модулю 10^5. Заведем bool-массив из 10^5 элементов — сколько раз каждый модуль встречался. Рассмотрим 2 варианта
1) Искомые числа по модулю 10^5 различные. Тогда у нас будут 2 ненулевые ячейки. Мы знаем модули искомых чисел по 10^5. Задача свелась к следующей — найти из массива чисел одно число, не имеющее себе пары. Решается xor-ом. Считываем снова массив и вычисляем 2 xor-а для найденных модулей.
2) Искомые числа равны по модулю 10^5 (все ячейки нулевые). Тогда они не равны по модулю 10^5+1.

Comments

[Arktos]

Можно и не считывать несколько раз, а один раз считать и проделать сразу все действия — вычислить все xor-ы чисел по модулю 10^5 и 10^5+1

[ArtemE]

а нельзя вычислять xor для всех N без модулей, а сами числа сложить в два массива (причем ксорить их по модулям простых чисел). а затем перебрать числа, выбрать подходящие из этих массивов и проверить обнулят ли они ксором общий xor?

[Arktos]

Может и можно. Но зачем перебирать, если можно их сразу получить ксоря полностью группы по модулю.
Да, не заметил, что числа могут быть отрицательные. Тогда сначала их надо привести к положительным прибавив 10^9 и разбивать на группы по модулям двух взаимнопростых чисел больше корня, например 10^5 и 10^5 + 1.