cywohoy   2년 전

일단 주어진 조건을 통해 최악의 경우인 n=40, k=2인 경우 정해를 통해 문제를 해결하였을 때 반례가 발생할 확률이 대략 4e-13입니다.

The second line contains n distinct integers p1, p2, . . . , pn (1 ≤ pi ≤ n) — the resulting permutation. It is guaranteed that this permutation was generated using the algorithm described above for some k such that 20k ≤ n.

위 조건을 통해 각각의 테스트 케이스가 무작위적으로 생성되었다는 것 자체는 보장됩니다. 여기에 문제가 되는 것은, 해당 순열이 Petr's Algorithm을 이용해 생성되었다는 걸 보장하더라도 반례에 해당하는 순열이 생성될 확률이 0은 아니라는 것입니다. 물론 일반적인 무작위화 문제들과 같이 (solved.ac의 Unrated 기준 역시 '문제 상황만을 근거로 첫 번째 제출의 오답 확률을 0.01%* 미만으로 낮출 수 없는 문제'를 조건으로 제시하고 있습니다) 4e-13이라는 확률은 큰 문제가 되어 보이지 않습니다.

문제가 되는 것은 테스트 케이스의 개수를 명시하지 않았고, 각각의 순열이 선택적으로 골라지지 않았다는 것 역시 명시되어있지 않은 부분입니다. 충분히 많은 알고리즘의 시행으로 반례에 해당하는 순열이 생성될 수 있기 때문에, 극단적으로 1e100개의 테스트 케이스가 들어온다면 4e-13의 확률로 오답 확률을 0.01% 미만으로 낮출 수 있다고 보기 어렵습니다. 다만 이 부분은 확인 결과 다른 무작위화 문제들에도 비슷하게 적용되는 것으로 보아 실제로는 그다지 고려 대상이 되지 않는 것으로 판단했습니다. (이 부분은 제가 이해를 올바로 하지 못한 것일 수 있습니다.) 

그러나 두 번째, 각각의 순열이 선택적으로 골라지지 않았다는 조건은 명시되어야 한다고 생각합니다. 역시나 극단적으로 Petr's Algorithm을 1e100회 시행 후 반례에 해당하는 순열만을 테스트 케이스로 제공하는 경우 역시 'this permutation was generated using the algorithm described above'라는 조건에 위배된다고 말할 수 없기 때문입니다. 

따라서 '해당 알고리즘을 통해 생성된 모든 순열이 테스트 케이스로 주어진다'와 같은 조건이 추가되어야 실제로 해결 가능한 문제라고 볼 수 있을 것이라 판단됩니다.

cywohoy   2년 전

더하여, 조금 더 조건을 명확하게 하고 싶다면 k의 최솟값을 구하라는 방향으로 문제를 수정할 수도 있겠으나, 정당성 증명(확률 계산) 자체도 이 문제의 일부라고 생각하는 만큼 그 부분에 대해서는 더 많은 논의가 필요해 보입니다.

cywohoy   2년 전

다시 구해 보니 최악의 경우가 n = 2, k = 40이 아니네요. n이 증가할수록 반례가 발생할 확률이 e^-20, 대략 2e-9에 수렴합니다. 위의 글과 직접적인 관련은 없지만, 잘못된 내용이기에 정정합니다.

iktk   2년 전

문제 조건상 k의 최솟값을 구할 수 있을 뿐 상한은 구할 수 없는 것 같은데요, (더 큰 k로 돌리면 더 작은 k로 돌린 모든 결과를 만들어낼 수 있음) 

k의 최솟값을 구하는 문제로 수정하면 문제 없지 않을까요?

cywohoy   2년 전

문제에서 요구하는 것에 '정해로 문제를 풀었을 때 가능한 k의 최솟값이 실제 k가 아닐 확률'이 충분히 작음을 보여 정당성을 증명하는 과정까지도 포함된다고 생각했어요. k의 최솟값을 구하도록 수정한다면 문제의 원래 취지와 어긋나지 않을까 하는 생각이 드네요. 문제에서 20k <= n으로 한정지은 것도 확률적인 부분 때문인 것으로 판단했습니다.

댓글을 작성하려면 로그인해야 합니다.