고로정렬의 복수 timer 20s memory 1024MB

이 문제에서 어떤 것이 무작위로 선택된다고 말할 때는, 가능한 모든 경우 중에서 균등한 확률로 선택되며, 다른 어떤 선택과도 독립적으로 선택된다는 뜻이다.

코드 잼 참가자들은 한때 막강한 고로가 정수 배열을 정렬하도록 도와준 적이 있다. (이 문제를 풀기 위해 그 문제를 읽을 필요는 없다.) 다시 한 번, 고로가 당신의 도움이 필요하다. 그는 탁자 위에 한 줄로 \mathbf{N}개의 상자를 놓아 두었고, 왼쪽에서 오른쪽으로 1부터 \mathbf{N}까지 번호가 매겨져 있다. 각 상자에는 공이 정확히 하나 들어 있다. 공에도 1부터 \mathbf{N}까지 번호가 매겨져 있다. 고로는 모든 i에 대해 공 i가 상자 i에 들어가기를 원한다. 즉 공들이 정렬된 순서로 놓이기를 바란다. 하지만 처음에는 그렇지 않다.

고로가 강력한 주먹으로 탁자를 한 번 치면, 공들이 공중으로 튀어 올라 다시 상자들로 떨어진다. 고로는 이를 매우 정확히 해낼 수 있어서, 각 상자에 공이 정확히 하나씩 떨어지게 된다. 어떤 공은 원래 나오던 상자에 다시 떨어질 수도 있고, 다른 상자로 떨어질 수도 있다.

더 좋은 점은, 고로가 매번 탁자를 치기 전에 상자에 색을 지정할 수도 있다는 것이다. 그러면 고로는 색이 c인 상자에서 나온 공이 항상 색이 c인 상자로만 떨어지도록 탁자를 칠 수 있다. 이 정확도는 놀랍지만, 고로가 제어할 수 있는 것은 여기까지이다. 같은 색 안에서는 공들이 상자들에 무작위로 배정된다.

예를 들어, 공들이 (위 그림처럼) 1, 4, 3, 6, 5, 2 순서로 놓여 있다고 하자. 고로는 — 꼭 최적은 아닐 수 있지만 — 첫 번째 상자를 빨간색, 두 번째와 여섯 번째 상자를 초록색, 세 번째부터 다섯 번째 상자를 파란색으로 칠하기로 할 수 있다. 그러고 나서 고로가 탁자를 치면,

• 첫 번째 상자에 있는 1은 빨간색 상자가 그 상자 하나뿐이므로 다시 같은 상자로 떨어진다.
• 두 번째와 여섯 번째 상자에 있는 4와 2는 확률 \frac{1}{2}로 제자리에 남고, 확률 \frac{1}{2}로 서로 자리를 바꾼다.
• 세 번째, 네 번째, 다섯 번째 상자에 있는 3, 6, 5는 다음 순서 중 하나가 되며, 각각의 확률은 \frac{1}{6}이다:
  • 3, 6, 5
  • 3, 5, 6
  • 6, 3, 5
  • 6, 5, 3
  • 5, 3, 6
  • 5, 6, 3

따라서 예를 들어, 한 번의 충격 후 공들의 순서가 1, 2, 3, 5, 6, 4가 될 확률은 \frac{1}{12}이다. 고로가 이런 결과나 다른 정렬되지 않은 결과를 얻으면, 다음 라운드를 위해 다시 상자 색을 지정해야 하고, 결국 1, 2, 3, 4, 5, 6으로 정렬된 상태에 도달할 때까지 이를 반복해야 한다. 고로는 이전에 어떻게 색을 지정했는지와 무관하게, 매번 탁자를 치기 전에 어떤 방식으로든 색을 지정할 수 있다.

공들을 효율적으로 정렬할 수 있는 더 나은 전략을 구현하도록 고로를 도와줄 수 있겠는가? 공들은 처음에 무작위의 정렬되지 않은 순서로 시작함이 보장된다.