PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author:
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Medium
PREREQUISITES:
None
PROBLEM:
Given N and D, construct any tournament on N vertices with diameter D, or claim that no such tournament exists.
A tournament is a directed graph on N vertices such that, for each 1 \leq i \lt j \leq N, exactly one of the edges i\to j or j\to i exists.
EXPLANATION:
We want a diameter of D, so we definitely need a path with D edges somewhere.
So, let’s start off by having the edges 1 \to 2 \to \ldots \to D \to D+1.
Further, to ensure this is the shortest path from 1 to D+1, we must also ensure that it’s not possible to “short-circuit” the path.
So, for each (i, j) with 1 \leq i \lt j \leq D+1, we’re forced to direct the edges as i \gets j (other than i \to i+1 which forms the path, of course).
Now, it can be seen that this construction is a pretty nice starting point.
Indeed, as long as D \geq 2, we see that:
- Every vertex in [1, D+1] can reach any other vertex in [1, D+1] by following at most D edges, i.e. all shortest paths have length \leq D.
- The path 1 \to D+1 has length exactly D.
In combination with the first point, this means we have a tournament on D+1 vertices with diameter exactly equal to D.
In particular, if D+1 = N this already gives us a valid construction.
We now only need to deal with D+1 \lt N, i.e. need to decide what to do with respect to edges involving vertices in [D+2, N].
Before that however, note that D = 1 is a special case: we’ll have 1 \to 2 but 2 cannot reach 1 yet.
However, having a diameter of 1 means that every vertex should be able to reach every other vertex using a single edge; which is clearly impossible for a tournament since we can’t have 1 \to 2 and 2\to 1 simultaneously.
So, for D = 1, no valid tournament can exist. We thus only deal with D \geq 2.
Let’s return to the initial construction.
We already have a valid tournament on [1, D+1], and need to figure out [D+2, N].
In particular, we need to ensure that:
- Every vertex in [1, D+1] can reach every vertex in [D+2, N], and vice versa.
- Vertices in [D+2, N] can reach each other.
- All of the above must be done using paths of length \leq D, while also not causing the 1 \to D+1 path to become any shorter.
One way of doing that is as follows.
First, let’s start off by directing all remaining edges “backwards”.
That is, for each (i, j) with i \lt j and j \geq D+2, direct the edge as i \gets j.
Then, for each (D, j) with D \lt j, direct the edge forward, i.e. as D \to j instead.
Let’s now look at some pair of vertices (i, j) with i \lt j.
- If i, j \leq D+1, we already know they can reach each other using at most D edges.
- If i \leq D and j \gt D+1, then:
- i can reach j via the path i \to i+1 \to\ldots\to D \to j, which uses at most D edges (specifically, it uses D-i+1).
- j can reach i via just j \to i.
- If i = D+1 and j \gt D+1, then:
- i can reach j via the path i \to (i-2) \to (i-1) \to j, which uses 3 edges.
- j can reach i via j \to i.
- If i, j \gt D+1 then i can reach j via i \to D-1 \to D \to j, and j can reach i using a similar path; either way it’s 3 edges.
- It still takes at least D edges to reach D+1 from 1.
All in all, we’ve obtained a situation where the diameter is at least D (because of 1 \to D+1), and also all other pairs can reach each other using no more than either D or 3 edges.
So, if D \geq 3 this is already a valid construction.
We’ve now seen that D = 1 is impossible, while D \geq 3 is always possible.
What about D = 2?
Consider the following construction.
For each 1 \leq i \leq N-2, add the edges i \to N-1 and i \gets N.
Also add the edge N-1 \to N.
Now,
- N-1 can reach any other vertex with at most two edges, via N-1 \to N \to i.
- N can reach any other vertex with at most two edges, via N \to i \to N-1.
- Vertices in [1, N-2] can reach N-1 and N using at most two edges, via i \to N-1 \to N.
This means we only need to deal with vertices in [1, N-2] now.
However, we’ve not decided on directions for any of these edges yet: so essentially, we’re just looking for a tournament on N-2 edges with D = 2.
This can just be solved recursively, till we end up with some small enough N that’s solvable easily.
In particular, note that N = 3 has a simple solution, by just doing 1 \to 2 \to 3 \to 1.
Since we’re reducing from N to N-2, we’re now able to solve for all odd integers \geq 3.
Finally, we’re left with D = 2 and even N.
This is not quite as trivial, because it turns out that N = 4 doesn’t actually have a solution - a quick way to verify this is to note that starting with the triangle 1\to 2\to 3\to 1 is “forced”, and then due to symmetry there are only 4 different ways to add edges between these and vertex 4 (the number of i \to 4 edges can be 0,1,2,3); and all four choices can be verified to not work.
However, for N = 6 a construction does exist, and goes as follows.
Start with the two disjoint triangles 1 \to 2 \to 3 \to 1 and 4 \to 5 \to 6 \to 4.
Now, add the edges 1 \to 4, 2 \to 6, and 3 \to 5.
Observe that this lets all vertices in [1, 3] reach any vertex in [4, 6] using at most two moves.
There are 6 remaining edges, all of them can be directed from the [4, 6] side to the [1, 3] side; completing the construction.
Once we have N = 6, all further even numbers can be handled via the recursive construction of N from N-2.
TIME COMPLEXITY:
\mathcal{O}(N^2) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n, d = map(int, input().split())
if d == 1:
print(-1)
continue
ans = [ [0 for i in range(n)] for j in range(n) ]
if d == 2:
if n == 4:
print(-1)
continue
if n%2 == 1:
ans[0][1] = ans[1][2] = ans[2][0] = 1
else:
ans[0][1] = ans[1][2] = ans[2][0] = 1
ans[3][4] = ans[4][5] = ans[5][3] = 1
ans[0][3] = ans[1][5] = ans[2][4] = 1
ans[4][0] = ans[5][0] = 1
ans[4][1] = ans[3][1] = 1
ans[3][2] = ans[5][2] = 1
st = 4 if (n%2 == 1) else 7
for i in range(st, n, 2):
ans[i-1][i] = 1
for j in range(i-1):
ans[j][i-1] = ans[i][j] = 1
else:
for i in range(n):
for j in range(i+1, n):
if j <= d:
if i+1 == j: ans[i][j] = 1
else: ans[j][i] = 1
else:
if i == d-1: ans[i][j] = 1
else: ans[j][i] = 1
for a in ans:
print(''.join(str(x) for x in a))