jinhan814   1년 전

해당 문제는 쿼리 순서를 적절히 조정하여 총 연산량($\mathtt{ops}$)을 줄이는 방식으로 채점이 진행되며, 10개의 tc에 대해 tc별로 다음과 같은 방식으로 점수가 부여됩니다.

$$\mathtt{score} = \min \left( 6, 6 \cdot \frac{2 \cdot 10^7}{\mathtt{ops}} \right)$$ 
현재 문제의 채점 기준은 각 tc 별 $\mathtt{score}$의 합이 $60$이어야 ac를 받도록 설정되어있기에 모든 tc에 대해 $\mathtt{score} = 6 \Leftrightarrow \mathtt{ops} \leq 2 \cdot 10^7$을 받는 풀이를 구성해야 합니다. 그러나 제공되는 채점용 입력 데이터(input0, input1)를 분석한 결과, $\mathtt{ops} \leq 2 \cdot 10^7$을 만족하는 쿼리 순서를 구성하는 것이 거의 불가능함을 확인했습니다. 구체적으로는 다음과 같은 사실을 확인했습니다.

본 문제는 $[1, 10^5] \times [1, 10^5]$ 범위의 $10^5$개의 정수 좌표 점의 Open L1 TSP(모든 점을 포함하는 path)를 구하는 문제입니다. 대부분의 TSP Solver는 Closed TSP(모든 점을 포함하는 cycle)를 구해주기에 우선 Closed TSP의 해를 확인했습니다.

  • Concorde TSP Solver를 이용해 Closed TSP의 근사해와 최적해의 하한을 구한 결과는 다음과 같습니다.
  • QSopt Solver를 이용해 계산한 input0의 최적해의 하한은 $20\,024\,022$입니다. (해당 Solver는 TSP를 ILP로 환원한 뒤 해의 하한과 상한을 구해줍니다)
  • QSopt Solver를 이용해 계산한 input1의 최적해의 하한은 $20\,069\,648$입니다.
  • Lin-Kernighan Solver를 이용해 계산한 input0의 해는 $20\,082\,647$입니다. (가중치가 가장 큰 간선 삭제)
  • Lin-Kernighan Solver를 이용해 계산한 input1의 해는 $20\,124\,198$입니다. (가중치가 가장 큰 간선 삭제)

Closed TSP와 Open TSP의 차이는 시작점과 끝점을 연결하는 간선의 유무이며, 문제 조건 상 간선의 가중치는 $199\,998$을 넘지 않기에 구한 하한에 $199\,998$를 빼면 Open TSP의 하한을 얻을 수 있습니다. 이는 input1 기준 $19\,924\,200$으로 매우 tight합니다. 또한 시작점과 끝점을 연결하는 간선을 삭제해 실제로 $199\,998$에 준하는 개선을 보이긴 어렵다고 생각됩니다. 이와 관련해, $(1, 1) \rightarrow (10^5, 1) \rightarrow (10^5, 10^5)$ 경로를 강제해 Closed TSP를 구한 뒤 해당 경로를 지워서 Open TSP를 구한 결과는 다음과 같습니다.

  • Lin-Kernighan Solver를 이용해 계산한 input0의 해는 $20\,081\,000$입니다.
  • Lin-Kernighan Solver를 이용해 계산한 input1의 해는 $20\,120\,985$입니다.

이는 단순히 가중치가 가장 큰 간선을 삭제하는 방법보다 $2\,000 \sim 4\,000$ 정도 개선된 값이지만, 마찬가지로 $2 \cdot 10^7$ 이하 해를 구하긴 어렵다고 생각합니다. input0, input1 뿐만 아니라 로컬에서 생성한 랜덤 데이터와 다른 테스트 데이터도 같은 경향을 보였습니다.

이러한 사실을 고려할 때, 본 문제는 만점을 의도한 문제라기보다는, 제한된 시간 내에 휴리스틱으로 가능한 한 많은 점수를 획득하도록 설계된 문제로 보입니다. 실제로 충분한 계산 시간을 확보하더라도 $60$점을 달성하는 것이 매우 어렵거나 불가능에 가깝고, $1$초 제한 내에서는 사실상 달성 불가능한 수준입니다.

이에 채점 기준을 누적 점수가 59점 이상이면 "맞았습니다"로 변경하는 걸 제안드립니다. 유사한 유형의 문제인 814 - 2, 814 - 3, 3-SAT 2 역시 이와 같은 채점 기준을 가지고 있으며, 해당 점수는 로컬에서 충분한 계산 시간을 이용하면 재현 가능하기 때문에 위와 같이 조건을 완화하면 충분히 챌린징하면서 현실적으로 해결할 수 있는 문제가 될 거라 생각합니다.

jinhan814   1년 전

preview

참고용으로 경로를 추가한 뒤 input1에 대한 Closed TSP 해를 구한 결과를 첨부합니다.

이상의 내용은 각 테스트 케이스에 대해 $\mathtt{ops} \leq 2 \cdot 10^7$ 을 만족하는 해를 구성하는 것은 현실적으로 어려우며, 실제로 불가능할 가능성이 높다는 추측을 담고 있습니다. 다만 Open TSP의 lower bound가 실제로 $2 \cdot 10^7$  을 초과함을 확인한 것은 아니므로, 모든 테스트 케이스에 대해 $\mathtt{ops} \leq 2 \cdot 10^7$  을 만족하는 해가 존재할 가능성을 완전히 배제할 수는 없습니다. 이 점 참고 바랍니다.

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