$0$ 이상 $2^{15}$ 미만의 서로 다른 정수 $N$개로 이루어진 집합 $A$와 $B$가 주어진다. 한 번의 조작으로 $A$의 원소를 하나 골라 비트를 하나 변경할 수 있는데, 그 결과가 $A$에 이미 있는 값이면 안된다. $2^{19}$회 이하의 조작으로 $A$를 $B$로 바꾸는 방법을 하나 찾아 출력하시오.

분석

가능한 조작이 최대한 한정적인 상황을 생각해 보자. 조작이 한정적이려면 집합의 크기가 가능한 커야 한다.

$N = 2^{15}$이면 빈 자리가 1개도 없으므로 아무것도 조작할 수 없지만, $A = B$가 보장되므로 0을 출력하면 된다.

$N = 2^{15} - 1$인 경우, $A = U - {x}$, $B = U - {y}$로 둘 수 있다. ($U$는 $0$ 이상 $2^{15}$ 미만의 모든 정수의 집합이다.) 두 집합이 같으면 역시 자명하므로, $x \neq y$라고 하자. 그러면 가능한 조작을 가지고 $y$를 $x$로 바꾸어야 한다. 둘이 비트 1개 차이라면 자명하지만, 비트가 여러 개가 다르면 어떻게 할 것인가?

아이디어

$y$를 $x$로 바꾸기 위해서 거쳐야 하는 수의 목록을 $y, a_1, a_2, \cdots, a_k, x$라고 하자. 이 목록에 있는 수는 한 번의 조작으로 이웃한 수로 바꿀 수 있다. 단, 그 이웃한 수가 $A$에 없어야 한다. 현재 상태는 $y, a_1, a_2, \cdots, a_k$는 $A$에 있고, $x$만 $A$에 없는 상태이다. 각 수를 그 수가 $A$에 있는지를 나타내는 true/false로 바꾸면, 한 번의 조작으로 (true, false)를 (false, true)로, 또는 그 반대로 바꿀 수 있다. 최종적으로는 $a_1, a_2, \cdots, a_k$의 true/false는 그대로 두고, $y$는 false, $x$는 true인 상태로 이동하면 된다.

이를 실행하는 방법은 의외로 간단하다. 가장 오른쪽의 true부터 $x$ 자리로 옮겨주고, 그 왼쪽 true를 오른쪽 true가 빠진 자리로 옮기고, …를 반복하면 된다.

0 1 3 7
o o o x
operation: 3->7
o o x o
operation: 1->3
o x o o
operation: 0->1
x o o o

이는 $a_i$들 중에서 일부만 true인 경우에도 똑같이 적용할 수 있다.

0  1  3  7 15 31
o  x  o  o  x  x
operation: 7->15
o  x  o  x  o  x
operation: 15->31
o  x  o  x  x  o
operation: 3->7
o  x  x  o  x  o
operation: 0->1
x  o  x  o  x  o
operation: 1->3
x  x  o  o  x  o

이렇게 하면 정확히 서로 다른 비트의 개수만큼의 조작으로 원하는 상태에 도달할 수 있음 또한 알 수 있다.

이제 현재 상태가 어떻든 상관없이 $A$에 있는 수 $x$를 $A$에 없는 수 $y$로 15회 이내에 바꿀 수 있다. $A$와 $B$는 최대 $2^{14}$개 원소가 다를 수 있으므로, $A$에만 있는 원소 $x$와 $B$에만 있는 원소 $y$를 임의로 짝지어서 순서대로 바꿔주면 조작 횟수 제한 이내에 목표를 달성할 수 있다.