Поиск самой большой из серии чисел XORed

Я работаю над решением проблемы, связанной с нахождением самой большой из серии чисел, являющейся XORed.

Это является реальной проблемой:

  

Xorq изобрел алгоритм шифрования, который использует побитовое XOR   операций. Этот алгоритм шифрования использует последовательность   неотрицательные целые числа \ $ x_1, x_2, ... x_n \ $ в качестве ключа. Чтобы реализовать это   алгоритм эффективно, Xorq должен найти максимальное значение для (\ $ a \ $ xor \ $ x_j \ $)   для заданных целых чисел \ $ a \ $, \ $ p \ $ и \ $ q \ $ таких, что \ $ p <= j <= q \ $. Помогите Xorq реализовать   эта функция.

     

Ввод

     

Первая строка ввода содержит одно целое число \ $ T \ $ (\ $ 1 <= T <= 6 \ $). Тест T   следуют случаи.

     

Первая строка каждого тестового примера содержит два целых числа \ $ N \ $ и \ $ Q \ $ разделенные   одним пространством (\ $ 1 <= N <= 100000 \ $; \ $ 1 <= Q <= 50,000 \ $). Следующая строка содержит   \ $ N \ $ целые числа \ $ x_1, x_2, ... x_n \ $, разделенные одним пространством (\ $ 0 <= x_i <2 ^ {15} \ $).   Каждая из следующих строк Q описывает запрос, который состоит из трех целых чисел   \ $ a_i \ $, \ $ p_i \ $ и \ $ q_i \ $ (\ $ 0 <= a_i <2 ^ {15} \ $, \ $ 1 <= p_i <= q_i <= N \ $ ).

     

Выход

     

Для каждого запроса напечатайте максимальное значение для (\ $ a_i \ $ xor \ $ x_j \ $) так, чтобы   \ $ p_i <= j <= q_i \ $ в одной строке.

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

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

#include <stdio.h>

int main (int argc, char * argv[]) {
    unsigned int T,N,Q,i,a,p,q,count,max,n[100000],res[100000];
    scanf ("%d\n%d %d", &T, &N, &Q);
    while (T--) {
        for (i = 0; i < N; i++) {
            scanf ("%d", &n[i]);
        }
        while (Q--) {
            count = 0;
            scanf ("%d %d %d", &a, &p, &q);
            p--;
            q--;
            for (i = p; i <= q; i++) {
                res[count++] = a ^ n[i];
            }
            max = res[0];
            for (i = count; i--;) {
                if (res[i] > max) { 
                    max = res[i];
                }
            }
            printf ("%d\n", max);
        }
    }
    return 0;
}

Извиняюсь за все произвольно названные переменные. Все эти проблемы просто используют одиночные имена символов в качестве их переменных.

11 голосов | спросил Ryan McClure 24 J000000Thursday14 2014, 22:49:32

1 ответ


5

То, что я закончил, заняло не более 0,27 для пробного № 10. Поскольку максимальное значение равно 32767, я просто создаю массив со структурой, в которой хранится список индексов, имеющих это значение:

typedef struct {
    int indexCount;
    int *indexes; // position (i.e. j) where number is
} NODE;

Затем в моем цикле я спускаюсь от максимально возможного значения до 0, xor его с помощью «a», чтобы получить значение x для поиска. Это индекс в массив узлов и быстро скажет, какие индексы (x 1 .. x N ) содержат это число.

for (largest = 32767; largest > 0; largest--) {
    v = largest ^ a; // value we're looking for
    // see if it has any indexes in range
    for (k = 0; k < nodes[v].indexCount; k++) {
        index = nodes[v].indexes[k];
        if (index >= p && index <=q) {
            found = 1;
            break;
        }
    }
    if (found)
        break;
}
printf("%d\n", largest);

У этого есть несколько примечаний:

  1. Он работает больше, поэтому количество тестов меньше
  2. Это только жизнеспособно из-за ограничения в значениях для x и a (0 <= x i <= 2 15 и 0 <= a i суб> & л; = 2 15 ). Если бы возможные значения были 2 31 , он мог бы занять 2 миллиарда раз.
  3. Он работает быстрее, когда конечные результаты больше. Случайная выборка значений в возможном диапазоне должна быть прекрасной, но может замедляться, если запрошенный диапазон не имеет ни одного из этих значений. Самыми плохими результатами будет большой список значений x, которые соответствуют a (дающий результат 0)

Я думаю, что лучшим решением будет дерево, где left означает, что число имеет «0» на этом бите, а справа означает, что число имеет «1» на этом бите. Листами будут значения x, следующие за этим битовым шаблоном. Каждый узел будет поддерживать диапазон индексов, где могут быть найдены числа ниже. Вы бы спустились по дереву с помощью напротив бит в значении a от бит 14 до тех пор, пока диапазон индекса узла перекрывается с p..q. Состав:

typedef struct {
    int indexCount;
    int capacity;
    int *indexes;
} INDEXLIST;

typedef struct {
    NODE *left, *right;
    int minIndex, maxIndex;
    INDEXLIST indexes;
} NODE;

Когда вы, наконец, достигнете дна со всеми 14 выбранными битами, эти биты составляют число и indexes в узле - это список индексов.

изменить

Я внедрил список ( ideone ) , если кто-то заинтересован, должен практиковать c, когда я могу ...

typedef struct {
    int count;
    int capacity;
    int *indexes; // position (i.e. j) where number is
} INDEXLIST;

typedef struct NODE_STRUCT {
    struct NODE_STRUCT *left, *right;
    int minIndex, maxIndex;
    int value; // for a leaf
    INDEXLIST *indexList; // for a leaf
} NODE;

Поэтому при загрузке x ​​ 1 .. x N я заполняю дерево, начиная с бит 14, и идя влево для 0 и справа для 1, расширяя ---- +: = 9 =: + ---- и minIndex для всех узлов в путь и только заполнение maxIndex и value для конечный узел.

При поиске максимального значения я пересекаю дерево в порядке поиска наивысшего результата xored. Например, если бит 14 значения indexList равен 1, я сначала лежу в поисках a с 0 в этой позиции. Если бит 13 равен 0, я сначала направо, ища код x с помощью x в этой позиции. Он обходит дерево в порядке, чтобы максимизировать полученное значение xored, поэтому, когда я достигаю листа, который содержит индекс в диапазоне, я возвращаю значение, которое я создал, на основе тех лево-правых вариантов, которые будут вставлены оригиналом значение xored с переданным значением 1.

a

У уникального значения может быть 96+ байтов служебных данных, не считая других узлов дерева, но он может обрабатывать больше бит с просто перекомпиляцией и намного эффективнее в разреженных списках, чем моя первая попытка ...

ответил Jason Goemaat 25 J000000Friday14 2014, 01:35:12

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132