Saturday, October 26, 2019

A Stonefeang week

There were a couple of rounds during the Jun 17 - Jun 23 week. One of them was Codeforces Round 569 (problems, results, top 5 on the left, analysis). Radewoosh and ACRush have managed to finish the problemset in the last minutes of the contest (just 43 seconds before the end in case of Radewoosh!), and thus jumped far above everybody else. Well done!

The other round was TopCoder SRM 761 (problems, results, top 5 on the left, my screencast). The hard problem was solved by just 3 contestants, and my solution employed a somewhat general trick that I nevertheless don't remember appearing in many other problems. You are given a graph with n<=15 vertices and m<=200 edges. For each k between n-1 and m, compute the number of spanning sets of edges of size k (ones that connect all n vertices together). The numbers need to be computed modulo 109+7.

Thanks for reading, and check back for my solution of this problem!

No comments:

Post a Comment