Блог пользователя ricardogg

Автор ricardogg, история, 5 лет назад, По-английски

I often come across problems that involve deleting both rows and columns in matrix in order to create some special matrix. One example I noticed today is the problem Coin Grid from the CSES problem set (link). I couldn't find an editorial for the task, and I never knew how to approach such problems, even thought I have seen couple of them. Can you give me some general hints and advices on how to approach such problems, when you need to find minimum moves and you can modify both rows and columns at the same time.

I couldn't find the older problems I have seen, but if you know some, please share them in the comments.

  • Проголосовать: нравится
  • -8
  • Проголосовать: не нравится

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится

This problem can be solved by finding the minimum vertex cover of a bipartite graph. Consider a bipartite graph, where one part corresponds to the rows of the grid and the other part corresponds to its columns. For each coin, connect the vertices of the row and column it is in. In this graph, we now want to select a minimum set of vertices (the moves), such that each edge is incident to at least one vertex. This is called a minimum vertex cover. By Königs theorem this is equal to the maximum matching in bipartite graphs, which can be found efficiently using the standard algorithm.