하나 둘 셋 2

크기 $p$인 그룹에 $2$가 $c$개 들어간다면 $0,1,2$의 개수는 각각 $p-q+c$, $q-2c$, $c$여야 한다. 따라서 $0\le c\le\lfloor q/2\rfloor$이고, 모든 크기 $p$인 그룹에서 $c$의 합을 $C-\lambda q$로 맞추면 된다. $\lambda$의 정의로부터 항상 가능하다.

각 그룹은 정확히 그룹 크기에서 $1$을 뺀 횟수만큼의 연산으로 평균화할 수 있다. 크기 $p$인 그룹은 $0,1,2$로 이루어지고 합이 홀수이다. 크기 $2p$인 그룹은 모든 값을 $2$로 나누면 합이 홀수인 $0,1$ 그룹이 된다.

크기가 $D=2^k$이고 원소가 $0,1,2$이며 합이 홀수 $q$인 그룹을 생각하자. 연산을 거꾸로 구성한다. 처음에는 최종 평균 $q/D$가 $D$개 있다고 생각한다. 같은 값 $x$ 두 개를 골라 하나를 원래 정수 $a\in\{0,1,2\}$로 확정하고, 다른 하나를 $2x-a$로 되돌리면 평균 연산 하나를 역으로 복원할 수 있다.

현재 활성 원소의 수가 $D$일 때 $r=q\bmod D$라고 하자. 모든 활성 값의 소수 부분은 $r/D$이므로 활성 값은 $r/D$와 $1+r/D$ 두 종류뿐이다. 높은 값의 개수를 $H$라고 하고 같은 종류끼리 두 개씩 묶는다.

• $r<D/2$이면 낮은 쌍은 $0$을 하나 확정하고 낮은 값 하나를 남긴다. 높은 쌍은 $1$을 확정해 높은 값을 남기거나, $2$를 확정해 낮은 값을 남길 수 있다.
• $r>D/2$이면 높은 쌍은 $2$를 하나 확정하고 높은 값 하나를 남긴다. 낮은 쌍은 $1$을 확정해 낮은 값을 남기거나, $0$을 확정해 높은 값을 남길 수 있다.

다음 단계의 활성 원소는 $D/2$개이다. 각 상태 $(D,H)$에서 앞으로 복원할 수 있는 남은 $2$의 개수는 하나의 정수 구간을 이룬다. $D=2$에서는 $(H,c)=(0,0)$ 또는 $(2,1)$이고, 위 전이로 작은 $D$부터 구간을 계산할 수 있다. 접두·접미 최솟값과 최댓값을 사용하면 한 레벨을 $O(D)$에 계산할 수 있고, 모든 레벨의 크기 합도 $O(D)$이다. 복원할 때는 다음 상태가 가능한 구간 안에 남는 전이를 하나 고른다. 기록한 역연산의 순서를 뒤집으면 $D-1$번의 정방향 연산을 얻는다.

$i$번째 연결 요소에 처음 $2$가 $c_i$개 있었다면 그 연결 요소의 합은 $qs_i$이므로 $c_i\le\left\lfloor\dfrac{qs_i}{2}\right\rfloor$이다. $q$가 홀수이므로 다음이 성립한다.

따라서 $k\le g-\lambda$이다. 한 연결 요소를 만들려면 적어도 그 크기에서 $1$을 뺀 만큼의 연산이 필요하므로 전체 연산 수는 적어도

이다.