A matroid week

Two weeks ago, TopCoder SRM 774 has started a new race for a TCO20 spot (problems, results, top 5 on the left). The 1000-pointer was tricky both algorithmically and from the implementation standpoint, causing a few resubmissions and a few failed systests for high-scoring solutions. As a result, the total scores were not that high and the importance of the challenge phase was amplified.

In my previous summary, I have mentioned a Codeforces problem: you are given a 20x20 grid colored as a chessboard, with the top-left corner colored black. Some of the cells are removed from the grid, the remaining cells form a 4-connected piece and include the top-left corner. You need to insert some walls between the remaining cells in such a way that we get a good labyrinth: there must be exactly one way to get from each cell to each other cell. Moreover, we want each black cell (remember the chessboard coloring) except the top-left cell to not be a dead-end in the labyrinth: each such cell must have at least two accessible neighbors.

When solving this problem during the round, I have made the correct first step: we want to find a spanning tree where the degree of each black cell is at least two, which is equivalent to finding a spanning forest where the degree of each black cell is at least two as we can always add more edges to get a tree.

But then I've tried to find some greedy approach that takes two edges for each black vertex without forming cycles, realized that it's not always possible, thought that if we want to add an edge that forms a cycle we need to remove some other edge from this cycle and choose another edge for its black vertex, and then somehow failed to notice that I'm just describing finding an alternating path for a matroid intersection problem :) The matroids in question are the cycle matroid and the matroid where independent sets have degree <=2 for each black vertex, and we need to check if the biggest independent set in their intersection has degree of exactly 2 for each black vertex.

In that summary, I have also described a solution to an AtCoder problem that felt like unexplained magic. Um_nik has brought a simpler quadratic solution to my attention: instead of starting from n scores of 1 and adding 1 to a suffix n-1 times, we can start from n scores of n and subtract 1 from a prefix any number of times! The reason we don't need to limit the number of operations to n-1 in this approach is that if the first problem has zero or negative score, then the constraint about the sum of the first k+1 numbers being greater than the sum of the last k numbers would be necessarily violated.

This means we can remove the number of operations dimension from our dynamic programming and it becomes quadratic. This is not directly equivalent to the magical solution, but at least it explains why there's a fertile ground for one.

I have also promised to organize a poll about the best problem of 2019, but for that I need to review all my posts from last year and also the other excellent candidates you shared with me on Codeforces, so this will take some more time. Stay tuned :)

Thanks for reading, and check back for more!