[IOI 2024] Message

문제: (oj.uz) https://oj.uz/problem/view/IOI24_message (acmicpc.net) https://www.acmicpc.net/problem/32265

문제의 풀이의 설명은 여러 Editorial에도 많이 설명이 되어 있기에, 생각 과정 위주로 시간 순으로 적어보겠습니다. 

보내야하는 정보의 양

"길이 $N$ 이하의 메세지를 보낼 수 있다." 라는 말은 "길이 $N+1$의 메세지를 보낼 수 있다" 라는 말과 거의 비슷합니다. $2^0 + 2^1 + 2^2 + \cdots + 2^N = 2^{N+1} -1$이고, 보통 다음과 같이 인코딩/디코딩을 하는 것 같습니다.

• 길이 $K$의 메세지를 보내기 위해서는 $K$번째 비트를 $1$로 채우고, 하위 비트를 길이 $K$의 메세지로 채운다.
• $N+1$의 메세지에서 길이와 메세지를 복구하기 위해서는 첫째의 $0$이 아닌 비트를 찾는다.

이 문제에서는 총 $1025$ 비트를 보내야합니다.

보내는 정보의 종류와 인코딩 여유공간에 대해

이 문제에서 보내야하는 정보는 $1025$비트짜리 메세지 하나입니다. 그리고, 우리가 보낼 수 있는 순수한 정보의 양은 $C$를 서로 안다고 가정했을 때 $16 \times 66 = 1024 + 32$입니다. $31$비트에 에러를 수정할 수 있는 정보를 담아야합니다.

$C$에 대한 정보를 보내지 않아도 된다고 생각해봅시다. Cleopatra는 마치 $C$가 다른 배열인것처럼, 원래 컨트롤 할 수 있는 위치가 컨트롤 하지 않는 것으로 보이도록 프로토콜을 조작해서 보낼 수 있습니다. 그렇기 때문에, $C$의 정보를 보내는 것이 필요했습니다.

$C$로 가능한 경우의 수가 $3 \times 10^8$정도 ($28$비트 정도)이기 때문에 메세지를 보낼 때 정보를 낭비할 수 없겠다고 생각했습니다. 이제, $C$를 보내는 일에 집중해야한다고 생각했습니다.

Cleopatra가 항상 비트를 랜덤으로 뒤집도록 할 수 있다

이건 제가 인코딩, 디코딩 문제에서 항상 생각해보는데, 일반적으로 적응적인 것보다 적응적이지 않은 것에서 쓸 수 있는 트릭이 더 많고, 필요하면 높은 확률로 문제를 풀 수 있도록 만들 수 있습니다. OTP와 유사한 기법을 사용하면 Cleopatra의 코드를 (사실상) 적응적이지 않도록 할 수 있습니다. 다음과 같은 전략을 실행합니다. (실제로 OTP는 아닙니다.)

1. 보내지는 메세지 $31 \cdot Q$개에 대해, 랜덤으로 $0$ 혹은 $1$을 할당하고, Aisha와 Basma는 해당 비트를 공유합니다.
2. Aisha는 보낼 때 메세지를 보낼 때 해당 비트를 XOR해서 보냅니다. Cleopatra가 컨트롤 하는 비트에 대해서는 비트를 랜덤으로 설정합니다.
3. Basma는 받은 후 해당 비트를 XOR합니다.

이렇게 한 경우 Cleopatra는 내부 통신에 대해서 알 수 없으며, Cleopatra가 뒤집는 비트는 랜덤으로 설정된 비트가 됩니다. 사실상 Cleopatra의 역할을 비트를 랜덤으로 뒤집도록 강제할 수 있습니다. 이를 항상 염두에 두고 아래 생각들을 했습니다.

중간에 한 시도들에 대해

대부분 글들이 다른 중간에 한 시도들을 다루지 않기 때문에 다루어보겠습니다.

send_packet의 리턴값에 대한 고찰

저는 send_packet의 리턴값을 생각보다 중요하게 생각했습니다. send_packet의 리턴값을 토대로 다음에 보낼 $A_i$를 바꿔볼까 같은 생각들을 했습니다. send_packet의 리턴값을 xor해서 넣으면 B에 어떤 필드가 바뀌었는지에 대한 추가적인 정보를 줄 수 있지 않을까?와 같은 생각도 했는데, 이는 기본적으로 A와 B모두가 같이 아는 키를 가지고 암호화 하는 것과 다르지 않았습니다. 지금 와서 생각해보면, send_packet의 리턴 값을 기준으로 주는 정보의 종류를 다르게 하는 것은 의미가 있을 지 모르겠지만, 정보를 쓰는 방법을 다르게 하는 것은 별로 의미가 없는 행위 같습니다.

$C$의 필드를 짝짓기

또 다른 시도는 올바른 정보를 주기 위해, 필드들을 짝지어보자라는 생각을 했습니다. 올바르게 전달되는 필드가 과반이기 때문에 적어도 한 짝은 올바르게 전달되는 필드의 짝이라고 생각했습니다. 이 방법도 바로 실패했는데, 가장 큰 이유는 올바른 짝과 틀린 짝을 구분할 수 없었기 때문입니다. 클레오파트라가 마치 틀린 짝을 올바른 것처럼 바꿀 수 있습니다.

이런 슬픈 시도들이 있었습니다...

$C$를 보내는 방법에 대해

(편의상 $X_i$는 $X_{i \bmod \lvert X \rvert}$입니다.)

가장 먼저 생각해 본 방법은, $C$ 자체의 특징을 이용하는 것입니다. 첫 메세지로 $A_i = C_{i+1}$과 같은 형태의 메시지를 보낸다고 해봅시다. 이 경우 연속된 올바른 위치는 $0...01$과 같은 형태로 표현이 됨을 알 수 있습니다. 이 방법의 문제는 클레오파트라가 $0..01$과 같은 메세지를 넣을 수 있다는 것입니다.

이를 막기 위해서 다음에 생각했던 방법은 $A_i = C_{i-1}$과 같은 형태의 메세지를 넣는 것입니다. 이 경우 올바른 연속된 위치의 첫 패킷은 $0...01$, 두번째 패킷은 $10...0$이 될 것입니다. 이 방법도 역시 클레오파트라가 같은 방법으로 메세지를 속일 수 있습니다.

이 방법의 가장 큰 문제는 $0...01$ 과 같은 인코딩에서 $0...0$ 부분이 길어지면 정보를 상대적으로 주고 있지 않고, $1$이 가리키는 정보가 결론적으로 랜덤한 정보라는 것이었습니다. 올바른 정보를 한 번 찾기 시작하면, 계속 올바른 정보를 주는 것이 좋겠다는 생각을 했습니다.

$Q = 68$

$A_i = C_{i+1}$을 확장해서, $N_i =$ 다음으로 오는 $(C_j=0)$인 $j$에 대해 $j-i-1$로 합니다. $N_i$가 $15$이하이기 때문에, $4$비트를 사용해서 인코딩 할 수 있습니다. 이것을 찾는 방법은 $i \rightarrow i + N_i + 1$과 같은 형태로 그래프를 그리면 됩니다. 모든 정점의 outdegree가 $1$인 그래프인 functional graph가 나오고, 이 그래프에서 길이 $16$의 사이클은 단 하나만 존재할 수 있기 때문에, 해당 사이클이 정답인 사이클일 것입니다. 뭐 어떻게든 $1$비트는 보낼 수 있을 것 같아서, 이걸 구현하면 $Q = 68$을 받겠구나 하고 생각했습니다.

$Q = 66$

이제 문제는 $N_i$의 가장 상위 비트가 너무 $0$이 많다는 것이었습니다. $N_i$의 최상위비트는 $0$이 $0$개 혹은 $1$개였고, 이는 패킷 하나를 낭비하는 거였습니다. 이를 위해 생각한 아이디어가 $2$개 있습니다.

1. 이미 정보가 결정이 된 비트에 대해서는 여기에다가 $M$의 정보를 채워넣기 시작하자라는 것이었습니다. 굳이 $0$으로 정보를 채울 필요 없이, $M$의 정보를 어느 순간부터 써나가면 됩니다.
2. $N_i$를 $0, 1, 2, 3, \cdots, 15$로 표현하는 것에서 $0, 1, 2, \cdots, 6, 7$이상 으로 바꾸는 것이었습니다. $N_i$의 합이 $15$이기 때문에, 저걸 잘 쓰면 하나를 더 아낄 수 있을 것 같았습니다. (사실 생각할 때는 $8$이상이어서, 저게 최대 $1$개인줄 알았습니다...)

이걸 이용해서 좀 더 생각을 해 보았습니다. 일단 $N_i = 0$인 것들이 많기 때문에, $0$인 것과 $0$이 아닌 것을 구분합니다.

그 다음에 send_packet의 리턴값을 알기 때문에 functional graph의 정해진 값과 정해지지 않은 값을 줄 수 있습니다. 이제, 나머지 간선을 어떻게 그을까...하고 고민을 하던 중 $N_i = 1$인것과 아닌 것을 구분하는 정도밖에 못하겠다는 생각을 했습니다.

 

구현 디테일을 생각해보니, $N_i$를 $0$을 $N_i$개 쓴 이후 $1$을 쓰는 방식으로 인코딩 하는 것을 알았습니다. 이 경우, $N_i$의 합이 $15$이기 때문에 모든 $N_i$를 보내는데 총 $31$개의 비트를 사용하는 것을 알았습니다. 풀이를 정리하면 다음과 같습니다.

Aisha

1. 모든 $C_i = 0$인 $i$에 대해 바로 직후에 오는 $C_j = 0$을 찾고, $N_i = j-i-1$이라고 정의합니다.
2. 모든 $C_i = 0$인 $i$에 대해 처음 $N_i$번 동안은 $0$을 보냅니다. 다음 $1$번은 $1$을 보냅니다.
3. 나머지 $66 \times 16 - 31 = 1025$개의 비트는 위의 "보내야 하는 정보의 양"과 같이 $M$을 인코딩 한 이후, 차례대로 써서 보냅니다.

Basma

1. 모든 $i$에 대해, 처음으로 받은 $1$비트의 위치를 센 이후, $k_i$번째에 등장했다면 $i \rightarrow (i + k_i) \mod 31$로 functional graph를 긋습니다.
2. 길이 $16$인 사이클을 찾습니다.
3. 처음에 나온 $1$까지는 무시하고, 그 이후에는 정보를 받아서 $1025$개의 비트를 적은 이후, 위의 적힌 방법과 같이 $M$을 디코딩합니다.

코드는 다음과 같습니다: https://oj.uz/submission/1311666