PROBLEM LINK:
Author: Kamil Dębowski
Testers: Hasan Jaddouh, Sergey Kulik
Editorialist: Pawel Kacprzak
DIFFICULTY:
Hard
PREREQUISITES:
All-pairs shortest paths, math
PROBLEM:
For a given path graph G with additional K edges, the goal is to find the sum of distances between all pairs of vertices i < j.
EXPLANATION:
Subtask 1
In the first subtask, we know that N \leq 40 and K \leq 10. Moreover, there are at most 1000 separated test cases to be handled. However, such a small N allows us to solve the problem in the most straightforward way.
Let’s iterate over all vertices from 1 to N. For a fixed vertex s, we are going to use BFS to compute distances from s to all other vertices. Notice that BFS can be used there because all edges have unit weights, so the distance between a pair of vertices is just the smallest number of edges taken across all paths between them. The complexity of BFS is linear in terms of the number of vertices and edges, and our G has exactly N vertices and N-1+K edges, so the time complexity of a single BFS is O(N+K). After computing distances from s to all other vertices, we can iterate over all vertices v > s and add the distance from s to v to the result. Since we are computing distances from all N vertices, the total time complexity of this method is for a single test case is O(N \cdot (N+K)), which is perfectly acceptable for such small N as we have here, even if there are at most 1000 test cases to handle. For implementation details of this approach please refer to this solution.
Subtask 2
Will be added later
Subtask 3
Will be added later
Subtask 4
Will be added later
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution can be found here.
First tester’s solution can be found here.
Second tester’s solution can be found here.