ELEPHANT's blog

To xor or not to xor
By ELEPHANT, 12 years ago, In English

Hi

Any ideas how to solve this problem?

  • Vote: I like it
  • +13
  • Vote: I do not like it

»
12 years ago, # |
← Rev. 2   Vote: I like it +14 Vote: I do not like it

I think you can do such thing:

  1. Compose answer by getting maximum possible prefix of some size and appending 1 or 0 to it

  2. All that you need then is to be able to check whether some prefix can be obtained or not. To do that you can use linear equations modulo 2

→ Reply
»
12 years ago, # |
  Vote: I like it +5 Vote: I do not like it

After you break that one, you can try this one XMAX

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it 
//v is input array
long long ans = 0;
while (1)
{
    long long t = *max_element(all(v));
    if (t == 0) break;
    fori(sz(v))
        v[i] = min(v[i], v[i] ^ t);
    ans = max(ans, ans ^ t);
}
write ans;
→ Reply