데이터 만들기 6

프로그래밍 대회용 문제를 낼 때 가장 어려운 일 중 하나는 테스트 데이터를 만드는 일이다. 좋은 테스트 데이터는 문제의 의도에 맞게 짠 코드와 그렇지 않은 코드를 구별해야 한다.

이 문제는 최단 경로를 구하는 프로그램을 제출하는 문제가 아니다. 두 구현을 구분하는 방향 가중치 그래프를 출력하는 문제이다.

코드 A는 최적화 벨만-포드(OptimizedBellmanFord)이고, 코드 B는 수정 다익스트라(ModifiedDijkstra)이다. 두 코드는 모두 카운터를 유지하며, 카운터가 $10^6$을 넘으면 시간 초과이다.

출력할 그래프 $X$는 다음을 만족해야 한다.

1. 코드 A가 $X$를 처리할 때 시간 초과가 나면 안 된다.
2. 코드 B가 $X$를 처리할 때 시간 초과가 나야 한다.

아무 그래프나 허용하면 정답이 여러 개이므로, 그래프는 아래 규칙으로 유일하게 정한다.

정수 $K$, $Q$가 주어지고, 정점 수는 $V = 2K+1$이다. 정점은 $0$부터 $V-1$까지이다.

• 정점 $0$은 나가는 변이 없다.
• 정점 $1$은 정점 $0$으로 가는 가중치 $1$인 변을 하나 가진다.
• 정점 $2$는 정점 $1$로 가는 가중치 $1$인 변을 하나 가진다.
• 각 $t = 1, 2, \ldots, K-1$에 대해 다음 삼각형을 붙인다.
  • 정점 $2t+1$은 정점 $2t$로 가는 가중치 $-2^{t+1}$인 변을 하나 가진다.
  • 정점 $2t+2$는 나가는 변을 두 개 가진다. 첫 변은 정점 $2t+1$로 가고 가중치는 $2^t$이다. 둘째 변은 정점 $2t$로 가고 가중치는 $0$이다.
• 질의는 $Q$개이고, 모두 시작점이 $V-1$, 도착점이 $0$이다.

이 그래프는 음수 가중치를 포함한 삼각형을 체인으로 이은 형태이다. 수정 다익스트라는 우선순위 큐에 같은 정점을 지수적으로 여러 번 넣게 되어 $K$가 커지면 카운터가 $10^6$을 넘는다. 최적화 벨만-포드는 음수 사이클이 없고 정점과 변이 적어 카운터가 한도를 넘지 않는다.

첫째 줄에 정수 $K$, $Q$가 주어진다.

• $1 \le K \le 16$
• $1 \le Q \le 10$

그래프와 질의를 아래 형식으로 출력한다. 같은 줄의 정수는 공백 하나로 구분하고, 줄 끝에는 공백을 두지 않는다.

첫째 줄에 $V$를 출력한다. $V = 2K+1$이다.

다음 $V$줄 가운데 $i$번째 줄($i$는 $0$부터)에는 정점 $i$의 나가는 변 개수 $n_i$를 쓰고, 이어서 $n_i$개의 쌍 $j$ $w$를 쓴다. $j$는 도착 정점이고 $w$는 가중치이다.

그다음 줄에 $Q$를 출력한다.

다음 $Q$줄에 각 질의의 시작점과 도착점을 공백으로 구분해 출력한다.

최적화 벨만-포드와 수정 다익스트라의 의사코드는 다음과 같다. 카운터는 시간 한도를 재는 값이다.

OptimizedBellmanFord
counter = 0
for each query (s, t):
    dist[u] = INF for all u
    dist[s] = 0
    loop V - 1 times:
        change = false
        for each edge (u, v, w) in adjacency list order:
            counter += 1
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                change = true
        if change is false:
            break
    output dist[t]

ModifiedDijkstra
counter = 0
for each query (s, t):
    dist[u] = INF for all u
    dist[s] = 0
    pq.push((0, s))
    while pq is not empty:
        counter += 1
        (d, u) = pq.pop()
        if d == dist[u]:
            for each edge (u, v, w):
                if dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w
                    pq.push((dist[v], v))
    output dist[t]

변은 정점 번호가 작은 것부터, 같은 정점에서는 출력에 적은 순서대로 스캔한다. 수정 다익스트라의 우선순위 큐는 $(d, u)$의 최소 힙이다.