It's SRM 640, that means there have been 140 SRMs since SRM 500, remember SRM 500? It was fun.

## Div1 250: The one with Trees

You have a bunch of stars with different colors. Use Ribbons to connect the stars, so that the ribbons and stars make a tree (connected, no cycles). Only some specific pairs of stars may be connected. Return the minimum number of ribbons connecting two stars with equal colors we should use.

So... isn't this the very definition of the minimum spanning tree problem? You need to find an undirected tree, with a minimum sum of used edge costs. Just make an edge cost 1 if the two stars it connects have the same color.

So just implement Prim's or Kruskal's Minimum Spaning Tree algo. I went for Kruskal because I am odd.

class ChristmasTreeDecoration: def solve(self, col, x, y): n = len(col) # I like python for things like this, create a list of edges (c,u,v) c is cost edges = [ ( int(col[i-1] == col[j-1]), i-1, j-1) for (i,j) in zip(x,y) ] # Precarious union find thingie parent = range(n) def getParent(x): while parent[x] != x: (x, parent[x]) = (parent[x], parent[parent[x]]) return x # Kruskal: total = 0; for (cost, u,v) in sorted(edges): #sorting edges by cost if getParent(u) != getParent(v): #distinct components parent[getParent(u)] = v #connect them total += cost # add cost return total

After coding this and realizing it is super short and elegant I starred at the screen for a while. Skeptical that this was so easy. 250s lately are harder than this. I also doubted for a while if my getParent(x) function is bugged or not. Normally I use a stack to move all x to have parent[x] = the super grand parent. But this seems to work fine.

## Div1 550: The one with bipartite graphs

You are given `n_1,n_2,a,d`, `n_1,n_2 <= 1000000000` return the maximum number of edges in a graph with `n_1+n_2` vertices, where each vertex has degree of at least `d` and the maximum bipartite matching is `a`.

So yeah... this problem exists. I am sure there has to be some sort of solution.

## Div1 1000:

Another problem that probably has a solution. My hunch is that this one is rather easy once you do plenty of math.

## Challenge phase

Nothing to report.

Let's see if that 250 survives.

## 1 comment :

So... Where have you been last 3 months?

Post a Comment