Code Jam 2019 Qualification Round "Dat Bae"

Dat Bae 문제의 풀이를 우연히 떠올리게 되어 F=5 테스트케이스도 맞췄는데 구글에서 제시한 풀이는 내 것과 사뭇 달랐다.
내 풀이는 딱 B<=16 인 경우에만 적용되지만 구글이 제시한 풀이는 B<32 도 된다!

내 풀이

첫번째 쿼리로 비트열을 구획화 한다. 이 구획화로 얻으려는 결과물은 보낸 비트열의 특정 구획이 받은 비트열의 어떤 구획과 대응되는지 알아내는 것이다. 이 정보를 토대로 그 구획에 해당되는 컴퓨터들 중 고장낸 것들의 "개수"를 알아낼 수 있다. (아직 어떤 컴퓨터인지는 모른다.)

000....00 을 보내면 어떻게 될까? 0의 개수만 줄어들은 0000....00 이 돌아온다. 이런 식으로 보내면 아무런 정보를 얻을 수 없다.

그래서 착안한 방법은 같은 개수의 연속된 0과 1이 번갈아가며 나타나는 비트열을 보내는 것이다. (ex 000111000111...) 0과 1로 구획 경계를 만드는 것이다. 이렇게 보내면 수신한 비트열도 0과 1이 번갈아가며 나타날텐데 다른 점은 고장난 컴퓨터들로 인해 구획별로 비트의 개수에 차이가 난다.그렇다면 이 개수를 새면 위에서 얘기한 구획별 고장난 컴퓨터들의 개수를 알아낼 수 있다.

그런데 고려해야할 엣지케이스가 있다.

000111000111000111 을 보냈는데 두번째 000111에 해당하는 컴퓨터들이 죄다 고장났다면 000111000111이 돌아올텐데 첫번째나 세번째 000111을 삭제시켜도 같은 비트열을 만들어낸다. 모호성: 고장난 컴퓨터들의 위치를 확정지을 수 없다.

위의 문제는 단위 구획의 크기를 늘려서 해결 할 수 있다. B=6이라면 구획의 크기를 6으로 주면 된다. (000000111111...) 만약 고장난 컴퓨터 6개의 위치들이 111111 라면 000000000000 같은 패턴이 나타날텐데 구획의 크기는 6이므로 고장난 컴퓨터는 저 12개의 0비트의 한가운데임을 쉽게 알 수 있고 만약 앞선 예시같이 몰려있지 않다면 구획에 적어도 1개 이상의 비트가 살아남아 수신되므로 구획별 고장난 컴퓨터의 개수를 알 수 있다.

구획별 고장난 컴퓨터의 개수를 알아냈다. 원래의 problem의 여러 개의 subproblem으로 쪼개졌다. 각 subproblem은 보내는 비트열의 길이가 B이다. 보낸 비트열의 개수가 B/2, B/4, ... 인 subproblem들로 쭉쭉 내려간다.
종국에는 보내는 비트열이 01이 될 것이고 고장난 컴퓨터의 위치를 확정지을 수 있다.
왜 내 풀이가 B<=16일 때만 적용되나? 첫번째 구획화를 할 때 1회 쿼리, 그 다음 subproblem으로 쪼갤 때 할 수 있는 쿼리의 최대 횟수는 4회이다. 이 4회만에 크기가 1인 subproblem에 도달해야 한다. 그래서 2^4=16 인 것이다.
(edit) 다시 분석해보니 내 풀이도 16<B<32 인 경우에도 적용할 수 있다는 것을 알아냈다. 01이 가장 마지막으로 전송하는 비트열의 패턴이므로 F=5면 처음에 00000000000000001111111111111111 (총 길이 32)을 보낼 수 있다.

구글의 풀이

내 풀이가 모범답안이라 확신하고 채점이 끝난 뒤 올라온 구글의 풀이를 봤더니 우와소리가 나오는 방법을 썼다!
구글은 F번의 쿼리를 보내면 각 컴퓨터를 F개의 비트열로 특정할 수 있음에 착안했다. (이 부분을 처음 읽을 때 소름이 돋았다)

첫번째 테스트케이스의 경우에는 1024개의 컴퓨터를 F=10 번의 쿼리를 보내 각 컴퓨터별로 유일한 비트열(값으로 따지면 0 ~ 1023이다)을 부여한 다음 수신 받은 비트열로 재구성을 했을 때 존재하지 않는 비트열들에 해당되는 컴퓨터가 고장났음을 알아냈다.

두번째 테스트케이스는 5번의 쿼리만이 주어진다. 이젠 0 ~ 31 밖에 부여하지 못한다. 이번 풀이는 내 풀이 중 구획화와 비슷한 부분이 있다. 1024개의 컴퓨터에 0, 1, ..., 31, 0, 1, ..., 31, ..., 0, 1, ..., 31 을 부여한다. 여기서 최대 31개의 연속된 위치의 컴퓨터가 죽어도 어떤 구획의 마지막 정상 컴퓨터의 번호은 그 다음 구획의 첫 정상 컴퓨터의 번호보다 항상 크거나 같다. 당장 1, 2, 3, ..., 31 을 고장내봐도 0, 0, 1, ..., 31 으로 첫번째 0과 두번째 0 사이에서 구획이 달라짐을 알 수 있다. 연속된 32개가 죽는 경우는 처리할 수 없다. (내 풀이에서 언급한 모호성이 있다)