1 / 2
Apr 2015

XMAX2 is a pretty straight forward problem and I am sure my algorithm is right. But I am getting a NZEC which I am not able to reproduce on my machine. Can any one throw some light ?
Is it because my I/O is slow or my algo is slow. I noticed that there are no successful submissions in Python, but wanted to give it a try.

def main():
    n = int(input())
    a = [0]*n
    for i in range(n):
        a[i] = int(input())
    a = sorted(a, reverse=True)
    print_array(a, 'After sorted')
    b = 63 # 2**63 > 10**18
    while 2**b & a[0] == 0:
        b -= 1
    # print(b)
    # gauss jordan elimination
    i = 0 # row
    while b >= 0 and i < n:
        # go row by row
        if 2**b & a[i] != 0:
            # eliminate this bit from all numbers below and above
            for j in range(n):
                if j != i and a[j] & 2**b != 0:
                    a[j] = a[j] ^ a[i]
            print_array(a, 'after b={}, i={}'.format(b, i))
            b -= 1 # move on to next bit
            i += 1 # move on to next row
        # see if you can pivot
        else:
            for j in range(i+1, n):
                if 2**b & a[j] != 0:
                    # swap these two
                    a[i], a[j] = a[j], a[i]
                    break
            else: # no such number with 1 at this bit
                # move on to next bit on the same row
                b -= 1
    # print numbers
    print_array(a, 'After Gauss')
    ans = 0
    for j in range(n):
            ans = ans ^ a[j]
    # print('Ans: {}'.format(ans))
    print(ans)
def print_array(a, s):
    # print(s)
    # for i, n in enumerate(a):
    #     print('{}: {:08b}'.format(i, n, n))
    pass
if __name__ == '__main__':
    main()
  • created

    Apr '15
  • last reply

    Apr '20
  • 1

    reply

  • 890

    views

  • 2

    users

  • 1

    link

5 years later

Your algo is correct. I am also facing the same issue. I tried the same code in CPP but got WA. I don’t know why :expressionless: