OJ Board

Posted: **Sat Oct 22, 2005 2:07 am**

Can anybody help me with the following problem. I use brute force but I got timeouts. Any ideas of possible optimisations?

Here is the problem statement:
Cow XOR
Adrian Vladu -- 2005

Farmer John is stuck with another problem while feeding his cows. All of his N (1 ≤ N ≤ 100,000) cows (numbered 1..N) are lined up in front of the barn, sorted by their rank in their social hierarchy. Cow #1 has the highest rank; cow #N has the least rank. Every cow had additionally been assigned a non-unique integer number in the range 0..(2^21 - 1).

Help FJ choose which cows will be fed first by selecting a sequence of consecutive cows in the line such that the bitwise "xor" between their assigned numbers has the maximum value. If there are several such sequences, choose the sequence for which its last cow has the highest rank. If there still is a tie, choose the shortest sequence.
PROGRAM NAME: cowxor
INPUT FORMAT

* Line 1: A single integer N
* Lines 2..N+1: N integers ranging from 0 to 2^21 - 1, representing the cows' assigned numbers. Line j describes cow of social hierarchy j-1.

SAMPLE INPUT (file cowxor.in)

5
1
0
5
4
2

INPUT DETAILS:
There are 5 cows. Cow #1 had been assigned with 1; cow #2 with 0; cow #3 with 5; cow #4 with 4; cow #5 with 2.
OUTPUT FORMAT

* Line 1: Three space-separated integers, respectively: the maximum requested value, the position where the sequence begins, the position where the sequence ends.

SAMPLE OUTPUT (file cowxor.out)

6 4 5

OUTPUT DETAILS:
4 xor 2 = 6 (001) xor (010) = (011)

Thanks for any replies.

Posted: **Sat Oct 22, 2005 10:35 pm**

Here's my solution for your problem. It takes O(nm+2^m) time, O(2^m) space, where m=21.

Code: Select all

/* let a[0], a[1], ..., a[n-1] be the sequence of cows' assigned numbers
   let b[k] = a[0] xor a[1] xor ... xor a[k-1], for k=0..n
   then a[i] xor a[i+1] xor ... xor a[j-1] = b[i] xor b[j]

   the problem reduces to finding a pair of integers (i,j), s.t.
     a) 0 <= i <= j <= n
     b) b[i] xor b[j] is maximized
     c) j is minimized
     d) i is maximized
   the answer to the original problem is the segment a[i]...a[j-1] */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

#define M       21              /* number of bits in cows' assigned numbers */
#define MAXN    100005
#define INF     0x7FFFFFFF

int a[MAXN], b[MAXN], c[(1 << M) + 1], d[MAXN], e[(1 << M) + 1], n;
int bestx, bestj;

int cmp(const void *p, const void *q) { return *(int *)p - *(int *)q; }

int main()
{
        int i, j, k;

        freopen("cowxor.in", "r", stdin);
        /*freopen("cowxor.out", "w", stdout);*/

        scanf("%d", &n);
        assert(1 <= n && n < MAXN);
        for (i = 0, b[0] = 0; i < n; i++) {
                scanf("%d", &a[i]);
                assert(0 <= a[i] && a[i] < (1 << M));
                b[i+1] = b[i] ^ a[i];
        }

        /* Compute c[k] = |{i: 0 <= i <= n, b[i] < k}|, for k=0..2^M */
        memcpy(d, b, (n+1) * sizeof(b[0]));
        qsort(d, n+1, sizeof(d[0]), &cmp);
        for (d[n+1] = INF, i = j = 0; i <= n;) {
                while (d[i] >= j) c[j++] = i;
                while (d[i] < j) i++;
        }
        while (j <= (1 << M)) c[j++] = i;

        /* Compute e[k] = min {i: 0 <= i <= n, b[i] = k }, for k=0..2^M */
        for (i = 0; i <= (1 << M); i++) e[i] = INF;
        for (i = 0; i <= n; i++) if (e[b[i]] > i) e[b[i]] = i;

        bestx = bestj = 0;
        for (j = 1; j <= n; j++) {
                /* find an integer k such that k xor b[j] is maximized and
                   c[k+1]-c[k] > 0  (i.e. there exists x, s.t. b[x]=k) */
                for (k = 0, i = M-1; i >= 0; i--)
                        if ((c[k+(1<<(i+1))] - c[k+(1<<i)]) > 0 &&   /* if i-th bit may be 1, and */
                            ((c[k+(1<<i)] - c[k]) == 0 ||            /* (it cannot be 0, or */
                             ((b[j] >> i) & 1) == 0))                /* it's desirable it's 1), */
                                k |= 1 << i;                         /* set i-th bit */
                assert(e[k] < INF);

                if (e[k] >= j || (k ^ b[j]) <= bestx) continue;
                bestj = j;
                bestx = k ^ b[j];
                if (bestx == ((1 << M) - 1)) break;
        }

        for (i = j = bestj; i >= 0 && (b[i] ^ b[j]) != bestx; i--);
        assert(i >= 0 && (b[i] ^ b[j]) == bestx);
        printf("%d %d %d\n", bestx, i+1, j);

        return 0;
}

Posted: **Sun Oct 23, 2005 4:29 am**

Hi. Thanks for your reply. So now I realized that my problem wasn't really a problem. I thought that 1<<21 is too much space but it's ok on usaco machinges. However, it gives errors on my machine. Does anybody know how to fix that? I guess there is some kind of flag that reduces it.

Posted: **Sun Oct 23, 2005 3:41 pm**

Could you describe in detail what kind of errors you have?
If it's something with your solution, could you also describe your algorithm or post its code?

Posted: **Sun Oct 23, 2005 3:59 pm**

Oh, there is no problem actually. I was solving that problem under winxp cause my linux box was 'injured' for a moment. WinXp is so memory devouring that I didn't have place to allocate 1<<21 integers which lead my to asking that question. Now everything is ok. Thanks again for your reply.

OJ Board

USACO --- cowxor

USACO --- cowxor