Monday, January 27, 2020

Best problems of 2019

Just like last couple of years (2017, 2018), I've went through the problems I mentioned in 2019 to find the ones I liked the most. I have also looked at some of the problems recommended in this post, in this post, and in various private messages. Of course, this is still an entirely subjective exercise, and it is certainly easier for me to like a problem that I have solved or tried to solve than one that I did not. Here is the shortlist (for those interested, here is a slightly bigger one), as usual in chronological order:
  • The Open Cup problem "Alien Invasion" about finding an area of a polygon by interactively asking about areas of convex hulls, by ???, with solution in this post.
  • The AtCoder problem "Triangular Lamps Hard" about finding the original state of a cellular automaton on a triangular grid, by rng_58 and yosupo, with solution in this post.
  • The Open Cup problem "Equanimous" about inserting + and - between digits of a number to get the smallest positive value and grouping all numbers in a large segment by that value, by tangjz, with solution in this post.
  • The TopCoder problem "SpanningSubgraphs" about counting spanning subgraphs with each number of edges, by lewin, with solution in this post.
  • The IOI problem "Split the Attractions" about splitting a graph into three parts of given size such that at least two are connected, by LGM and Saeed_Reza, with solutions discussed in this Codeforces post.
Which one do you think is the very best? Also, please help me fill the unknown problem authors in comments!