Return to Answer

added another example

Source Link

edited Jul 24, 2014 at 23:48

edit

I implemented the list (ideone) if anyone's interested, gotta practice c when I can...

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;

So when loading the x₁..x_N, I populate the tree starting at bit 14 and going left for a 0 and right for a 1, expanding minIndex and maxIndex for all the nodes in the path and only populating value and indexList for the final node.

When searching for a maximum value, I traverse the tree in the order of looking for the highest resulting xored value. For instance if bit 14 of the a value is 1, I go left first looking for x values with a 0 in that position. If bit 13 is 0, I then go right first looking for an x with a 1 in that position. It traverses the tree in the order to maximize the resulting xored value, so when I reach a leaf that contains an index in range, I return the value I've built-up based on those left-right choices which will be the original inserted value xored with the a value passed.

NODE *add_index_to_node(NODE *node, int index, int value, int depth);
int find_largest(NODE *node, int value, int minIndex, int maxIndex, int depth);

while (T--) {
    scanf("%d %d", &N, &Q);
    for (i = 1; i <= N; i++) {
        scanf("%d", &x);
        root = add_index_to_node(root, i, x, 0);
    }

    for (i = 0; i < Q; i++) {
        scanf("%d %d %d", &a, &p, &q);
        result = find_largest(root, a, p, q, 0);
        printf("%d\n", result);
    }

    // free memory
    free_node(root);
    root = NULL;
}

A unique value could have 96+ bytes of overhead not including the other tree nodes, but it could handle more bits with just recompiling and is a lot more efficient at sparse lists than my first try...

edit

I implemented the list (ideone) if anyone's interested, gotta practice c when I can...

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;

NODE *add_index_to_node(NODE *node, int index, int value, int depth);
int find_largest(NODE *node, int value, int minIndex, int maxIndex, int depth);

while (T--) {
    scanf("%d %d", &N, &Q);
    for (i = 1; i <= N; i++) {
        scanf("%d", &x);
        root = add_index_to_node(root, i, x, 0);
    }

    for (i = 0; i < Q; i++) {
        scanf("%d %d %d", &a, &p, &q);
        result = find_largest(root, a, p, q, 0);
        printf("%d\n", result);
    }

    // free memory
    free_node(root);
    root = NULL;
}

Source Link

created Jul 24, 2014 at 21:35

Jason Goemaat

What I ended up doing took at most 0.27s for trial #10. Since the maximum value is 32767, I just create an array with a structure that stores a list of indexes that have that value:

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

Then in my loop, I loop down from the largest possible value to 0, xor it with 'a' to get the value of x to look for. That is the index into the array of nodes and will tell me quickly which indexes (x₁..x_N) contain that number.

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);

This has a couple of notes:

It does more work up front so the number of tests are affected less
It's only viable because of the restriction in values for x and a (0<=x_i<=2¹⁵ and 0<=a_i<=2¹⁵). If the possible values were 2³¹ it could loop 2 billion times.
It works fastest when the final results are larger. A random sampling of values in the possible range should be fine but could slow down if the requested range has none of those values. The poorest results would be a large list of x values that match a (giving a result of 0)

I think a better solution would be a tree where left means the number has a '0' at that bit and right means the number has a '1' at that bit. The leaves would be the x values following that bit pattern. Each node would maintain the index range where numbers below could be found. You would walk down the tree using the opposite of bits in the a value from bit 14 down as long as the node's index range overlaps with p..q. Structure:

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

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

When you finally reach the bottom with all 14 bits chosen, those bits make up the number and indexes in the node is the list of indexes.