Google Kick Start 2019 Round D - X or What?

 

https://codingcompetitions.withgoogle.com/kickstart/round/0000000000051061/0000000000161426

Kick Start - Google’s Coding Competitions

 

자연수 i를 이진수로 표현했을때 1의 갯수를 n(i)라고 표시해보자. 두개의 숫자를 xor하는 경우를 생각해보면 홀짝의 경우에 따라 4가지의 경우가 존재한다.

1. n(i) 홀수, n(j) 홀수

  -> n(i xor j) 짝수

2, 3. n(i) 홀수, n(j) 짝수, n(i) 짝수, n(j) 홀수

  -> n(i xor j) 홀수

4. n(i) 짝수, n(j) 짝수

  -> n(i xor j) 짝수

가 성립한다.

이는 조금만 생각하면 알수있는데 n(i)를 0과 xor을 한다고 생각해보자.

0100010
0000000
-------
0100010

이런식으로 아무것도 변하지 않는다. 그렇다면 n(j)가 1인 경우를 생각해보자.

0100010
0000001
-------
0100011

0100010
0000010
-------
0100000

이런식으로 한개의 0의 1로 되거나 1개의 1이 0으로 된다. 즉 n(i xor j) if n(j)=1는 홀짝이 뒤바뀐다.

같은 논리로

n(j)가 짝수면 n(i xor 0)의 결과와 비교해 짝수개의 1이 0이되거나 0이 1이되어 n(i xor j)의 홀짝이 바뀌지 않고

n(j)가 홀수면 n(i xor 0)의 결과와 비교해 홀수개의 1이 0이되거나 0이 1이되어 n(i xor j)의 홀짝이 뒤바뀐다.

 

문제의 결국 조건인 xor_even를 만족하려면 짝수개의 n(i)가 홀수인 원소를 가진 subinterval를 구해주면 된다. 이때 가장 긴 subinterval를 구해주는 방법은 매우 쉬운데 n(Ai)가 홀수일때 그것의 위치를 저장해두는 것이다.

만일 위치를 저장해놓은 배열의 길이가 짝수라면 A 전체에 n(i)가 홀수인것이 짝수개 존재하는 것이므로 A 전체가 xor_even이다. 하지만 배열의 길이가 홀수라면 n(Ai)가 홀수인것들중 하나를 빼면 그 이후나 이전의 subinterval은 xor_even이 된다.

len(odd_pos)가 홀수이고 n(Ai)가 홀수일경우

A1 A2 A3 A4 ... Ai-1 Ai Ai+1 Ai+2 ... Ak

n(i)가 홀수인 수가 짝수개이므로 n(A1 xor A2 xor A3 xor ... xor Ai-1)은 짝수
n(i)가 홀수인 수가 짝수개이므로 n(Ai+1 xor Ai+1 xor ... xor Ak)은 짝수

그러므로 그냥 처음부터 n(Ai)가 홀수인것의 위치가 아니라 i - 1과 len(A) - i중 큰 것을 저장해두고 그것들중 최댓값이 가장 긴 xor_even인 subinterval이 된다.

 

Ai를 q로 변경할대 만약 n(Ai)와 n(q)가 홀짝이 같다면 전체적인 홀짝은 변하지 않게된다. n(Ai)와 n(q)가 홀짝이 다르다면 n(q)가 홀수일경우 n(Ai)는 짝수이므로 odd_pos배열에 i - 1과 len(A) - i중 큰 것을 추가하면되고 n(q)가 짝수일경우 n(Ai)는 홀수이므로 i - 1과 len(A) - i중 큰 것을 odd_pos배열에서 삭제하면 된다.

import bisect

def is_odd(x):
    return bin(x)[2:].count('1') % 2 == 1

T = int(input().strip())
for t in range(T):
    [N, Q] = list(map(lambda x: int(x), input().strip().split(' ')))
    A = list(map(lambda x: int(x), input().strip().split(' ')))
    odd_pos = []
    result = []

    for i, a in enumerate(A):
        if is_odd(a):
            bisect.insort(odd_pos, max(N - i - 1, i))

    for _ in range(Q):
        [i, q] = list(map(lambda x: int(x), input().strip().split(' ')))
        if is_odd(A[i]) == False and is_odd(q) == True:
            bisect.insort(odd_pos, max(N - i - 1, i))
        elif is_odd(A[i]) == True and is_odd(q) == False:
            odd_pos.pop(bisect.bisect(odd_pos, max(N - i - 1, i)) - 1)

        A[i] = q

        if len(odd_pos) % 2 == 0:
            result.append(N)
        else:
            result.append(odd_pos[-1])

    print('Case #%s: %s' % (t + 1, " ".join(map(lambda x: str(x), result))))

여기서 주의해야할점은 만일 odd_pos를 bisect를 쓰지 않고 마지막에 가장 긴 subinterval을 계산할때

result.append(sorted(odd_pos)[-1])

이런식으로 그때그때 정렬을 한다면 시간복잡도가 O(qnlogn)이 되어버려 시간초과가 된다는 것이다.