I have been trying to solve this problem but I don't seem to find a correct solution to it. http://acm.tju.edu.cn/toj/showp3260.html

# | User | Rating |
---|---|---|

1 | tourist | 3557 |

2 | Radewoosh | 3468 |

3 | Um_nik | 3429 |

4 | Petr | 3354 |

5 | Benq | 3286 |

6 | mnbvmar | 3280 |

7 | wxhtxdy | 3276 |

7 | LHiC | 3276 |

9 | ecnerwala | 3214 |

10 | yutaka1999 | 3190 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 191 |

2 | Radewoosh | 180 |

3 | tourist | 172 |

4 | Vovuh | 165 |

4 | PikMike | 165 |

4 | antontrygubO_o | 165 |

7 | rng_58 | 160 |

8 | majk | 156 |

8 | Um_nik | 156 |

10 | 300iq | 155 |

I have been trying to solve this problem but I don't seem to find a correct solution to it. http://acm.tju.edu.cn/toj/showp3260.html

↑

↓

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/18/2019 03:15:54 (e1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

You need some brain.

;)

Sorry, but I am not so good to solve all the problems that I read, some problems are out of my reach and that's why I ask sometimes for an explanation or a hint to learn and solve it.

Repeat until there is a class, and only one girl needs only one this class, exclude this girl and this class.

Now consider graph where each vertex is an class, and there is an edge between A and B iff there is a girl who wants to attend classes A and B.

Divide graph into components of connectivity.

Each component is a cycle, or a path. Note that at each of the two ends of the path there also can be a girl who wants to attend only one class. In each of the components problem can be easily solved.

Thanks for answering, now consider the following problem: Given a set of elements and the profit you can make out of each element, What is the maximum total profit you can make by choosing any subset if there are some edges e(u,v) that don't allow element u to be in the same subset that element v.

Which algorithm can be used to solve this problem?

I don't think this problem has an effective(polynomial) solution. But it is my intuitive opinion.

This problem is a typical clique problem. The maximum clique cannot be found in polynomial time (of course, in case of

P≠NPor something). And the maximum clique can be easily reducted to this problem: if you want to find maximum clique in some graphG, then considerG_{1}is a complementary graph forG. (I'm not sure if the translation is correct; I mean thatG_{1}contains any edge (u,v) if and only ifGdoes not contain it.) Then if you say that the profit of each element equals to one and solve your problem onG_{1}, you will find a maximum clique inG.So, no polynomial solution for this problem may exist. However, there are some nice approaches to solve clique problems (along with a

O(2^{N}*poly(N)) brute force solution, of course). One of the easiest ismeet in the middle. I'll explain how to use this algo to find maximum clique, so you'll be able to adapt it for your own needs.First of all, we split the graph into two parts with equal size ( ± 1 if

Nis odd). Then we find a maximul clique in both parts separately (inO(2^{N / 2}*poly(N))). Now we should find maximum clique which intersects with both parts.For first part we compute some DP

d[mask]. It means "what is the size of a maximum clique in a subgraph specified by this mask". The number of masks is 2^{N / 2}, and every value can be computed inO(poly(N)).Then we will run through all subgraphs in the second part. If the subgraph is not a clique, then skip it. Else compute a value

friends_mask. It relays to some subgraph of the first part, the every vertex of which is connected to every vertex of current subgraph. Consider that the size of current subgraph (in second part) isS1, andd[friends_mask] =S2. We've just found a clique of sizeS1 +S2. Actually, the subgraph of second part is a clique, the subgraph which is mentioned in DP is a clique too, and all vertices of first subgraph are connected to the whole second subgraph.It's easy to prove, that if we select maximum of all

S1 +S2 values, it will be exactly the size of a maximum clique. Adapting this algorithm for the above-mentioned problem should also be not very hard.Excellent explanation ifsmirnov thank you very much.

Your solution is indeed nice. After finding the components it can be seen that it is either a cicle or a path. Then if it is a path using DP a solution can be easily found, and when it is a cicle it can be reduced to a path by taking each node and its two adyacent nodes and using the same algorithm for a path it can be solved as well.