Monday, November 9, 2015

A week with stabilizers

Open Cup 2015-16 Grand Prix of Ekaterinburg took place last week (problems, results, top 5 on the left). Congratulations to the XZ team on their first win of the season! The results were decided by problem H, which asked to count how many different permutations can be generated by a given set of permutations of order at most 15, and thus boiled down to a beautiful but a bit obscure algorithm: the Schreier–Sims algorithm. In my view, the most important result of this round is an elementary description of the Schreier-Sims algorithm by Andrey Halyavin and Maxim Akhmedov (in Russian).

Problem A was the nicest in my opinion. You're given 10000 points on the plane such that no three points lie on the same line. You have to build a triangulation of this set of points, and then answer 100000 requests of the form: which triangle of triangulation covers the point with the given coordinates? You're free to pick any triangulation, so the goal is to pick such one that allows answering these requests quickly.

Thanks for reading, and check back soon for this week's summary!

No comments:

Post a Comment