hjroh0315   3년 전

O(n)으로 해결 가능하다는 것이 문제의 의도로 보이는데, 시간 복잡도가 O(n)인 std::shuffle만 사용해도 (물론 그것이 uniform_int_distribution에서 발생한 상수 차이라고 하더라도) TLE가 발생합니다. 시간 제한을 적어도 0.15초 내지 0.2초 이상으로 늘려주세요.

startlink   3년 전

Quick select를 사용하는 것이 문제의 의도입니다.

hjroh0315   3년 전

Quick Select를 이용하기 위해서는 1. 평균 시간 복잡도로 작동함을 보장하기 위해 입력의 순서를 섞어주거나 2. 최악 시간 복잡도가 발생할 확률을 극도로 낮추기 위해 피벗을 랜덤으로 잡거나 3. Medians-of-medians 등의 방법으로 최악 시간 복잡도 O(n)을 보장해야 합니다. 시간 제한이 빠듯한 탓에 1번 및 2번 (내지는 심지어 3번이라도)의 접근에서 시간 초과가 발생할 수 있다는 것이 본 요청의 이유입니다. 이 점 고려하여 시간 제한 변경을 요청드리는 바입니다.

startlink   3년 전

제출 번호도 함께 남겨주세요.

hjroh0315   3년 전

66603573번 제출에서 시간 초과가 발생하지 않아야 합니다.

startlink   3년 전

재채점했습니다.

kimyeonwoo0506   3년 전

68762526번 제출이 시간초과가 나는건 아직 처리가 안된 부분이 있어서 일까요...?

95%에서 특정 케이스에 대하여 시간초과가 나는 것 같은데, 단순히 Quick select 알고리즘 그 이상의 것을 요구하는 문제인지 질문드립니다.

hjroh0315   3년 전

별도의 추가 로직 없이 작성한 Quickselect는 최악 $O(n^2)$입니다. 이 시간 제한 변경 요청의 의도는 "단순한 Quickselect를 통과시켜야 한다"가 아니라 "최악 케이스를 피하기 위한 로직을 추가한 Quickselect에서조차 시간 초과가 발생해서는 안 된다"입니다.

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