[Code Jam Qualification Round 2020] ESAb ATAd

문졔 :

https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd27/0000000000209a9e

 

---

B개의 비트가 있다.

B는 주어지지만 비트 정보는 주어지지 않는다.

 

인터렉션으로 P를 입력하면, P번째 위치의 비트를 알 수 있다.

• P는 1-indexed

1번째, 11번째, 21번째, ... , \(10n+1\)번째 인터렉션마다 비트를 알려주기 전에 B개의 모든 비트에 대하여 다음 연산이 수행 된다.

• 25% 확률로 모든 0은 1이 되고, 모든 1은 0이 된다.(flip)
• 25% 확률로 비트의 순서가 반대가 된다.(reverse)
• 25% 확률로 상기 두 연산이 모두 수행된다.
• 25% 확률로 어떤 연산도 수행되지 않는다.

위 연산이 수행된 후에 P위치의 비트를 알려준다.

 

인터렉션을 이용하여 비트를 구하는 문제

• 인터렉션을 10번 수행할 때마다 비트가 바뀌는데, 정답 출력 시점에서의 비트를 출력하면 된다.

 

제약 

• 인터렉션은 최대 150번 수행 가능
• Subtask
  1. B=10
  2. B=20
  3. B=100

 

---

풀이

Subtask 1

인터렉션을 10번 수행하면 된다.

첫 인터렉션에서 연산이 수행되지만, 인터렉션을 11번까지 수행하지 않으므로 10개 비트를 찾을 때까지 비트는 변하지 않는다.

 

---

Subtask 2

비트의 가운데를 기준으로 왼쪽 비트 10개, 오른쪽 비트 10개를 대칭적으로 보자

총 10개의 비트 쌍이 나온다.

비트 쌍 단위로 인터렉션을 수행해보자

그리고 10개의 비트 쌍 중에서 값이 같은 비트 쌍과 값이 다른 비트 쌍을 찾는다.

 

인터렉션이 20번 수행되는 동안, 비트 값이 바뀔 수 있지만 비트 쌍의 parity는 변하지 않는다.

 

parity가 같은 경우

 

parity가 다른 경우

 

위 성질을 이용하여 \(10n+1\)번째 인터렉션 마다, reverse와 flip 연산 수행여부를 확인할 수 있다.

1. parity가 같은 쌍의 비트를 확인한다. 비트 값이 변한 경우 flip 연산이 수행된 것이다.
2. flip 연산 여부 확인 후, parity가 다른 쌍의 비트를 확인한다. 결과에 따라 reverse가 수행되었는지 아닌지 알 수 있다.

 

parity가 같은 쌍만 있는 경우, reverse 연산은 의미가 없다.

비트 하나만 확인하여 flip 여부만 확인하면 된다.

 

parity가 다른 쌍만 있는 경우, reverse 연산과 flip 연산의 수행 결과는 같다.

비트 하나만 확인하여 필요할 때만 flip해주면 된다.

 

정리하면 다음과 같이 풀이하면 된다.

1. 10개의 비트 쌍의 parity를 구한다.
2. 비트 쌍마다 비트 값을 구한다.
3. \(10n+1\)번째 인터렉션 마다는 reverse와 flip 연산 수행 여부를 추가적으로 체크한다.

 

---

Subtask 3

B=100일 때, 상기 방법으로 비트를 구할 경우, 인터렉션 제약을 어기게 된다.

 

비트 값을 구하는 동시에, parity도 구하자.

parity도 사실, parity가 같은 쌍과 parity가 다른 쌍 하나 씩만 필요하기 때문에, Subtask 2처럼 모든 쌍의 parity를 구할 필요가 없다.

• flip 여부를 알기 위해서는 parity가 같은 쌍 하나만 알면 된다.
• reverse 여부를 알기 위해서는 parity가 같은 쌍 하나와 parity가 다른 쌍 하나만 알면 된다.

 

 

비트 값을 찾은 쌍 중, parity가 같은 쌍이 있는 경우, flip 여부를 확인하는데 문제없다.

비트 값을 찾은 쌍 중, parity가 같은 쌍만 있는 경우, 현재 찾은 값들 중 reverse의 결과는 같기 때문에 reverse 여부는 확인할 필요가 없다.

 

비트 값을 찾은 쌍 중, parity가 다른 쌍도 있는 경우, reverse 여부를 확인하는데 문제없다.

비트 값을 찾은 쌍 중, parity가 다른 쌍만 있는 경우, reverse와 flip의 각 연산 후 결과값이 같기 때문에, 값이 변했을 경우에만 flip을 적용해주면 된다.

 

 

인터렉션 호출 수는 짝수로 맞추는게 편리하다.

쌍 단위로 비트를 구하기 때문에 구하는 것은 문제가 되지 않지만, 만약 reverse 체크나 flip 체크를 위해 인터렉션을 한 번만 수행한 경우 더미 인터렉션을 한 번더 수행하여 짝수로 맞추면 편리하다.

 

2번의 인터렉션으로 연산 수행 여부를 구할 수 있고 총 인터렉션 호출 수는 124가 된다.