Making test data 6

Writing a contest problem is hard, and the hardest part is often the test data. Good tests separate a solution that matches the intended algorithm from one that does not.

This task does not ask you to compute shortest paths. It asks you to print a directed weighted graph that separates two implementations.

Code A is OptimizedBellmanFord. Code B is ModifiedDijkstra. Both keep a counter. If the counter exceeds $10^6$, the run is treated as time limit exceeded.

Graph $X$ must satisfy the following.

1. Code A must not exceed the time limit on $X$.
2. Code B must exceed the time limit on $X$.

Many graphs would work, so the graph is fixed by the following rules.

Integers $K$ and $Q$ are given. The number of vertices is $V = 2K+1$. Vertices are numbered $0$ through $V-1$.

• Vertex $0$ has no outgoing edges.
• Vertex $1$ has one edge to vertex $0$ of weight $1$.
• Vertex $2$ has one edge to vertex $1$ of weight $1$.
• For each $t = 1, 2, \ldots, K-1$, attach the following triangle.
  • Vertex $2t+1$ has one edge to vertex $2t$ of weight $-2^{t+1}$.
  • Vertex $2t+2$ has two outgoing edges. The first goes to vertex $2t+1$ with weight $2^t$. The second goes to vertex $2t$ with weight $0$.
• There are $Q$ queries, each from $V-1$ to $0$.

The graph is a chain of triangles that include negative weights. ModifiedDijkstra reinserts the same vertices into the priority queue an exponential number of times, so the counter exceeds $10^6$ when $K$ is large. OptimizedBellmanFord sees no negative cycle and only a few vertices and edges, so its counter stays under the limit.

The first line contains two integers $K$ and $Q$.

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

Print the graph and the queries in the format below. Separate integers on the same line with a single space. Do not put a trailing space at the end of a line.

Print $V$ on the first line, where $V = 2K+1$.

Then print $V$ lines. The line for vertex $i$ (with $i$ starting at $0$) starts with $n_i$, the number of outgoing edges, followed by $n_i$ pairs $j$ $w$, where $j$ is the head and $w$ is the weight.

Then print $Q$.

Then print $Q$ lines, each with the source and the target of one query.

Pseudocode for the two implementations follows. The counter is the time-limit meter.

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]

Edges are scanned from smaller vertex indices to larger ones. Edges of the same vertex are scanned in the order they are printed. The ModifiedDijkstra priority queue is a min-heap on $(d, u)$.