jlcastrillon's blog

I need some help…
By jlcastrillon, 13 years ago, In English

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

Tags tju
  • Vote: I like it
  • +1
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
13 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

→ Reply
»
13 years ago, # |
  Vote: I like it +4 Vote: I do not like 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.

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 3   Vote: I like it +9 Vote: I do not like it

      This problem is a typical clique problem. The maximum clique cannot be found in polynomial time (of course, in case of P ≠ NP or something). And the maximum clique can be easily reducted to this problem: if you want to find maximum clique in some graph G, then consider G1 is a complementary graph for G. (I'm not sure if the translation is correct; I mean that G1 contains any edge (u, v) if and only if G does not contain it.) Then if you say that the profit of each element equals to one and solve your problem on G1, you will find a maximum clique in G.

      So, no polynomial solution for this problem may exist. However, there are some nice approaches to solve clique problems (along with a O(2N * poly(N)) brute force solution, of course). One of the easiest is meet 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 N is odd). Then we find a maximul clique in both parts separately (in O(2N / 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 2N / 2, and every value can be computed in O(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) is S1, and d[friends_mask] = S2. We've just found a clique of size S1 + 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.

      → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply