10982  Troublemakers
Moderator: Board moderators
10982  Troublemakers
I got WA. my algorithm is:
. first i tried to bicolor given graph.
. then put the same colored vertex in one class and others in another class.
. check that the two class satisfies the given constraints and print the result.
what is wrong with my algo? or give me the correct algo. Please help me.
. first i tried to bicolor given graph.
. then put the same colored vertex in one class and others in another class.
. check that the two class satisfies the given constraints and print the result.
what is wrong with my algo? or give me the correct algo. Please help me.
2 Per:
I am a little bit confused by your last post.
You want to say that we need to calculate probability
of splitting n/2 pairs and after that just do appropriate
number of random divisions. If feasible division was not found
then it is impossible to split graph in such a way.
Or you mean something else???
I am a little bit confused by your last post.
You want to say that we need to calculate probability
of splitting n/2 pairs and after that just do appropriate
number of random divisions. If feasible division was not found
then it is impossible to split graph in such a way.
Or you mean something else???

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
No. I wanted to say exactly what I said.kp wrote:2 Per:
I am a little bit confused by your last post.
You want to say that we need to calculate probability
of splitting n/2 pairs and after that just do appropriate
number of random divisions. If feasible division was not found
then it is impossible to split graph in such a way.
Thanks, but I can't really claim to have found it... you'll hardly find any maxcut paper not mentioning it.Abednego wrote:Yay Per! You found the solution that I was hoping someone would find. There is also a very simple greedy solution, but the randomized one is a lot more beautiful.
The greedy solution is essentially the derandomization of the randomized one, or are you talking about something else?
Yes, plus it is easy to see why:
Every "troublesome" pair will be considered exactly once (namely, when you have placed one of the members and are deciding where to put the other). At every decision, you "enable" at most half of the pairs that you are considering. Therefore, at the end, you will have "enabled" at most half the total number of pairs. QED.
Every "troublesome" pair will be considered exactly once (namely, when you have placed one of the members and are deciding where to put the other). At every decision, you "enable" at most half of the pairs that you are considering. Therefore, at the end, you will have "enabled" at most half the total number of pairs. QED.
10982  Troublemakers
There are a few output in this problem, aren't there ?
In Sample input .
4 3
1 2
2 3
3 4
>
output can be
1 3 4 / or / 2 / or / 2 3 ???
Then May I print one of them?
============================
sorry for my foor english
In Sample input .
4 3
1 2
2 3
3 4
>
output can be
1 3 4 / or / 2 / or / 2 3 ???
Then May I print one of them?
============================
sorry for my foor english