Submit solution

Points: 10
Time limit: 0.6s
Memory limit: 256M

Problem type

Given an array of length N, partition it into one or more contiguous groups. Once partitioned, take the XOR of the elements in each group. Compute the sum of these values. Bessie wants this sum to be minimal, Farmer John wants the sum to be maximal. Compute the difference between their sums.

Input Specification

The first line of the input will contain a single positive integer, N. You may assume N \le 10^5.

The second line of the input will contain N space-separated positive integers, the integers of the array in order. These positive integers will be less than 10^9.

Output Specification

Print on a single line the difference between the sums Bessie and Farmer John compute.

Sample Input

1 2 4 8 16

Sample Output



  • 30
    4fecta  commented on Jan. 15, 2020, 4:20 a.m.

    Fun relevant fact:

    XOR got the symbol \oplus from its similarity to the addition function. XOR essentially adds (+) the two bits at the same position of each number, then takes the result \bmod 2 (\bigcirc). Quite interesting!

    • 18
      magicalsoup  commented on Jan. 15, 2020, 4:48 a.m.

      Damn, 4fecta here spitting out cool facts. What a chad.

      • 14
        p1geon  commented on Jan. 15, 2020, 5:01 a.m.

        on god :pray:

        • 18
          Aaeria  commented on Jan. 15, 2020, 5:04 a.m.

          This sounds like an usaco problem lol