O(n)으로 해결 가능하다는 것이 문제의 의도로 보이는데, 시간 복잡도가 O(n)인 std::shuffle만 사용해도 (물론 그것이 uniform_int_distribution에서 발생한 상수 차이라고 하더라도) TLE가 발생합니다. 시간 제한을 적어도 0.15초 내지 0.2초 이상으로 늘려주세요.
Quick Select를 이용하기 위해서는 1. 평균 시간 복잡도로 작동함을 보장하기 위해 입력의 순서를 섞어주거나 2. 최악 시간 복잡도가 발생할 확률을 극도로 낮추기 위해 피벗을 랜덤으로 잡거나 3. Medians-of-medians 등의 방법으로 최악 시간 복잡도 O(n)을 보장해야 합니다. 시간 제한이 빠듯한 탓에 1번 및 2번 (내지는 심지어 3번이라도)의 접근에서 시간 초과가 발생할 수 있다는 것이 본 요청의 이유입니다. 이 점 고려하여 시간 제한 변경을 요청드리는 바입니다.
별도의 추가 로직 없이 작성한 Quickselect는 최악 $O(n^2)$입니다. 이 시간 제한 변경 요청의 의도는 "단순한 Quickselect를 통과시켜야 한다"가 아니라 "최악 케이스를 피하기 위한 로직을 추가한 Quickselect에서조차 시간 초과가 발생해서는 안 된다"입니다.
hjroh0315 3년 전 5
O(n)으로 해결 가능하다는 것이 문제의 의도로 보이는데, 시간 복잡도가 O(n)인 std::shuffle만 사용해도 (물론 그것이 uniform_int_distribution에서 발생한 상수 차이라고 하더라도) TLE가 발생합니다. 시간 제한을 적어도 0.15초 내지 0.2초 이상으로 늘려주세요.