ALMROW - Editorial

PROBLEM LINK:

Practice
Contest

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.

I used the same approach that I have used in SUMDIS problem in March Long Challenge for subtask 1/4 with a trick. I have assigned weight of each edge as 1. Getting wrong answer for test case 3.
Can you find error in this approach.

Solution links are pointing to solution of HAIRCUT problem. Plz fix that.

1 Like

Edges aren’t directed here.