13166번 - 범죄 파티
정해인 Two Sat + 이분 탐색이 상수 이슈로 TLE를 맞기 쉬운 것으로 알려져 있고, 실제로 채점현황에 TLE가 많이 보입니다. 시간제한을 2초 정도로 늘렸으면 합니다.
해설 슬라이드를 통해 확인 가능한 정해는 2SAT뿐만이 아니고, 훨씬 빠른 풀이도 있습니다.
이분매칭은 조건 몇 개 무시하고 푸는 거라 정해라기보단 별해에 가까운 것 같습니다.
출제자가 고려한 풀이 중 하나가 충분히 돌아가는데 그중 다른 풀이가 시간 내에 돌지 않는다고 해서 시간 제한을 바꿀 필요가 없어 보입니다. 2SAT만을 출제 의도로 볼 근거가 없습니다.
이분매칭은 플로우 알고리즘 특성상 최악의 테케가 없어 O(NsqrtN)에 이분탐색으로 logX가 붙음에도 통과되는 것으로 보입니다. N 제한 100000 (200000)에 NsqrtNlogX이면 AC를 보장하기 힘든 시간복잡도이고, NsqrtNlogX가 통과하는데 NlogX가 통과하지 않는 건 테스트 케이스의 문제일 것이기 때문에 시간 제한을 늘리는 것이 맞다고 생각합니다.
1. 출제자가 상정한 그리디 풀이가 있습니다. (출제자가 상정하지 않은 O(N a(N)) 풀이가 있습니다.)
2. 문제에서 주어진 제약 하에도 이분 매칭이 NsqrtN인가요?
3. 이분 매칭이 시간 초과를 받는 데이터를 추가해 주세요.
4. 시간복잡도가 느린 풀이가 통과한다면, 더더욱 시간 제한을 늘리면 안 되는 거 아닌가요?
댓글을 작성하려면 로그인해야 합니다.
pretty_pi 2년 전
정해인 Two Sat + 이분 탐색이 상수 이슈로 TLE를 맞기 쉬운 것으로 알려져 있고, 실제로 채점현황에 TLE가 많이 보입니다. 시간제한을 2초 정도로 늘렸으면 합니다.