It was a long day, trying to finish the very late SRM 621 editorial. I eventually improvised something. I tried to learn as much as possible about suffix automata until I can at least explain the solution with some more detail than the sketches.
So then the match started, I wasn't too thrilled because it is a 9:00 PM match and they tend to be... boring and have too few coders. But oh well...
Div1 250: The one with roads
You are given a weighted complete directed graph (A map of roads connecting each pair of cities) and a integer `T`. On a special holiday, for each ordered pair of distinct cities `(i,j)` a bus must travel from city `i` to city `j`, the path used by the bus must be the shortest possible. If there are multiple shortest pats, the bus driver may pick any of them - We don't know which. A road between two cities is unsafe if it is possible that more than `T` buses will go through it. Find the total sum of lengths of unsafe roads.
The thing here is how to know if a road might be used by a bus. There are `O(n^2)` buses and each might use each road. For pair of cities `(a,b)` , then road `(x -> y)` is used if and only if: mindist[a][x] + road[x][y] + dist[y][b] = dist[a][b]. Where mindist[p][q] is the minimum distance between cities p and q and road[p][q] is the length of the direct road connecting them. We can find mindist[p][q] in `O(n^3)` with Floyd-Warshall, sure, we could do something even faster, but it is not needed because the logic (picking `a,b,x,y` is `O(n^4)`.
Code some cute python code, submit:
class BuildingRoutes:
def build(self, dist, T):
n = len(dist)
allN = range(n)
# turn string list dist into a matrix:
dist = [ [ord(x)-ord('0') for x in row] for row in dist ]
# number of times a road might be used
roadcount = [ [0] * n for i in allN ]
INF = 10**9
# Floyd-Warshall
mindist = [ [dist[i][j] for j in allN] for i in allN ]
for k in xrange(n):
for i in xrange(n):
for j in xrange(n):
mindist[i][j] = min(mindist[i][j], mindist[i][k] + mindist[k][j])
# Find potential uses:
for a in allN:
for b in allN:
if a != b:
for x in allN:
for y in allN:
if x != y:
if mindist[a][x] + dist[x][y] + mindist[y][b] == mindist[a][b]:
roadcount[x][y] += 1
res = 0
for i in allN:
for j in allN:
if roadcount[i][j] >= T:
res += dist[i][j]
return res
Unfortunately, I forgot to test the largest case before submitting the solution. I test the largest case and it turns out it times out. Very disappointing that it times out in python. And it is only by a few seconds. I had to remake the code in c++, lost plenty of points because of spending double time and recoding. I should know better, need to keep in mind that `50^4` is too bad for python.
int build(vector<string> dist, int T)
{
// O(n^4) too slow in python, had to migrate code to c++ . arg
int n = dist.size();
vector<vector<int>> roadcount(n, vector<int>(n,0));
const int INF = 1000000000;
vector<vector<int>> mindist(n, vector<int>(n,INF));
// Floyd-warshall
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
mindist[i][j] = dist[i][j] - '0';
}
}
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
mindist[i][j] = min(mindist[i][j], mindist[i][k] + mindist[k][j]);
}
}
}
// for each pair of cities (a,b), find if a road(x,y) could be used:
for (int a = 0; a < n; a++) {
for (int b = 0; b < n; b++) {
for (int x = 0; x < n; x++) {
for (int y = 0; y < n; y++) {
if ( (x != y) && (a != b) ) {
if (mindist[a][x] + (dist[x][y]-'0') + mindist[y][b] == mindist[a][b]) {
roadcount[x][y]++;
}
}
}
}
}
}
int res = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (roadcount[i][j] >= T) {
res += dist[i][j] - '0';
}
}
}
return res;
}
Div1 500: The one with tree dp (Tree dp again...
You are given a weighted tree. We want to divide the tree into a minimum number `K` of connected subtrees such that their diameter does not exceed `K`. (Diameter is the maximum distance between two vertices in a subtree).
Okay, I didn't have time to solve . I got distracted and was already quite late because of 250. But here is what seems like a solution:
Imagine the root. Either THE root, or a node we are treating as root because we cut the edge above it. Then we have to decide if the children of the root will be used in the subtree or not.
In general, it is best to use a child instead of not using it. Because if we do not use it, we forcefully are creating a new tree, but if we do not, we might be able to avoid it. The issue is how to balance out the lengths of the subtrees that we will keep conencted to the root.
This is a neat trick: Let `M` be the maximum distance between the root and the nodes in one of the arms of the subtree. Then the maximum distance between the root and the nodes in the other arms cannot be greater than `K - M`. We can pick one of the children, decide it will be the one with distance `M`, and then the remaining children must have arms of distance of at most `K - M`. If the edge connecting the root to a child is larger than `K - M`, we cannot use this child and must create a new tree.
We need to solve a subproblem: Do the decision for a subtree rooted at a node `X`, such that the distance between `X` and any grand children cannot exceed `M` and the diameter cannot exceed `K`. This is solved in a similar way, picking a children of `X` to have the maximum distance.
All in all, we have to solve the problem for `f(X, M)` , `M` will not exceed 500, (because `K` is at most 500), so we will be fine.
Challenge phase / etc
Challenge phase already started, I will go check what hapens. Scheduling this post so that it is posted when the challenge phase ends.
