sifat_15's blog

UVALive — 7887 (Back to the Future)
By sifat_15, history, 7 years ago, In English

Can Anyone give the idea for the following Problem UVALIVE — 7887 Back To The Future

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
7 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

First of all lets build a graph with the metal pieces being the nodes and with edges connecting compatible metals. Now what the problem is asking us is to find the largest subgraph (not necessarily connected) such that for each node u in this subgraph the following property holds: A ≤ deg[u] ≤ N - B - 1. Now it all comes down to constructing this subgraph efficiently. We can do this using the following strategy:

1) Start with the whole graph as your subgraph
2) Check if this subgraph is OK. Notice that we can do this by checking if the property holds only for the nodes with the lowest and highest degrees.
3) If it doesn't hold then remove the node for which the property doesn't hold from your subgraph. Go back to (2).

You can do this efficiently by using a set.
Here is my accepted code for the problem.

→ Reply