OneWhoKnocks's blog

By OneWhoKnocks, history, 4 years ago, In English

Problem Statement:

There are n Coins present in a cartesian plane. We have been given coordinates(x,y) of these coins. We can take home as much of these coins possible, given constraint that no 2 coins should have either x or y coordinates in common. Find the maximum number of coins we can take back home.

My Approach:

For a particular coin with x and y coordinates, i added 2 vertices(x and y) having an edge between them. So, i was able to convert this problem to a graph problem which will be to find minimum number of vertices to be removed so that each vertex in the graph has an edge with only one other vertex.

I wanted to discuss the possible approaches to solve this problem. Thanks.

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Ok, I'll try.

Construct a bipartite graph which 1 side is a set of nodes representing X-coordinates and the other side is the set of nodes representing Y-coordinates. An edge represents a coin.

According to the statement, you will pick maximum number of edges such that each node will be adjacent to at most 1 edge in the picked set. That is equivalent to the maximum matching of the graph.

Now it is a well-known problem.